√k bound for bipartite matching discrepancy

Conjecture 6.1 · arXiv:2604.09449

arXiv Conjecture medium confidence— first stated 2026-04-10

Authors: Emma Hogan, Alex Scott, Dmitry Tsarev

Status open high confidence

Conjecture 6.1 of Hogan–Scott–Tsarev (arXiv:2604.09449) posits that the worst-case $\ell_1$-discrepancy of a representative perfect matching in $K_{n,n}$ under $\mathbb{R}^k$-valued edge weights of $\ell_1$-norm at most 1 is $\Theta(\sqrt{k})$, bridging the authors' own $O(k^2)$ upper bound and the $\sqrt{k/2}$ lower bound from Theorem 5.1 of the same paper. No follow-up resolving this conjecture has been found in the five weeks since posting; the conjecture is open.

Reviewer notes. Paper posted 2026-04-10; only ~5 weeks old at review date. Three web searches and a direct arXiv fetch returned no citing or follow-up papers. The O(k^2) upper bound and the Omega(sqrt(k)) lower bound are both established in arXiv:2604.09449 itself; the conjecture that the true order is Theta(sqrt(k)) remains open with high confidence.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. Let $h\colon E(K_{n,n})\to\mathbb{R}^{k}$ such that $\|h(e)\|_{1}\leq 1$ for all $e\in E(K_{n,n})$. Then there is a perfect matching $M$ of $K_{n,n}$ satisfying [a bound of order $O(\sqrt{k})$ on $\|\sum_{e\in M}h(e)\|_1$].

Context

There is a gap between the $O(k^2)$ upper bound for representative matchings in bipartite complete graphs (Section 1.1) and the worst-case lower bound of $\sqrt{k/2}$ constructed in Theorem 5.1. The authors conjecture that the lower bound gives the correct order, so that the true bound is $\Theta(\sqrt{k})$.

Notes. The conclusion of the conjecture is truncated in the source text; the full right-hand side bound is not reproduced. Based on the surrounding context the conjectured bound is $O(\sqrt{k})$, matching the lower bound of Theorem 5.1.

Source paper

Colour-balanced subgraphs
Emma Hogan, Alex Scott, Dmitry Tsarev · 2026-04-10
https://arxiv.org/abs/2604.09449