Abstrakt
We introduce and study a variant of Ramsey numbers foredge-orde-red graphs, that is, graphs with linearly ordered sets of edges. The edge-ordered Ramsey number Re(G) of an edge-ordered graph G is the minimum positive integer N such that there exists an edge-ordered complete graph K_N on N vertices suchthat every 2-coloring of the edges of K_N contains a monochromatic copy of G as an edge-ordered subgraph of K_N.
We prove that the edge-ordered Ramsey number Re(G) is finite for every edge-ordered graph G and we obtain better estimates for special classes of edge-orderedgraphs. In particular, we prove Re(G) <= 2^(O(n^3 logn)) for every bipartite edge-orderedgraph G on n vertices.
We also introduce a natural class of edge-orderings, calledlexicographic edge-orderings, for which we can prove much better upper bounds onthe corresponding edge-ordered Ramsey numbers.