TWO EXTENSIONS OF RAMSEY'S THEOREM
Ramsey's theorem, in the version of Erdo{double acute}s and Szekeres, states that every 2-coloring of the edges of the complete graph on {1,2,.,n} contains a monochromatic clique of order (1/2) log n. In this article, we consider two well-studied extensions of Ramsey's theorem. Improving a...
| المؤلفون الرئيسيون: | , , |
|---|---|
| التنسيق: | Journal article |
| اللغة: | English |
| منشور في: |
2013
|
| _version_ | 1826294206934548480 |
|---|---|
| author | Conlon, D Fox, J Sudakov, B |
| author_facet | Conlon, D Fox, J Sudakov, B |
| author_sort | Conlon, D |
| collection | OXFORD |
| description | Ramsey's theorem, in the version of Erdo{double acute}s and Szekeres, states that every 2-coloring of the edges of the complete graph on {1,2,.,n} contains a monochromatic clique of order (1/2) log n. In this article, we consider two well-studied extensions of Ramsey's theorem. Improving a result of Rödl, we show that there is a constant c > 0 such that every 2-coloring of the edges of the complete graph on {2,3,.,n} contains a monochromatic clique S for which the sum of 1/log i over all vertices iεS is at least c log log log n. This is tight up to the constant factor c and answers a question of Erdo{double acute}s from 1981. Motivated by a problem in model theory, Väänänen asked whether for every k there is an n such that the following holds: for every permutation π of 1,.,k-1, every 2-coloring of the edges of the complete graph on {1,2,.,n} contains a monochromatic clique a1 < < ak with aπ(1)+1-aπ(1)>aπ(2)+1-aπ(2)>> aπ(k-1)+1-aπ(k-1)That is, not only do we want a monochromatic clique, but the differences between consecutive vertices must satisfy a prescribed order. Alon and, independently, Erdo{double acute}s, Hajnal, and Pach answered this question affirmatively. Alon further conjectured that the true growth rate should be exponential in k. We make progress towards this conjecture, obtaining an upper bound on n which is exponential in a power of k. This improves a result of Shelah, who showed that n is at most double-exponential in k. © 2013. |
| first_indexed | 2024-03-07T03:42:04Z |
| format | Journal article |
| id | oxford-uuid:be3e165a-901b-43ca-b123-72883b5c23ef |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T03:42:04Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | oxford-uuid:be3e165a-901b-43ca-b123-72883b5c23ef2022-03-27T05:37:46ZTWO EXTENSIONS OF RAMSEY'S THEOREMJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:be3e165a-901b-43ca-b123-72883b5c23efEnglishSymplectic Elements at Oxford2013Conlon, DFox, JSudakov, BRamsey's theorem, in the version of Erdo{double acute}s and Szekeres, states that every 2-coloring of the edges of the complete graph on {1,2,.,n} contains a monochromatic clique of order (1/2) log n. In this article, we consider two well-studied extensions of Ramsey's theorem. Improving a result of Rödl, we show that there is a constant c > 0 such that every 2-coloring of the edges of the complete graph on {2,3,.,n} contains a monochromatic clique S for which the sum of 1/log i over all vertices iεS is at least c log log log n. This is tight up to the constant factor c and answers a question of Erdo{double acute}s from 1981. Motivated by a problem in model theory, Väänänen asked whether for every k there is an n such that the following holds: for every permutation π of 1,.,k-1, every 2-coloring of the edges of the complete graph on {1,2,.,n} contains a monochromatic clique a1 < < ak with aπ(1)+1-aπ(1)>aπ(2)+1-aπ(2)>> aπ(k-1)+1-aπ(k-1)That is, not only do we want a monochromatic clique, but the differences between consecutive vertices must satisfy a prescribed order. Alon and, independently, Erdo{double acute}s, Hajnal, and Pach answered this question affirmatively. Alon further conjectured that the true growth rate should be exponential in k. We make progress towards this conjecture, obtaining an upper bound on n which is exponential in a power of k. This improves a result of Shelah, who showed that n is at most double-exponential in k. © 2013. |
| spellingShingle | Conlon, D Fox, J Sudakov, B TWO EXTENSIONS OF RAMSEY'S THEOREM |
| title | TWO EXTENSIONS OF RAMSEY'S THEOREM |
| title_full | TWO EXTENSIONS OF RAMSEY'S THEOREM |
| title_fullStr | TWO EXTENSIONS OF RAMSEY'S THEOREM |
| title_full_unstemmed | TWO EXTENSIONS OF RAMSEY'S THEOREM |
| title_short | TWO EXTENSIONS OF RAMSEY'S THEOREM |
| title_sort | two extensions of ramsey s theorem |
| work_keys_str_mv | AT conlond twoextensionsoframseystheorem AT foxj twoextensionsoframseystheorem AT sudakovb twoextensionsoframseystheorem |