Rainbow perfect-matching game threshold conjecture

Let nn be even. In the rainbow perfect matching game RPn\mathcal{RP}_n, played on n/2n/2 copies of KnK_n, Maker wins by claiming a rainbow perfect matching; let bRPnb_{\mathcal{RP}_n} denote its threshold bias. Rainbow-perfect-matching threshold conjecture.

bRPn=(12+o(1))n2log(n).b_{\mathcal{RP}_n}=\left(\frac{1}{2}+o(1)\right)\frac{n^2}{\log(n)}.

This is posed as a conjectural threshold for a natural rainbow extension of the perfect-matching Maker–Breaker game; no supporting theorem or resolution is supplied in the source.

Sources & referencesView supporting material

Primary source

Juri Barkey, Bruno Borchardt, Dennis Clemens, Milica Maksimović, Mirjana Mikalački and Miloš Stojaković, “Rainbow connectivity Maker-Breaker game”, arXiv:2603.09770 (2026).

Additional references

6 papers in this index state this conjecture (2016–2026). The statement above is taken from the most recent of them; the others are arXiv:2302.06146, arXiv:2011.14363, arXiv:1808.04954, arXiv:1605.06752, arXiv:1605.05667.

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.