For two graphs, G and F, and an integer r ≥ 2 we write G → (F)r if every r-coloring of the edges of G results in a monochromatic copy of F. In 1995, the first two authors established a threshold edge probability for the Ramsey property G(n, p) → (F)r, where G(n, p) is a random graph obtained by including each edge of the complete graph on n vertices, independently, with probability p. The original proof was based on the regularity lemma of Szemerédi and this led to tower-type dependencies between the involved parameters. Here, for r = 2, we provide a self-contained proof of a quantitative version of the Ramsey threshold theorem with only double exponential dependencies between the constants. As a corollary we obtain a double exponential upper bound on the 2-color Folkman numbers. By a different proof technique, a similar result was obtained independently by Conlon and Gowers.
@article{bwmeta1.element.doi-10_7151_dmgt_1971,
author = {Vojt\v ech R\"odl and Andrzej Ruci\'nski and Mathias Schacht},
title = {Ramsey Properties of Random Graphs and Folkman Numbers},
journal = {Discussiones Mathematicae Graph Theory},
volume = {37},
year = {2017},
pages = {755-776},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1971}
}
Vojtěch Rödl; Andrzej Ruciński; Mathias Schacht. Ramsey Properties of Random Graphs and Folkman Numbers. Discussiones Mathematicae Graph Theory, Tome 37 (2017) pp. 755-776. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1971/