On the grid Ramsey problem and related questions
<p>The Hales–Jewett theorem is one of the pillars of Ramsey theory, from which many other results follow. A celebrated theorem of Shelah says that Hales–Jewett numbers are primitive recursive. A key tool used in his proof, now known as the cube lemma, has become famous in its own right. In it...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Published: |
Oxford University Press
2014
|
| _version_ | 1797063569650483200 |
|---|---|
| author | Conlon, D Fox, J Lee, C Sudakov, B |
| author_facet | Conlon, D Fox, J Lee, C Sudakov, B |
| author_sort | Conlon, D |
| collection | OXFORD |
| description | <p>The Hales–Jewett theorem is one of the pillars of Ramsey theory, from which many other results follow. A celebrated theorem of Shelah says that Hales–Jewett numbers are primitive recursive. A key tool used in his proof, now known as the cube lemma, has become famous in its own right. In its simplest form, this lemma says that if we color the edges of the Cartesian product <i>K</i><sub><i>n</i></sub> × <i>K</i><sub><i>n</i></sub> in <i>r</i> colors then, for <i>n</i> sufficiently large, there is a rectangle with both pairs of opposite edges receiving the same color. Shelah’s proof shows that <i>n</i> = <i>r</i><sup>(<sup><i>r</i>+1</sup><sub style="position: relative; left: -.8em;">2</sub>)</sup> + 1 suffices. More than twenty years ago, Graham, Rothschild and Spencer asked whether this bound can be improved to a polynomial in <i>r</i>. We show that this is not possible by providing a superpolynomial lower bound in <i>r</i>. We also discuss a number of related problems.</p> |
| first_indexed | 2024-03-06T21:01:47Z |
| format | Journal article |
| id | oxford-uuid:3b1e2325-7bd5-41e9-966e-6eeb8d901c08 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T21:01:47Z |
| publishDate | 2014 |
| publisher | Oxford University Press |
| record_format | dspace |
| spelling | oxford-uuid:3b1e2325-7bd5-41e9-966e-6eeb8d901c082022-03-26T14:05:42ZOn the grid Ramsey problem and related questionsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:3b1e2325-7bd5-41e9-966e-6eeb8d901c08Symplectic Elements at OxfordOxford University Press2014Conlon, DFox, JLee, CSudakov, B <p>The Hales–Jewett theorem is one of the pillars of Ramsey theory, from which many other results follow. A celebrated theorem of Shelah says that Hales–Jewett numbers are primitive recursive. A key tool used in his proof, now known as the cube lemma, has become famous in its own right. In its simplest form, this lemma says that if we color the edges of the Cartesian product <i>K</i><sub><i>n</i></sub> × <i>K</i><sub><i>n</i></sub> in <i>r</i> colors then, for <i>n</i> sufficiently large, there is a rectangle with both pairs of opposite edges receiving the same color. Shelah’s proof shows that <i>n</i> = <i>r</i><sup>(<sup><i>r</i>+1</sup><sub style="position: relative; left: -.8em;">2</sub>)</sup> + 1 suffices. More than twenty years ago, Graham, Rothschild and Spencer asked whether this bound can be improved to a polynomial in <i>r</i>. We show that this is not possible by providing a superpolynomial lower bound in <i>r</i>. We also discuss a number of related problems.</p> |
| spellingShingle | Conlon, D Fox, J Lee, C Sudakov, B On the grid Ramsey problem and related questions |
| title | On the grid Ramsey problem and related questions |
| title_full | On the grid Ramsey problem and related questions |
| title_fullStr | On the grid Ramsey problem and related questions |
| title_full_unstemmed | On the grid Ramsey problem and related questions |
| title_short | On the grid Ramsey problem and related questions |
| title_sort | on the grid ramsey problem and related questions |
| work_keys_str_mv | AT conlond onthegridramseyproblemandrelatedquestions AT foxj onthegridramseyproblemandrelatedquestions AT leec onthegridramseyproblemandrelatedquestions AT sudakovb onthegridramseyproblemandrelatedquestions |