On edge‐ordered Ramsey numbers. Issue 4 (2nd September 2020) - Fox, Jacob; Li, Ray
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.