Hostname: page-component-745bb68f8f-l4dxg Total loading time: 0 Render date: 2025-01-11T03:32:12.476Z Has data issue: false hasContentIssue false
  • English
  • Français

Towards the Kohayakawa–Kreuter conjecture on asymmetric Ramsey properties

Part of: Extremal combinatorics Graph theory

Published online by Cambridge University Press:  24 June 2020

Frank Mousset ,
Rajko Nenadov  and
Wojciech Samotij
Frank Mousset*
Affiliation:
School of Mathematical Sciences, Tel Aviv University, Tel Aviv6997801, Israel
Rajko Nenadov
Affiliation:
Department of Computer Science, ETH Zurich, 8092 Zürich, Switzerland
Wojciech Samotij
Affiliation:
School of Mathematical Sciences, Tel Aviv University, Tel Aviv6997801, Israel
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

For fixed graphs F1,…,Fr, we prove an upper bound on the threshold function for the property that G(n, p) → (F1,…,Fr). This establishes the 1-statement of a conjecture of Kohayakawa and Kreuter.

MSC classification

Primary: 05D10: Ramsey theory
Secondary: 05C80: Random graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 6 , November 2020 , pp. 943 - 955
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press

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

Footnotes

†

Research supported in part by the Israel Science Foundation (ISF) grants 1147/14 (FM and WS) and 1028/16 (FM) and ERC Starting Grant 633509 (FM).

‡

A first draft of this paper was produced at the workshop of the research group of Angelika Steger in Buchboden in July 2018.

§

Part of the work was done while the second author was visiting Tel Aviv University.

References

Balogh, J., Morris, R. and Samotij, W. (2015) Independent sets in hypergraphs. J. Amer. Math. Soc. 28 669–709.CrossRefGoogle Scholar
Balogh, J., Morris, R. and Samotij, W. (2018) The method of hypergraph containers. In Proceedings of the International Congress of Mathematicians (Rio de Janeiro 2018), Vol. IV, Invited Lectures, pp. 3059–3092, World Scientific.CrossRefGoogle Scholar
Conlon, D., Gowers, W. T., Samotij, W. and Schacht, M. (2014) On the KŁR conjecture in random graphs. Israel J. Math. 203 535–580.CrossRefGoogle Scholar
Frankl, P. and Rödl, V. (1986) Large triangle-free subgraphs in graphs without K 4. Graphs Combin. 2 135–144.CrossRefGoogle Scholar
Friedgut, E. and Krivelevich, M. (2000) Sharp thresholds for certain Ramsey properties of random graphs. Random Struct. Algorithms 17 1–19.3.0.CO;2-4>CrossRefGoogle Scholar
Friedgut, E., Rödl, V., Ruciński, A. and Tetali, P. (2006) A Sharp Threshold for Random Graphs with a Monochromatic Triangle in Every Edge Coloring, Vol. 179, no. 845 of Memoirs of the American Mathematical Society, AMS.CrossRefGoogle Scholar
Gugelmann, L., Nenadov, R., Person, Y., Škorić, N., Steger, A. and Thomas, H. (2017) Symmetric and asymmetric Ramsey properties in random hypergraphs. Forum Math. Sigma 5 e28, 47.CrossRefGoogle Scholar
Hancock, R., Staden, K. and Treglown, A. (2019) Independent sets in hypergraphs and Ramsey properties of graphs and the integers. SIAM J. Discrete Math. 33 153–188.CrossRefGoogle Scholar
Janson, S. (1998) New versions of Suen’s correlation inequality. Random Struct. Algorithms 13 467–483.3.0.CO;2-W>CrossRefGoogle Scholar
Janson, S., Łuczak, T. and Ruciński, A. (1990) An exponential bound for the probability of nonexistence of a specified subgraph in a random graph. In Random Graphs ’87 (Poznań, 1987), pp. 73–87, Wiley.Google Scholar
Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience.CrossRefGoogle Scholar
Kohayakawa, Y. and Kreuter, B. (1997) Threshold functions for asymmetric Ramsey properties involving cycles. Random Struct. Algorithms 11 245–276.3.0.CO;2-0>CrossRefGoogle Scholar
Kohayakawa, Y., Łuczak, T. and Rödl, V. (1997) On K 4-free subgraphs of random graphs. Combinatorica 17 173–213.CrossRefGoogle Scholar
Kohayakawa, Y., Schacht, M. and Spöhel, R. (2014) Upper bounds on probability thresholds for asymmetric Ramsey properties. Random Struct. Algorithms 44 1–28.CrossRefGoogle Scholar
Łuczak, T., Ruciński, A. and Voigt, B. (1992) Ramsey properties of random graphs. J. Combin. Theory Ser. B 56 55–68.CrossRefGoogle Scholar
Marciniszyn, M., Skokan, J., Spöhel, R. and Steger, A. (2009) Asymmetric Ramsey properties of random graphs involving cliques. Random Struct. Algorithms 34 419–453.CrossRefGoogle Scholar
Nenadov, R., Person, Y., Škorić, N. and Steger, A. (2017) An algorithmic framework for obtaining lower bounds for random Ramsey problems. J. Combin. Theory Ser. B 124 1–38.CrossRefGoogle Scholar
Nenadov, R. and Steger, A. (2016) A short proof of the random Ramsey theorem. Combin. Probab. Comput. 25 130–144.CrossRefGoogle Scholar
Rödl, V. and Ruciński, A. (1993) Lower bounds on probability thresholds for Ramsey properties. In Combinatorics: Paul Erdös is Eighty, Vol. 1, Bolyai Society Mathematical Studies, pp. 317–346, János Bolyai Mathematical Society.Google Scholar
Rödl, V. and Ruciński, A. (1994) Random graphs with monochromatic triangles in every edge coloring. Random Struct. Algorithms 5 253–270.CrossRefGoogle Scholar
Rödl, V. and Ruciński, A. (1995) Threshold functions for Ramsey properties. J. Amer. Math. Soc. 8 917–942.CrossRefGoogle Scholar
Ruciński, A. and Vince, A. (1985) Balanced graphs and the problem of subgraphs of random graphs. Congr. Numer. 49 181–190.Google Scholar
Saxton, D. and Thomason, A. (2015) Hypergraph containers. Invent. Math. 201 925–992.CrossRefGoogle Scholar
Schacht, M. and Schulenburg, F. (2018) Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs. Random Struct. Algorithms 52 3–40.CrossRefGoogle Scholar