Geodesic
Ramsey Properties of Random Graphs and Folkman Numbers
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 755-776

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: Ramsey property, random graph, Folkman number 
@article{DMGT_2017_37_3_a17,
     author = {R\"odl, Vojt\v{e}ch and Ruci\'nski, Andrzej and Schacht, Mathias},
     title = {Ramsey {Properties} of {Random} {Graphs} and {Folkman} {Numbers}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {755--776},
     publisher = {mathdoc},
     volume = {37},
     number = {3},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a17/}
}
TY  - JOUR
AU  - Rödl, Vojtěch
AU  - Ruciński, Andrzej
AU  - Schacht, Mathias
TI  - Ramsey Properties of Random Graphs and Folkman Numbers
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 755
EP  - 776
VL  - 37
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a17/
LA  - en
ID  - DMGT_2017_37_3_a17
ER  - 
%0 Journal Article
%A Rödl, Vojtěch
%A Ruciński, Andrzej
%A Schacht, Mathias
%T Ramsey Properties of Random Graphs and Folkman Numbers
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 755-776
%V 37
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a17/
%G en
%F DMGT_2017_37_3_a17
Rödl, Vojtěch; Ruciński, Andrzej; Schacht, Mathias. Ramsey Properties of Random Graphs and Folkman Numbers. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 755-776. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a17/