Abstract
We introduce and study a variant of Ramsey numbers for edge-ordered graphs, that is, graphs with linearly ordered sets of edges. The edge-ordered Ramsey number (R) over bar (e)(G) of an edge-ordered graph is G the minimum positive integer N such that there exists an edge-ordered complete graph R-N on N vertices such that every 2-coloring of the edges of R-N contains a monochromatic copy of G as an edge-ordered subgraph of R-N.
We prove that the edge-ordered Ramsey number (R) over bar (e)(G) is finite for every edge-ordered graph G and we obtain better estimates for special classes of edge-ordered graphs. In particular, we prove (R) over bar (e)(G) <= 2(O(n3 log n)) for every bipartite edge-ordered graph G on n vertices.
We also introduce a natural class of edge-orderings, called lexicographic edge-orderings, for which we can prove much better upper bounds on the corresponding edge-ordered Ramsey numbers. (C) 2020 Elsevier Ltd. All rights reserved.