Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

Threshold functions for Ramsey properties


Authors: Vojtěch Rödl and Andrzej Ruciński
Journal: J. Amer. Math. Soc. 8 (1995), 917-942
MSC: Primary 05C55; Secondary 05C80, 05D10
DOI: https://doi.org/10.1090/S0894-0347-1995-1276825-6
MathSciNet review: 1276825
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC: 05C55, 05C80, 05D10

Retrieve articles in all journals with MSC: 05C55, 05C80, 05D10


Additional Information

Article copyright: © Copyright 1995 American Mathematical Society