Ordered Ramsey numbers
<p>Given a labeled graph H with vertex set {1, 2, ..., n}, the ordered Ramsey number r<(H) is the minimum N such that every two-coloring of the edges of the complete graph on {1, 2, ..., N} contains a copy of H with vertices appearing in the same order as in H. The ordered Ramsey number...
| Hlavní autoři: | , , , |
|---|---|
| Médium: | Journal article |
| Vydáno: |
Elsevier
2016
|
| _version_ | 1826306035172769792 |
|---|---|
| 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>Given a labeled graph H with vertex set {1, 2, ..., n}, the ordered Ramsey number r<(H) is the minimum N such that every two-coloring of the edges of the complete graph on {1, 2, ..., N} contains a copy of H with vertices appearing in the same order as in H. The ordered Ramsey number of a labeled graph H is at least the Ramsey number r(H) and the two coincide for complete graphs. However, we prove that even for matchings there are labelings where the ordered Ramsey number is superpolynomial in the number of vertices. Among other results, we also prove a general upper bound on ordered Ramsey numbers which implies that there exists a constant c such that r<(H) ≤ r(H) c log^2 n for any labeled graph H on vertex set {1, 2, ..., n}.</p> |
| first_indexed | 2024-03-07T06:41:50Z |
| format | Journal article |
| id | oxford-uuid:f98be693-20cc-4392-9c00-e6533f48c218 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T06:41:50Z |
| publishDate | 2016 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:f98be693-20cc-4392-9c00-e6533f48c2182022-03-27T12:58:44ZOrdered Ramsey numbersJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:f98be693-20cc-4392-9c00-e6533f48c218Symplectic Elements at OxfordElsevier2016Conlon, DFox, JLee, CSudakov, B<p>Given a labeled graph H with vertex set {1, 2, ..., n}, the ordered Ramsey number r<(H) is the minimum N such that every two-coloring of the edges of the complete graph on {1, 2, ..., N} contains a copy of H with vertices appearing in the same order as in H. The ordered Ramsey number of a labeled graph H is at least the Ramsey number r(H) and the two coincide for complete graphs. However, we prove that even for matchings there are labelings where the ordered Ramsey number is superpolynomial in the number of vertices. Among other results, we also prove a general upper bound on ordered Ramsey numbers which implies that there exists a constant c such that r<(H) ≤ r(H) c log^2 n for any labeled graph H on vertex set {1, 2, ..., n}.</p> |
| spellingShingle | Conlon, D Fox, J Lee, C Sudakov, B Ordered Ramsey numbers |
| title | Ordered Ramsey numbers |
| title_full | Ordered Ramsey numbers |
| title_fullStr | Ordered Ramsey numbers |
| title_full_unstemmed | Ordered Ramsey numbers |
| title_short | Ordered Ramsey numbers |
| title_sort | ordered ramsey numbers |
| work_keys_str_mv | AT conlond orderedramseynumbers AT foxj orderedramseynumbers AT leec orderedramseynumbers AT sudakovb orderedramseynumbers |