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
MathSciNet review: 1276825
Full-text PDF

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

$\displaystyle \mathop {\lim \limits_{n \to \infty }} Prob(K(n,N) \to {(G)_r}) =... ... < 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