Constant bound on colour-balanced perfect matching imbalance

Conjecture 6.2 · arXiv:2604.09449

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

Authors: Emma Hogan, Alex Scott, Dmitry Tsarev

Status open high confidence

Conjecture 6.2 from arXiv:2604.09449 was stated by the paper's authors in April 2026 and remains open. The paper establishes an O(k^2) upper bound (Theorem 1.2) on the minimum f_c value achievable by a perfect matching in any colour-balanced k-edge-colouring of K_{2kt}, and constructs a constant lower bound (Theorem 5.3); the conjecture asserts the constant lower bound is tight, i.e. that an absolute constant C independent of both k and t suffices. No follow-up resolving the conjecture was found in the ~5 weeks since posting.

Reviewer notes. The conjecture is very recent (April 2026). The closest precursor is arXiv:2410.07993, which proved a uniform bound of 4^(k^2) (n-independent but k-dependent) for the analogous f(M) measure; the source paper improves this to O(k^2) and conjectures an absolute constant. The paper also notes that a sqrt(k) lower bound for perfect matchings in K_{kt,kt} implies new ideas would be needed. No follow-up paper resolving Conjecture 6.2 was found.

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

Conjecture. There exists some absolute constant $C$ such that for all positive integers $k$ and $t$, every colour-balanced $k$-edge-colouring of $K_{2kt}$ admits a perfect matching $M$ satisfying $f_{c}(M)<C$.

Context

There is a gap between the $O(k^2)$ upper bound from Theorem 1.2 and the constant lower bound constructed in Theorem 5.3 for matchings in complete graphs. The authors conjecture the constant lower bound is tight. They note that a $\sqrt{k}$ lower bound for perfect matchings of $K_{kt,kt}$ implies that new ideas would be necessary to prove this conjecture.

Source paper

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