Pardey and Rautenbach's bounded-deviation conjecture for colour-balanced matchings

From papers

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|.

Pardey and Rautenbach's conjecture. For all integers k2k\geq 2 and t1t\geq 1, every colour-balanced kk-edge-coloured K2ktK_{2kt} admits a perfect matching MM satisfying fc(M)=O(k2)f_c(M)=O(k^2).

This asks for a uniformly controlled colour imbalance in a perfect matching, extending the known bound fc(M)2f_c(M)\leq 2 when k=3k=3. The conjecture remains open in the supplied source.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.