Rainbow-spanning-tree game threshold conjecture

Let RSn\mathcal{RS}_n be the rainbow-spanning-tree game played on n1n-1 copies of KnK_n, where Maker wins by claiming a rainbow spanning tree, and let bRSnb_{\mathcal{RS}_n} denote its threshold bias. Rainbow-spanning-tree threshold conjecture.

bRSn=(1+o(1))n2log(n).b_{\mathcal{RS}_n}=(1+o(1))\frac{n^2}{\log(n)}.

The paper proves matching order bounds, with a lower-bound constant log(2)/8\log(2)/8 and an upper bound of (1+o(1))n2/log(n)(1+o(1))n^2/\log(n); the conjecture asserts that the upper bound is asymptotically tight.

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

3 papers in this index state this conjecture (2021–2026). The statement above is taken from the most recent of them; the others are arXiv:2508.14186, arXiv:2105.08315.

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.