Ramsey Properties of Random Graphs and Folkman Numbers

• Autorzy: Vojtěch Rödl , Andrzej Ruciński , Mathias Schacht
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Ramsey property; random graph; Folkman number

Kategorie tematyczne

• 05C80: Random graphs
• 05C55: Generalized Ramsey theory

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 3
• Strony: 755-776

Daty

wydano

2017-08-01

otrzymano

2015-09-11

poprawiono

2016-06-28

zaakceptowano

2016-06-29

online

2017-07-06

Twórcy

autor

Vojtěch Rödl

• , ,

autor

Andrzej Ruciński

• , ,

autor

Mathias Schacht

• , ,

Identyfikatory

DOI

10.7151/dmgt.1971