Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 2017 | Submitted
Journal Article Open

Ordered Ramsey numbers


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

Additional Information

© 2016 Elsevier Inc. Received 20 October 2014, available online 16 July 2016. Conlon research supported by a Royal Society University Research Fellowship. Fox research supported by a Packard Fellowship, by NSF Career Award DMS-1352121 and by an Alfred P. Sloan Foundation Fellowship. Lee research supported by NSF Grant DMS-1362326. Sudakov research supported in part by SNSF grant 200021-149111. We would like to thank the anonymous referees for a number of helpful remarks.

Attached Files

Submitted - 1410.5292.pdf


Files (307.9 kB)
Name Size Download all
307.9 kB Preview Download

Additional details

August 22, 2023
October 18, 2023