Threshold functions for Ramsey properties

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.