Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Threshold functions for Ramsey properties
HTML articles powered by AMS MathViewer

by Vojtěch Rödl and Andrzej Ruciński PDF
J. Amer. Math. Soc. 8 (1995), 917-942 Request permission

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
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
  • © Copyright 1995 American Mathematical Society
  • 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