The constant-deviation conjecture for colour-balanced perfect matchings

Let K2ktK_{2kt} be the complete graph on 2kt2kt vertices, and let c ⁣:E(K2kt)[k]c\colon E(K_{2kt})\to [k] be a kk-edge-colouring. Call cc colour-balanced if every colour appears equally often, and for a perfect matching MM define

fc(M)=i=1kc1(i)Mt.f_c(M)=\sum_{i=1}^k\left|\left|c^{-1}(i)\cap M\right|-t\right|.

Constant-deviation conjecture. There exists an absolute constant CC such that for all positive integers kk and tt, every colour-balanced kk-edge-colouring of K2ktK_{2kt} admits a perfect matching MM satisfying fc(M)<Cf_c(M)<C.

This conjecture proposes that the colour imbalance can be bounded independently of both the number of colours and the matching size. The source presents it as an open problem, contrasting it with an O(k2)O(k^2) upper bound and a constant lower bound for matchings in complete graphs.

Sources & referencesView supporting material

Primary source

Emma Hogan, Alex Scott and Dmitry Tsarev, “Colour-balanced subgraphs”, arXiv:2604.09449 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.