Ramsey Properties of Random Graphs and Folkman Numbers

• Volume: 37, Issue: 3, page 755-776
• ISSN: 2083-5892

top

Abstract

top
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.

How to cite

top

Vojtěch Rödl, Andrzej Ruciński, and Mathias Schacht. "Ramsey Properties of Random Graphs and Folkman Numbers." Discussiones Mathematicae Graph Theory 37.3 (2017): 755-776. <http://eudml.org/doc/288531>.

@article{VojtěchRödl2017,
abstract = {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.},
author = {Vojtěch Rödl, Andrzej Ruciński, Mathias Schacht},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Ramsey property; random graph; Folkman number},
language = {eng},
number = {3},
pages = {755-776},
title = {Ramsey Properties of Random Graphs and Folkman Numbers},
url = {http://eudml.org/doc/288531},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Vojtěch Rödl
AU - Andrzej Ruciński
AU - Mathias Schacht
TI - Ramsey Properties of Random Graphs and Folkman Numbers
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 3
SP - 755
EP - 776
AB - 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.
LA - eng
KW - Ramsey property; random graph; Folkman number
UR - http://eudml.org/doc/288531
ER -

NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.