## Threshold functions for ramsey properties

### Authors:

- Vojtech Rödl,
- Andrzej Ruciński

### 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) → (G)
_{r}
, in short). We find a graph parameter γ = γ (G) yielding (Equation presented), 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 ≥ 2 and k ≥ 3 there exists C > 0 such that almost all graphs H with n vertices and (Equation presented) edges which are K
_{k+1}
-free, satisfy H → (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 (Equation presented) contain an arithmetic progression of length k in every r-coloring, and show that (Equation presented) is the threshold. © 1995 American Mathematical Society.

- Record ID
- UAM336f029c6add4795b818a324aec9f13f
- Author
- Journal series
- Journal of the American Mathematical Society, ISSN 0894-0347
- Issue year
- 1995
- Vol
- 8
- Pages
- 917-942
- ASJC Classification
- ;
- DOI
- DOI:10.1090/S0894-0347-1995-1276825-6 Opening in a new tab
- Language
- (en) English
- Score (nominal)
- 0
- Score source
- journalList
- Publication indicators
- = 83; = 105; : 1999 = 3.153; : 2006 (2 years) = 2.552 - 2007 (5 years) =2.846

- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM336f029c6add4795b818a324aec9f13f/

- URN
`urn:amu-prod:UAM336f029c6add4795b818a324aec9f13f`

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.