On edge‐ordered Ramsey numbers. Issue 4 (2nd September 2020)

• Record Type: Journal Article
• Authors: Fox, Jacob; Li, Ray
• Is Part Of: Random structures & algorithms. Volume 57:Issue 4(2020)
• Page Start: 1174
• Page End: 1204
• Publication Date: 2020-09-02
• Subjects: edge‐ordered graphs -- Ramsey theory -- sparse graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20954
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : An edge‐ordered graph is a graph with a linear ordering of its edges. Two edge‐ordered graphs are equivalent if there is an isomorphism between them preserving the edge‐ordering. The edge‐ordered Ramsey number r edge ( H ; q ) of an edge‐ordered graph H is the smallest N such that there exists an edge‐ordered graph G on N vertices such that, for every q ‐coloring of the edges of G, there is a monochromatic subgraph of G equivalent to H . Recently, Balko and Vizer proved that r edge ( H ; q ) exists, but their proof gave enormous upper bounds on these numbers. We give a new proof with a much better bound, showing there exists a constant c such that r edge ( H ; q ) ≤ 2 c q n 2 q − 2 log q n for every edge‐ordered graph H on n vertices. We also prove a polynomial bound for the edge‐ordered Ramsey number of graphs of bounded degeneracy. Finally, we prove a strengthening for graphs where every edge has a label and the labels do not necessarily have an ordering.