ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let nn and kk be positive integers, let K2knK_{2kn} be the complete graph on 2kn2kn vertices, and let [k]={1,2,…,k}[k]=\{1,2,\dotsc,k\}. A colouring c ⁣:E(K2kn)→[k]c\colon E(K_{2kn})\to [k] is colour-balanced when every colour is used on the same number of edges. For a perfect matching MM of K2knK_{2kn}, define

f(M)≔∑i=1k∣∣c−1(i)∩M∣−n∣.f(M)\coloneqq \sum_{i=1}^k\left|\left|c^{-1}(i)\cap M\right|-n\right|.

Pardey–Rautenbach conjecture. If c ⁣:E(K2kn)→[k]c\colon E(K_{2kn})\to [k] is colour-balanced, then there is a perfect matching MM of K2knK_{2kn} such that

f(M)≤O(k2).f(M)\leq \mathcal{O}(k^2).

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 nn, to an explicit bound of 4k24^{k^2}, 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.