Kohayakawa–Kreuter conjecture on asymmetric Ramsey thresholds

At least 4 years old · documented by

Let H1,…,HrH_1,\dots,H_r be graphs. For a graph HH, write m2(H)m_2(H) for its 2-density, and, when m2(H1)≥m2(H2)m_2(H_1)\geq m_2(H_2), define the mixed 2-density by

m2(H1,H2)=max⁡{e(J)v(J)−2+1/m2(H2):J⊆H1, v(J)≥2}.m_2(H_1,H_2)=\max\left\{\frac{{\mathsf{e}}(J)}{{\mathsf{v}}(J)-2+1/m_2(H_2)}:J\subseteq H_1,\ {\mathsf{v}}(J)\geq2\right\}.

Let Gn,pG_{n,p} be the binomial random graph, and say that it is Ramsey for (H1,…,Hr)(H_1,\dots,H_r) if every rr-edge-colouring contains a monochromatic copy of HiH_i in colour ii. Kohayakawa–Kreuter conjecture. If m2(H1)≥⋯≥m2(Hr)m_2(H_1)\geq\dotsb\geq m_2(H_r) and m2(H2)>1m_2(H_2)>1, then there exist constants C>c>0C>c>0 such that

lim⁡n→∞Pr⁡(Gn,p is Ramsey for (H1,…,Hr))={1if p≥Cn−1/m2(H1,H2),0if p≤cn−1/m2(H1,H2).\lim_{n\to\infty}\operatorname{Pr}(G_{n,p}\text{ is Ramsey for }(H_1,\dots,H_r))= \begin{cases} 1&\text{if }p\geq Cn^{-1/m_2(H_1,H_2)},\\ 0&\text{if }p\leq cn^{-1/m_2(H_1,H_2)}. \end{cases}

The paper confirms this conjecture for all rr-tuples of graphs, so it is solved; the mixed 2-density identifies the threshold scale for asymmetric random Ramsey properties.

References

Primary source

Micha Christoph, Anders Martinsson, Raphael Steiner and Yuval Wigderson, “Resolution of the Kohayakawa-Kreuter conjecture”, arXiv:2402.03045 (2024).

Additional references

4 papers in this index state this conjecture (2021–2024). The statement above is taken from the most recent of them; the others are arXiv:2307.16760, arXiv:2305.19964, arXiv:2105.15151.

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.