Pardey–Rautenbach conjecture on almost colour-balanced perfect matchings
Statement
Let and be positive integers, let be the complete graph on vertices, and let . A colouring is colour-balanced when every colour is used on the same number of edges. For a perfect matching of , define
Pardey–Rautenbach conjecture. If is colour-balanced, then there is a perfect matching of such that
The conjecture seeks a bound depending only on the number of colours, rather than on the number of vertices. Pardey and Rautenbach proposed it after showing that an exactly colour-balanced perfect matching need not exist for three colours; the paper improves the previous bound, which depended on , to an explicit bound of , but does not establish the conjectured quadratic dependence.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.