A Short Proof of the Random Ramsey Theorem. (22nd December 2014)

• Record Type: Journal Article
• Authors: NENADOV, RAJKO; STEGER, ANGELIKA
• Is Part Of: Combinatorics, probability and computing. Volume 25:Number 1(2016:Jan.)
• Page Start: 130
• Page End: 144
• Publication Date: 2014-12-22
• Subjects: Primary 05C80, -- Secondary 05D10; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000832
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : 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.