Journal article icon

Journal article

Ordered Ramsey numbers

Abstract:

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 superpolyno...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted manuscript

Actions


Access Document


Files:
Publisher copy:
10.1016/j.jctb.2016.06.007

Authors


More by this author
Department:
Wadham College
Sudakov, B More by this author
More from this funder
Funding agency for:
Conlon, D
Packard Fellowship More from this funder
Alfred P. Sloan Foundation More from this funder
Publisher:
Elsevier Publisher's website
Journal:
Journal of Combinatorial Theory: Series B Journal website
Volume:
122
Pages:
353-383
Publication date:
2016-07-05
Acceptance date:
2016-06-20
DOI:
ISSN:
1096-0902
Pubs id:
pubs:637303
URN:
uri:f98be693-20cc-4392-9c00-e6533f48c218
UUID:
f98be693-20cc-4392-9c00-e6533f48c218
Local pid:
pubs:637303

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP