# Ramsey Properties of Random Graphs and Folkman Numbers

Vojtěch Rödl; Andrzej Ruciński; Mathias Schacht

Discussiones Mathematicae Graph Theory (2017)

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

## Access Full Article

top## Abstract

top## How to cite

topVojtě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 ?

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