- Tytuł:
- Ramsey Properties of Random Graphs and Folkman Numbers
- Autorzy:
-
Rödl, Vojtěch
Ruciński, Andrzej
Schacht, Mathias - Powiązania:
- https://bibliotekanauki.pl/articles/31341650.pdf
- Data publikacji:
- 2017-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
Ramsey property
random graph
Folkman number - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2017, 37, 3; 755-776
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł