Rainbow-connectivity game threshold conjecture

Less than 1 year old · traced to

For the rainbow-connectivity game Cs,n\mathcal{C}_{s,n}, let bCs,nb_{\mathcal{C}_{s,n}} denote its threshold bias. Assume that s=ω(log⁡(n))s=\omega(\log(n)). Rainbow-connectivity threshold conjecture.

bCs,n=(1+o(1))snlog⁡(n).b_{\mathcal{C}_{s,n}}=(1+o(1))\frac{sn}{\log(n)}.

The paper determines the threshold up to a multiplicative factor 22 in this regime, while the displayed asymptotic equality remains conjectural.

References

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).

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.