Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-11T22:10:05.039Z Has data issue: false hasContentIssue false
  • English
  • Français

A Short Proof of the Random Ramsey Theorem

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  22 December 2014

RAJKO NENADOV  and
ANGELIKA STEGER
RAJKO NENADOV
Affiliation:
Institute of Theoretical Computer Science, ETH Zurich, 8092 Zurich, Switzerland (e-mail: rnenadov@inf.ethz.ch, steger@inf.ethz.ch)
ANGELIKA STEGER
Affiliation:
Institute of Theoretical Computer Science, ETH Zurich, 8092 Zurich, Switzerland (e-mail: rnenadov@inf.ethz.ch, steger@inf.ethz.ch)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper we give a short proof of the Random Ramsey Theorem of Rödl and Ruciński: for any graph F which contains a cycle and r ≥ 2, there exist constants c, C > 0 such that

$$ \begin{equation*} \Pr[G_{n,p} \rightarrow (F)_r^e] = \begin{cases} 1-o(1) &p\ge Cn^{-1/m_2(F)},\\ o(1) &p\le cn^{-1/m_2(F)}, \end{cases} \end{equation*} $$
where
$$ \begin{equation*} m_2(F) = \max_{J\subseteq F, v_J\ge 2} \frac{e_J-1}{v_J-2}. \end{equation*} $$
 The proof of the 1-statement is based on the recent beautiful hypergraph container theorems by Saxton and Thomason, and Balogh, Morris and Samotij. The proof of the 0-statement is elementary.

MSC classification

Primary: 05C80: Random graphs
Secondary: 05D10: Ramsey theory
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 1: Oberwolfach Special Issue Part 2 , January 2016 , pp. 130 - 144
Copyright
Copyright © Cambridge University Press 2014 

References

[1]Balogh, J., Morris, R. and Samotij, W. (2012) Independent sets in hypergraphs. J. Amer. Math. Soc. arXiv:1204.6530, to appear.Google Scholar
[2]Chen, B., Matsumoto, M., Wang, J. F., Zhang, Z. F. and Zhang, J. X. (1994) A short proof of Nash-Williams' theorem for the arboricity of a graph. Graphs Combin. 10 27–28.CrossRefGoogle Scholar
[3]Conlon, D. and Gowers, T. Combinatorial theorems in sparse random sets. arXiv:1011.4310Google Scholar
[4]Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 17–61.Google Scholar
[5]Friedgut, E., Rödl, V. and Schacht, M. (2010) Ramsey properties of random discrete structures. Random Struct. Alg. 37 407–436.CrossRefGoogle Scholar
[6]Gugelmann, L., Person, Y., Steger, A. and Thomas, H. (2012) A randomized version of Ramsey's theorem. Random Struct. Alg. 41 488–505.CrossRefGoogle Scholar
[7]Łuczak, T., Ruciński, A. and Voigt, B. (1992) Ramsey properties of random graphs. J. Combin. Theory Ser. B 56 55–68.CrossRefGoogle Scholar
[8]Marciniszyn, M., Skokan, J., Spöhel, R. and Steger, A. (2009) Asymmetric Ramsey properties of random graphs involving cliques. Random Struct. Alg. 34 419–453.CrossRefGoogle Scholar
[9]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.Google Scholar
[10]Rödl, V. and Ruciński, A. (1994) Random graphs with monochromatic triangles in every edge coloring. Random Struct. Alg. 5 253–270.CrossRefGoogle Scholar
[11]Rödl, V. and Ruciński, A. (1995) Threshold functions for Ramsey properties. J. Amer. Math. Soc. 8 917–942.CrossRefGoogle Scholar
[12]Saxton, D. and Thomason, A. (2012) Hypergraph containers. arXiv:1204.6595Google Scholar