On ordered Ramsey numbers of bounded-degree graphs

Abstract

An ordered graph is a pair $\mathcal{G}=(G,\prec )$ where $G$ is a graph and $\prec$ is a total ordering of its vertices. The ordered Ramsey number $\overline{R}(\mathcal{G})$ is the minimum number $N$ such that every $2$-coloring of the edges of the ordered complete graph on $N$ vertices contains a monochromatic copy of $\mathcal{G}$. We show that for every integer $d\ge 3$, almost every $d$-regular graph $G$ satisfies $\overline{R}(\mathcal{G})\ge \frac{n^{3/2-1/d}}{4\log n\log \log n}$ for every ordering $\mathcal{G}$ of $G$. In particular, there are 3-regular graphs $G$ on $n$ vertices for which the numbers $\overline{R}(\mathcal{G})$ are superlinear in $n$, regardless of the ordering $\mathcal{G}$ of $G$. This solves a problem of Conlon, Fox, Lee, and Sudakov. On the other hand, we prove that every graph $G$ on $n$ vertices with maximum degree 2 admits an ordering $\mathcal{G}$ of $G$ such that $\overline{R}(\mathcal{G})$ is linear in $n$. We also show that almost every ordered matching $\mathcal{M}$ with $n$ vertices and with interval chromatic number two satisfies $\overline{R}(\mathcal{M})\ge c{n}^2/{\log }^{2}n$ for some absolute constant $c$.

19 pages, 8 figures, minor corrections

Cited by in corpus (2)

• Edge-ordered Ramsey numbers
• On ordered Ramsey numbers of tripartite 3-uniform hypergraphs