Threshold functions for Ramsey properties

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

Journal of the American Mathematical Society, Tome 08 (1995) no. 4, pp. 917-942

Résumé

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)$ be the random graph chosen uniformly from among all graphs with $n$ vertices and $N$ edges. For a fixed graph $G$ and an integer $r$ we address the question what is the minimum $N = N(G,r,n)$ such that the random graph $K(n,N)$ contains, almost surely, a monochromatic copy of $G$ in every $r$-coloring of its edges ( $K(n,N) \to {(G)_r}$, in short). We find a graph parameter $\gamma = \gamma (G)$ yielding \[ \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 > 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 \geq 2$ and $k \geq 3$ there exists $C > 0$ such that almost all graphs $H$ with $n$ vertices and $C{n^{\frac {{2k}}{{k + 1}}}}$ edges which are ${K_{k + 1}}$-free, satisfy $H \to {({K_k})_r}$. We also apply our method to the problem of finding the smallest $N = N(k,r,n)$ guaranteeing that almost all sequences $1 \leq {a_1} {a_2} \cdots {a_N} \leq n$ contain an arithmetic progression of length $k$ in every $r$-coloring, and show that $N = \Theta ({n^{\frac {{k - 2}}{{k - 1}}}})$ is the threshold.

Détail

DOI : 10.1090/S0894-0347-1995-1276825-6

Bibliographie

[1] Bollobás, Béla Threshold functions for small subgraphs Math. Proc. Cambridge Philos. Soc. 1981 197 206

[2] Bollobás, Béla Random graphs 1985

[3] Bollobás, B., Thomason, A. Threshold functions Combinatorica 1987 35 38

[4] Folkman, Jon Graphs with monochromatic complete subgraphs in every edge coloring SIAM J. Appl. Math. 1970 19 24

[5] Frankl, P., Rödl, V. Large triangle-free subgraphs in graphs without 𝐾₄ Graphs Combin. 1986 135 144

[6] Graham, R. L. On edgewise 2-colored graphs with monochromatic triangles and containing no complete hexagon J. Combinatorial Theory 1968 300

[7] Graham, R. L. Recent developments in Ramsey theory 1984 1555 1567

[8] Graham, R. L., Nešetřil, J. Large minimal sets which force long arithmetic progressions J. Combin. Theory Ser. A 1986 270 276

[9] Graham, Ronald L., Rothschild, Bruce L., Spencer, Joel H. Ramsey theory 1990

[10] Irving, Robert W. On a bound of Graham and Spencer for a graph-coloring constant J. Combinatorial Theory Ser. B 1973 200 203

[11] Janson, Svante Poisson approximation for large deviations Random Structures Algorithms 1990 221 229

[12] Łuczak, Tomasz, Ruciński, Andrzej, Voigt, Bernd Ramsey properties of random graphs J. Combin. Theory Ser. B 1992 55 68

[13] Ne Et Il, Jaroslav, Rödl, Vojtěch The Ramsey property for graphs with forbidden complete subgraphs J. Combinatorial Theory Ser. B 1976 243 249

[14] Ne Et Il, Jaroslav, Rödl, Vojtěch Van der Waerden theorem for sequences of integers not containing an arithmetic progression of 𝑘 terms Comment. Math. Univ. Carolinae 1976 675 681

[15] Ne Et Il, Jaroslav, Rödl, Vojtěch The partite construction and Ramsey set systems Discrete Math. 1989 327 334

[16] Ne Et Il, Jaroslav, Rödl, Vojtěch Partite construction and Ramsey space systems 1990 98 112

[17] Rödl, Vojtěch On Ramsey families of sets Graphs Combin. 1990 187 195

[18] Rödl, Vojtěch, Ruciński, Andrzej Random graphs with monochromatic triangles in every edge coloring Random Structures Algorithms 1994 253 270

[19] Rödl, V., Ruciński, A. Lower bounds on probability thresholds for Ramsey properties 1993 317 346

[20] Ruciński, Andrzej Small subgraphs of random graphs—a survey 1990 283 303

[21] Spencer, Joel Restricted Ramsey configurations J. Combinatorial Theory Ser. A 1975 278 286

[22] Szemerédi, E. On sets of integers containing no 𝑘 elements in arithmetic progression Acta Arith. 1975 199 245

[23] Varnavides, P. On certain sets of positive density J. London Math. Soc. 1959 358 360