Portal de Periódicos da CAPES

Threshold functions for Ramsey properties

1995; American Mathematical Society; Volume: 8; Issue: 4 Linguagem: Inglês

10.1090/s0894-0347-1995-1276825-6

1088-6834

Vojtěch Rödl, Andrzej Ruciński,

Advanced Graph Theory Research

Probabilistic methods have been used to approach many problems of Ramsey theory. In this paper we study Ramsey type questions from the point of view of random structures. Let K ( n , N ) K(n,N) be the random graph chosen uniformly from among all graphs with n n vertices and N N edges. For a fixed graph G G and an integer r r we address the question what is the minimum N = N ( G , r , n ) N = N(G,r,n) such that the random graph K ( n , N ) K(n,N) contains, almost surely, a monochromatic copy of G G in every r r -coloring of its edges ( K ( n , N ) → ( G ) r K(n,N) \to {(G)_r} , in short). We find a graph parameter γ = γ ( G ) \gamma = \gamma (G) yielding \[ lim n → ∞ Prob ⁡ ( K ( n , N ) → ( G ) r ) = { 0 if N > c n y , 1 if N > C n y , \lim \limits _{n \to \infty } \operatorname {Prob}(K(n,N) \to {(G)_r}) = \left \{ {\begin {array}{*{20}{c}} {0\quad {\text {if }}\;N > c{n^y},} \\ {1\quad {\text {if}}\;N > C{n^y},} \\ \end {array} } \right .\quad \] for some c c , C > 0 C > 0 . We use this to derive a number of consequences that deal with the existence of sparse Ramsey graphs. For example we show that for all r ≥ 2 r \geq 2 and k ≥ 3 k \geq 3 there exists C > 0 C > 0 such that almost all graphs H H with n n vertices and C n 2 k k + 1 C{n^{\frac {{2k}}{{k + 1}}}} edges which are K k + 1 {K_{k + 1}} -free, satisfy H → ( K k ) r H \to {({K_k})_r} . We also apply our method to the problem of finding the smallest N = N ( k , r , n ) N = N(k,r,n) guaranteeing that almost all sequences 1 ≤ a 1 > a 2 > ⋯ > a N ≤ n 1 \leq {a_1} > {a_2} > \cdots > {a_N} \leq n contain an arithmetic progression of length k k in every r r -coloring, and show that N = Θ ( n k − 2 k − 1 ) N = \Theta ({n^{\frac {{k - 2}}{{k - 1}}}}) is the threshold.