On the Kohayakawa–Kreuter conjecture

article On the Kohayakawa–Kreuter conjecture published yes EDEN KUPERWASSER author WOJCIECH SAMOTIJ author Yuval Wigderson author 2d0023a0-1567-11f0-833d-d5c1e476d4b5 Let us say that a graph G is Ramsey for a tuple (H1, ... , Hr) of graphs if every r-colouring of the edges of G contains a monochromatic copy of Hi in colour i, for some i ∈ [[r]]. A famous conjecture of Kohayakawa and Kreuter, extending seminal work of Rödl and Rucinski, predicts the threshold at which the binomial random graph ´ Gn,p becomes Ramsey for (H1, ... , Hr) asymptotically almost surely. In this paper, we resolve the Kohayakawa–Kreuter conjecture for almost all tuples of graphs. Moreover, we reduce its validity to the truth of a certain deterministic statement, which is a clear necessary condition for the conjecture to hold. All of our results actually hold in greater generality, when one replaces the graphs H1, ... , Hr by finite families H1, ... , Hr. Additionally, we pose a natural (deterministic) graph-partitioning conjecture, which we believe to be of independent interest, and whose resolution would imply the Kohayakawa–Kreuter conjecture. Cambridge University Press2025 eng Mathematical Proceedings of the Cambridge Philosophical Society 0305-0041 1469-8064 2307.1661110.1017/s0305004125000143 1783293-320 yes E. KUPERWASSER, W. SAMOTIJ, Y. Wigderson, Mathematical Proceedings of the Cambridge Philosophical Society 178 (2025) 293–320. KUPERWASSER E, SAMOTIJ W, Wigderson Y. On the Kohayakawa–Kreuter conjecture. Mathematical Proceedings of the Cambridge Philosophical Society. 2025;178(3):293-320. doi:<a href="https://doi.org/10.1017/s0305004125000143">10.1017/s0305004125000143</a> KUPERWASSER, E., SAMOTIJ, W., & Wigderson, Y. (2025). On the Kohayakawa–Kreuter conjecture. Mathematical Proceedings of the Cambridge Philosophical Society. Cambridge University Press. <a href="https://doi.org/10.1017/s0305004125000143">https://doi.org/10.1017/s0305004125000143</a> KUPERWASSER E, SAMOTIJ W, Wigderson Y. 2025. On the Kohayakawa–Kreuter conjecture. Mathematical Proceedings of the Cambridge Philosophical Society. 178(3), 293–320. KUPERWASSER, EDEN, WOJCIECH SAMOTIJ, and Yuval Wigderson. “On the Kohayakawa–Kreuter Conjecture.” Mathematical Proceedings of the Cambridge Philosophical Society. Cambridge University Press, 2025. <a href="https://doi.org/10.1017/s0305004125000143">https://doi.org/10.1017/s0305004125000143</a>. KUPERWASSER, EDEN, et al. “On the Kohayakawa–Kreuter Conjecture.” Mathematical Proceedings of the Cambridge Philosophical Society, vol. 178, no. 3, Cambridge University Press, 2025, pp. 293–320, doi:<a href="https://doi.org/10.1017/s0305004125000143">10.1017/s0305004125000143</a>. E. KUPERWASSER, W. SAMOTIJ, and Y. Wigderson, “On the Kohayakawa–Kreuter conjecture,” Mathematical Proceedings of the Cambridge Philosophical Society, vol. 178, no. 3. Cambridge University Press, pp. 293–320, 2025. 221682026-06-29T10:55:00Z2026-07-14T08:38:08Z