Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-24T12:28:48.534Z Has data issue: false hasContentIssue false
  • English
  • Français

Ramsey properties of randomly perturbed graphs: cliques and cycles

Published online by Cambridge University Press:  30 June 2020

Shagnik Das  and
Andrew Treglown
Shagnik Das
Affiliation:
Institute of Mathematics, Freie Universität Berlin, Arnimallee 3, 14195Berlin, Germany
Andrew Treglown*
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, BirminghamB15 2TT, UK
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Given graphs H1, H2, a graph G is (H1, H2) -Ramsey if, for every colouring of the edges of G with red and blue, there is a red copy of H1 or a blue copy of H2. In this paper we investigate Ramsey questions in the setting of randomly perturbed graphs. This is a random graph model introduced by Bohman, Frieze and Martin [8] in which one starts with a dense graph and then adds a given number of random edges to it. The study of Ramsey properties of randomly perturbed graphs was initiated by Krivelevich, Sudakov and Tetali [30] in 2006; they determined how many random edges must be added to a dense graph to ensure the resulting graph is with high probability (K3, Kt) -Ramsey (for t ≽ 3). They also raised the question of generalizing this result to pairs of graphs other than (K3, Kt). We make significant progress on this question, giving a precise solution in the case when H1 = Ks and H2 = Kt where s, t ≽ 5. Although we again show that one requires polynomially fewer edges than in the purely random graph, our result shows that the problem in this case is quite different to the (K3, Kt) -Ramsey question. Moreover, we give bounds for the corresponding (K4, Kt) -Ramsey question; together with a construction of Powierski [37] this resolves the (K4, K4) -Ramsey problem.

We also give a precise solution to the analogous question in the case when both H1 = Cs and H2 = Ct are cycles. Additionally we consider the corresponding multicolour problem. Our final result gives another generalization of the Krivelevich, Sudakov and Tetali [30] result. Specifically, we determine how many random edges must be added to a dense graph to ensure the resulting graph is with high probability (Cs, Kt) -Ramsey (for odd s ≽ 5 and t ≽ 4).

To prove our results we combine a mixture of approaches, employing the container method, the regularity method as well as dependent random choice, and apply robust extensions of recent asymmetric random Ramsey results.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 6 , November 2020 , pp. 830 - 867
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 by GIF grant G-1347-304.6/2016.

‡

Research supported by EPSRC grant EP/M016641/1.

References

