Rainbow-connectivity game threshold conjecture

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.

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

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.