A uniform bound on almost colour-balanced perfect matchings in colour-balanced cliques

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 clique $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 colouring $c:E(K_{2nk})\to [k]$, we seek to find a perfect matching $M$ minimising $f(M)={\sum }_{i=1}^k||c^{-1}(i)\cap M|-n|$. The previous best upper bound, due to Pardey and Rautenbach, was $\min f(M)\le \mathcal{O}(k\sqrt{nk\log k})$. We remove the $n$-dependence, proving the existence of a matching $M$ with $f(M)\le 4^{k^2}$ for all $k$.

arXiv comment12 pages