Ramsey Properties of Random Graphs and Folkman Numbers
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 incl...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2017-08-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1971 |
| _version_ | 1797718009225150464 |
|---|---|
| author | Rödl Vojtěch Ruciński Andrzej Schacht Mathias |
| author_facet | Rödl Vojtěch Ruciński Andrzej Schacht Mathias |
| author_sort | Rödl Vojtěch |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T08:44:44Z |
| format | Article |
| id | doaj.art-41a5df736a0941be8855013b021b6e24 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:44:44Z |
| publishDate | 2017-08-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-41a5df736a0941be8855013b021b6e242023-09-02T16:29:59ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922017-08-0137375577610.7151/dmgt.1971dmgt.1971Ramsey Properties of Random Graphs and Folkman NumbersRödl Vojtěch0Ruciński Andrzej1Schacht Mathias2Emory University, Atlanta, United States of AmericaA. Mickiewicz University, Poznań, PolandUniversität Hamburg, Hamburg, GermanyFor 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.https://doi.org/10.7151/dmgt.1971ramsey propertyrandom graphfolkman number05c8005c55 |
| spellingShingle | Rödl Vojtěch Ruciński Andrzej Schacht Mathias Ramsey Properties of Random Graphs and Folkman Numbers Discussiones Mathematicae Graph Theory ramsey property random graph folkman number 05c80 05c55 |
| title | Ramsey Properties of Random Graphs and Folkman Numbers |
| title_full | Ramsey Properties of Random Graphs and Folkman Numbers |
| title_fullStr | Ramsey Properties of Random Graphs and Folkman Numbers |
| title_full_unstemmed | Ramsey Properties of Random Graphs and Folkman Numbers |
| title_short | Ramsey Properties of Random Graphs and Folkman Numbers |
| title_sort | ramsey properties of random graphs and folkman numbers |
| topic | ramsey property random graph folkman number 05c80 05c55 |
| url | https://doi.org/10.7151/dmgt.1971 |
| work_keys_str_mv | AT rodlvojtech ramseypropertiesofrandomgraphsandfolkmannumbers AT rucinskiandrzej ramseypropertiesofrandomgraphsandfolkmannumbers AT schachtmathias ramseypropertiesofrandomgraphsandfolkmannumbers |