Hostname: page-component-669899f699-qzcqf Total loading time: 0 Render date: 2025-04-30T05:46:43.413Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Kohayakawa–Kreuter conjecture

Part of: Extremal combinatorics Graph theory

Published online by Cambridge University Press:  28 April 2025

EDEN KUPERWASSER ,
WOJCIECH SAMOTIJ  and
YUVAL WIGDERSON
EDEN KUPERWASSER
Affiliation:
School of Mathematical Sciences, Tel Aviv University, Tel Aviv 6997801, Israel. e-mails: [email protected], [email protected]
WOJCIECH SAMOTIJ
Affiliation:
Institute for Theoretical Studies, ETH Zürich, Zürich, Switzerland. e-mail: [email protected]
YUVAL WIGDERSON
Affiliation:
Institute for Theoretical Studies, ETH Zürich, Zürich, Switzerland. e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Let us say that a graph $G$ is Ramsey for a tuple $(H_1,\ldots,H_r)$ of graphs if every r-colouring of the edges of G contains a monochromatic copy of $H_i$ in colour i, for some $i \in [\![{r}]\!]$. A famous conjecture of Kohayakawa and Kreuter, extending seminal work of Rödl and Ruciński, predicts the threshold at which the binomial random graph $G_{n,p}$ becomes Ramsey for $(H_1,\ldots,H_r)$ 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 $H_1,\ldots,H_r$ by finite families $\mathcal{H}_1,\ldots,\mathcal{H}_r$. 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.

MSC classification

Primary: 05C80: Random graphs 05C55: Generalized Ramsey theory 05D10: Ramsey theory
Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , First View , pp. 1 - 28
Copyright
© The Author(s), 2025. Published by Cambridge University Press on behalf of Cambridge Philosophical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

Footnotes

†

Supported by ERC Consolidator Grant 101044123 (RandomHypGra), by Israel Science Foundation Grant 2110/22, and by NSF-BSF Grant 2019679.

‡

Supported by ERC Consolidator Grants 863438 (LocalGlobal) and 101044123 (RandomHypGra), by Israel Science Foundation Grant 2110/22, and by NSF-BSF Grant 2019679.

References