Aigner-Horev, E. and Person, Y. (2019) Monochromatic Schur triples in randomly perturbed dense sets of integers. SIAM J. Discrete Math. 33 2175–2180.CrossRefGoogle Scholar
Alon, N. and Spencer, J. (2015) The Probabilistic Method, Wiley.Google Scholar
Balogh, J., Morris, R. and Samotij, W. (2015) Independent sets in hypergraphs. J. Amer. Math. Soc. 28 669–709.CrossRefGoogle Scholar
Balogh, J., Treglown, A. and Wagner, A. Z. (2019) Tilings in randomly perturbed dense graphs. Combin. Probab. Comput. 28 159–176.CrossRefGoogle Scholar
Bedenknecht, W., Han, J., Kohayakawa, Y. and Mota, G. O. (2019) Powers of tight Hamilton cycles in randomly perturbed hypergraphs. Random Struct. Algorithms 55 795–807.CrossRefGoogle Scholar
Bennett, P., Dudek, A. and Frieze, A. (2017) Adding random edges to create the square of a Hamilton cycle. arXiv:1710.02716Google Scholar
Bohman, T., Frieze, A., Krivelevich, M. and Martin, R. (2004) Adding random edges to dense graphs. Random Struct. Algorithms 24 105–117.CrossRefGoogle Scholar
Bohman, T., Frieze, A. and Martin, R. (2003) How many edges make a dense graph Hamiltonian? Random Struct. Algorithms 22 33–42.CrossRefGoogle Scholar
Böttcher, J., Han, J., Kohayakawa, Y., Montgomery, R., Parczyk, O. and Person, Y. (2019) Universality for bounded degree spanning trees in randomly perturbed graphs. Random Struct. Algorithms 55 854–864.CrossRefGoogle Scholar
Böttcher, J., Montgomery, R., Parczyk, O. and Person, Y. (2020) Embedding spanning bounded degree graphs in randomly perturbed graphs. Mathematika 66 422–447.CrossRefGoogle Scholar
Chung, F. (1997) Open problems of Paul Erdős in graph theory. J. Graph Theory 25 3–36.3.0.CO;2-R>CrossRefGoogle Scholar
Conlon, D. (2009) A new upper bound for diagonal Ramsey numbers. Ann. of Math. 170 941–960.CrossRefGoogle Scholar
Conlon, D. and Gowers, W. T. (2016) Combinatorial theorems in sparse random sets. Ann. Math. 84 367–454.CrossRefGoogle Scholar
Day, A. N. and Johnson, J. R. (2017) Multicolour Ramsey numbers of odd cycles. J. Combin. Theory Ser. B 124 56–63.CrossRefGoogle Scholar
Dudek, A., Reiher, C., Ruciński, A. and Schacht, M. (2020) Powers of Hamiltonian cycles in randomly augmented graphs. Random Struct. Algorithms 56 122–141.CrossRefGoogle Scholar
Erdős, P. and Graham, R. L. (1973) On partition theorems for finite graphs. Colloq. Math. Soc. János Bolyai. 10 515–527.Google Scholar
Erdős, P. and Stone, A. H. (1946) On the structure of linear graphs. Bull. Amer. Math. Soc. 52 1087–1091.CrossRefGoogle Scholar
Fox, J. and Sudakov, B. (2011) Dependent random choice. Random Struct. Algorithms 38 68–99.CrossRefGoogle Scholar
Friedgut, E., Rödl, V. and Schacht, M. (2010) Ramsey properties of random discrete structures. Random Struct. Algorithms 37 407–436.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.CrossRefGoogle Scholar
Han, J. and Zhao, Y. Hamiltonicity in randomly perturbed hypergraphs. J. Combin. Theory Ser. B, to appear.Google 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., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley.CrossRefGoogle Scholar
Joos, F. and Kim, J. (2020) Spanning trees in randomly perturbed graphs. Random Struct. Algorithms 56 169–219.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
Komlós, J. and Simonovits, M. (1996) Szemerédi’s Regularity Lemma and its applications in graph theory. In Combinatorics: Paul Erdös is Eighty, Vol. 2 (Miklós, D., Sós, V. T. and Szőnyi, T. eds.), pp. 295–352, János Bolyai Mathematical Society.Google Scholar
Kreuter, B. (1996) Threshold functions for asymmetric Ramsey properties with respect to vertex colorings. Random Struct. Algorithms 9 335–348.3.0.CO;2-Y>CrossRefGoogle Scholar
Krivelevich, M., Kwan, M. and Sudakov, B. (2016) Cycles and matchings in randomly perturbed digraphs and hypergraphs. Combin. Probab. Comput. 25 909–927.CrossRefGoogle Scholar
Krivelevich, M., Kwan, M. and Sudakov, B. (2017) Bounded-degree spanning trees in randomly perturbed graphs. SIAM J. Discrete Math. 31 155–171.CrossRefGoogle Scholar
Krivelevich, M., Sudakov, B. and Tetali, P. (2006) On smoothed analysis in dense graphs and formulas. Random Struct. Algorithms 29 180–193.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
McDowell, A. and Mycroft, R. (2018) Hamilton l-cycles in randomly perturbed hypergraphs. Electron. J. Combin. 25 P4.36.CrossRefGoogle Scholar
Mousset, F., Nenadov, R. and Samotij, W. (2018) Towards the Kohayakawa–Kreuter conjecture on asymmetric Ramsey properties. Comb. Probab. Comput. arXiv:1808.05070Google Scholar
Nenadov, R. and Steger, A. (2016) A short proof of the random Ramsey theorem. Combin. Probab. Comput. 25 130–144.CrossRefGoogle Scholar
Nenadov, R. and Trujić, M. (2018) Sprinkling a few random edges doubles the power. arXiv:1811.09209Google Scholar
Powierski, E. (2019) Ramsey properties of randomly perturbed dense graphs. arXiv:1902.02197Google 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 (Miklós, D., Sós, V. T. and Szőnyi, T., eds), 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
Saxton, D. and Thomason, A. (2015) Hypergraph containers. Inventio Math. 201 925–992.CrossRefGoogle Scholar
Spencer, J. H. (1975) Ramsey’s theorem: a new lower bound. J. Combin. Theory Ser. A 18 108–115.CrossRefGoogle Scholar
Szemerédi, E. (1976) Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes, Vol. 260 of Colloques Internationaux CNRS, pp. 399–401.Google Scholar
Turán, P. (1941) On an extremal problem in graph theory (in Hungarian). Math. Fiz. Lapok 48 436–452.Google Scholar