PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2017 | 37 | 3 | 755-776
Tytuł artykułu

Ramsey Properties of Random Graphs and Folkman Numbers

Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
37
Numer
3
Strony
755-776
Opis fizyczny
Daty
wydano
2017-08-01
otrzymano
2015-09-11
poprawiono
2016-06-28
zaakceptowano
2016-06-29
online
2017-07-06
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1971
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.