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/

[1] J. Balogh, R. Morris and W. Samotij, Independent sets in hypergraphs, J. Amer. Math. Soc. 28 (2015) 669–709. doi:10.1090/S0894-0347-2014-00816-X

[2] D. Conlon and T. Gowers, An upper bound for Folkman numbers, preprint.

[3] E. Friedgut, V. Rödl and M. Schacht, Ramsey properties of random discrete structures, Random Structures Algorithms 37 (2010) 407–436. doi:10.1002/rsa.20352

[4] S. Janson, T. Luczak and A. Ruciński, Random Graphs (John Wiley and Sons, New York, 2000). doi:10.1002/9781118032718

[5] R. Nenadov and A. Steger, A short proof of the random Ramsey theorem, Combin. Probab. Comput. 25 (2016) 130–144. doi:10.1017/S0963548314000832

[6] V. Rödl and A. Ruciński, Threshold functions for Ramsey properties, J. Amer. Math. Soc. 84 (1995) 917–942. doi:10.2307/2152833

[7] V. Rödl, A. Ruciński and M. Schacht, Ramsey properties of random k-partite, k-uniform hypergraphs, SIAM J. Discrete Math. 21 (2007) 442–460. doi:10.1137/060657492

[8] V. Rödl, A. Ruciński and M. Schacht, An exponential-type upper bound for Folkman numbers, Combinatorica, in press. doi:10.1007/s00493-015-3298-1

[9] D. Saxton and A. Thomason, Hypergraph containers, Invent. Math. 201 (2015) 925–992. doi:10.1007/s00222-014-0562-8

[10] E. Szemerédi, Regular partitions of graphs, in: Problèmes Combinatoires et Théorie des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS 260 (CNRS, Paris, 1978) 399–401.