Edge-ordered Ramsey numbers

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 ${\overline{R}}_e(\mathfrak{G})$ of an edge-ordered graph $\mathfrak{G}$ is the minimum positive integer $N$ such that there exists an edge-ordered complete graph ${\mathfrak{K}}_N$ on $N$ vertices such that every 2-coloring of the edges of ${\mathfrak{K}}_N$ contains a monochromatic copy of $\mathfrak{G}$ as an edge-ordered subgraph of ${\mathfrak{K}}_N$. We prove that the edge-ordered Ramsey number ${\overline{R}}_e(\mathfrak{G})$ is finite for every edge-ordered graph $\mathfrak{G}$ and we obtain better estimates for special classes of edge-ordered graphs. In particular, we prove ${\overline{R}}_e(\mathfrak{G})\le 2^{O(n^3\log n)}$ for every bipartite edge-ordered graph $\mathfrak{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.

Minor revision, a version that was published in the European Journal of Combinatorics

References in corpus (1)

• On edge-ordered Ramsey numbers

Cited by in corpus (1)

• Erdős-Szekeres theorem for multidimensional arrays