Edge-ordered Ramsey numbers
Main Article Content
Abstract
We introduce and study a variant of Ramsey numbers for \emph{edge-ordered graphs}, that is, graphs with linearly ordered sets of edges. The \emph{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}) \leq 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 \emph{lexicographic edge-orderings}, for which we can prove much better upper bounds on the corresponding edge-ordered Ramsey numbers.
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}) \leq 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 \emph{lexicographic edge-orderings}, for which we can prove much better upper bounds on the corresponding edge-ordered Ramsey numbers.
Article Details
How to Cite
Balko, M., & Vizer, M.
(2019).
Edge-ordered Ramsey numbers.
Acta Mathematica Universitatis Comenianae, 88(3), 409-414.
Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1266/674
Issue
Section
EUROCOMB 2019