A Uniform Bound on Almost Colour-Balanced Perfect Matchings in Colour-Balanced Complete Graphs

Abstract

An edge-colouring of a graph $G$ is said to be colour-balanced if there are equally many edges of each available colour. We are interested in finding a colour-balanced perfect matching within a colour-balanced complete graph $K_{2nk}$ with a palette of $k$ colours. While it is not necessarily possible to find such a perfect matching, one can ask for a perfect matching as close to colour-balanced as possible. In particular, for a colour-balanced colouring $c:E(K_{2nk})\rightarrow [k]$, we seek to find a perfect matching $M$ minimising $f(M):= \sum_{i=1}^k\bigl||c^{-1}(i)\cap M|-n\bigr|$.

The previous best upper bound, due to Pardey and Rautenbach, was $\min f(M)\leq \mathcal{O}(k\sqrt{nk\log k})$. We remove the $n$-dependence, proving the existence of a matching $M$ with $f(M)\leq 4^{k^2}$ for all $k$.