Balogh, J., Morris, R. and Samotij, W.. Independent sets in hypergraphs. J. Amer. Math. Soc. 28 (2015), 669–709.CrossRefGoogle Scholar
Bowtell, C., Hancock, R. and Hyde, J.. Proof of the Kohayakawa–Kreuter conjecture for the majority of cases. Preprint arXiv:2307.16760 (2023).CrossRefGoogle Scholar
Conlon, D., Fox, J. and Sudakov, B.. Recent developments in graph Ramsey theory. In Surveys in Combinatorics 2015. London Math. Soc. Lecture Note Ser., vol. 424 (Cambridge University Press, Cambridge, 2015), 49–118.Google Scholar
Conlon, D. and Gowers, W. T.. Combinatorial theorems in sparse random sets. Ann. of Math. (2) 184 (2016), 367–454.CrossRefGoogle Scholar
Edmonds, J.. Minimum partition of a matroid into independent subsets. J. Res. Nat. Bur. Standards Sect. B 69B (1965), 67–72.CrossRefGoogle Scholar
Frankl, P. and Rödl, V.. Large triangle-free subgraphs in graphs without $K_4$ , Graphs Combin. 2 (1986), 135–144.CrossRefGoogle Scholar
Friedgut, E. and Krivelevich, M.. Sharp thresholds for certain Ramsey properties of random graphs. Random Structures Algorithms 17 (2000), 1–19.3.0.CO;2-4>CrossRefGoogle Scholar
Friedgut, E., Rödl, V. and Schacht, M.. Ramsey properties of random discrete structures. Random Structures Algorithms 37 (2010), 407–436.CrossRefGoogle Scholar
Gugelmann, L., Nenadov, R., Person, Y., Škorić, N., Steger, A. and Thomas, H.. Symmetric and asymmetric Ramsey properties in random hypergraphs. Forum Math. Sigma 5 (2017), paper no. e28, 47 pages.CrossRefGoogle Scholar
Hakimi, S. L.. On the degrees of the vertices of a directed graph. J. Franklin Inst. 279 (1965), 290–308.CrossRefGoogle Scholar
Hancock, R., Staden, K. and Treglown, A.. Independent sets in hypergraphs and Ramsey properties of graphs and the integers. SIAM J. Discrete Math. 33 (2019), 153–188.CrossRefGoogle Scholar
Harel, M., Mousset, F. and Samotij, W.. Upper tails via high moments and entropic stability. Duke Math. J. 171 (2022), 2089–2192.CrossRefGoogle Scholar
Hyde, J.. Towards the 0-statement of the Kohayakawa--Kreuter conjecture. Combin. Probab. Comput. 32 (2023), 225–268.Google Scholar
Janson, S., Łuczak, T. and Ruciński, A.. Random graphs . Wiley-Interscience Series in Discrete Mathematics and Optimization. (Wiley-Interscience, New York, 2000).Google Scholar
Kohayakawa, Y. and Kreuter, B.. Threshold functions for asymmetric Ramsey properties involving cycles. Random Structures Algorithms 11 (1997), 245–276.3.0.CO;2-0>CrossRefGoogle Scholar
Kohayakawa, Y., Schacht, M. and Spöhel, R.. Upper bounds on probability thresholds for asymmetric Ramsey properties. Random Structures Algorithms 44 (2014), 1–28.CrossRefGoogle Scholar
Kuperwasser, E. and Samotij, W.. The list-Ramsey threshold for families of graphs. Combin. Probab. Comput. 33 (2024), 829–851.CrossRefGoogle Scholar
Liebenau, A., Mattos, L., Mendonça, W. and Skokan, J.. Asymmetric Ramsey properties of random graphs involving cliques and cycles. Random Structures Algorithms 62 (2023), 1035–1055.CrossRefGoogle Scholar
Marciniszyn, M., Skokan, J., Spöhel, R. and Steger, A.. Asymmetric Ramsey properties of random graphs involving cliques. Random Structures Algorithms 34 (2009), 419–453.CrossRefGoogle Scholar
Mousset, F., Nenadov, R. and Samotij, W.. Towards the Kohayakawa--Kreuter conjecture on asymmetric Ramsey properties. Combin. Probab. Comput. 29 (2020), 943–955.CrossRefGoogle Scholar
Nash-Williams, C. S. J. A.. Decomposition of finite graphs into forests. J. London Math. Soc. 39 (1964), 12.CrossRefGoogle Scholar
Nenadov, R. and Steger, A.. A short proof of the random Ramsey theorem. Combin. Probab. Comput. 25 (2016), 130–144.CrossRefGoogle Scholar
Oxley, J.. Matroid Theory, Oxf. Grad. Texts Math., vol. 21, 2nd ed. (Oxford University Press, Oxford, 2011).Google Scholar
Ramsey, F. P.. On a Problem of Formal Logic. Proc. London Math. Soc. (2) 30 (1929), 264–286.Google Scholar
Rödl, V. and Ruciński, A.. Lower bounds on probability thresholds for Ramsey properties. In Combinatorics, Paul Erdős is eighty, Vol. 1. Bolyai Soc. Math. Stud. (János Bolyai Math. Soc., Budapest, 1993), 317–346.Google Scholar
Rödl, V. and Ruciński, A.. Random graphs with monochromatic triangles in every edge colouring. Random Structures Algorithms 5 (1994), 253–270.CrossRefGoogle Scholar
Rödl, V. and Ruciński, A.. Threshold functions for Ramsey properties. J. Amer. Math. Soc. 8 (1995), 917–942.CrossRefGoogle Scholar
Saxton, D. and Thomason, A.. Hypergraph containers. Invent. Math. 201 (2015), 925–992.CrossRefGoogle Scholar
Schacht, M.. Extremal results for random discrete structures, Ann. of Math. (2) 184 (2016), 333–365.CrossRefGoogle Scholar
Turán, P.. Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48 (1941), 436–452.Google Scholar
Łuczak, T., Ruciński, A. and Voigt, B.. Ramsey properties of random graphs. J. Combin. Theory Ser. B 56 (1992), 55–68.CrossRefGoogle Scholar