# Ramsey numbers of ordered graphs††thanks: The first and the fourth author
were supported by the grants SVV-2013-267313 (Discrete Models and Algorithms),
GAUK 1262213 of the Grant Agency of Charles University and by the project CE-
ITI (GAČR P202/12/G061) of the Czech Science Foundation. The fourth author was
also supported by ERC Advanced Research Grant no 267165 (DISCONV). Part of the
research was conducted during the DIMACS REU 2013 program.

Martin Balko1 Josef Cibulka1 Karel Král2 Jan Kynčl1,3

###### 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
$\operatorname{\overline{R}}(\mathcal{G};c)$ is the minimum number $N$ such
that every ordered complete graph with $N$ vertices and with edges colored by
$c$ colors contains a monochromatic copy of $\mathcal{G}$.

In contrast with the case of unordered graphs, we show that there are
arbitrarily large ordered matchings $\mathcal{M}_{n}$ on $n$ vertices for
which $\operatorname{\overline{R}}(\mathcal{M}_{n};2)$ is super-polynomial in
$n$. This implies that ordered Ramsey numbers of the same graph can grow
super-polynomially in the size of the graph in one ordering and remain linear
in another ordering.

We also prove that the ordered Ramsey number $R(\mathcal{G};2)$ is polynomial
in the number of vertices of $\mathcal{G}$ if $\mathcal{G}$ has edges of
constant length or if $\mathcal{G}$ is an ordered graph of constant degeneracy
and constant interval chromatic number.

For a few special classes of ordered paths, stars or matchings, we give
asymptotically tight bounds on their ordered Ramsey numbers. For so called
monotone cycles we compute their ordered Ramsey numbers exactly. This result
implies exact formulas for geometric Ramsey numbers of cycles introduced by
Károlyi et al.

1 Department of Applied Mathematics and Institute for Theoretical Computer
Science,
Charles University, Faculty of Mathematics and Physics,
Malostranské nám. 25, 118 00 Praha 1, Czech Republic;
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

2 Department of Applied Mathematics,
Charles University, Faculty of Mathematics and Physics,
Malostranské nám. 25, 118 00 Praha 1, Czech Republic;
<EMAIL_ADDRESS>

3 Alfréd Rényi Institute of Mathematics, Reáltanoda u. 13-15, Budapest 1053,
Hungary

##  1 Introduction

Ramsey’s theorem states that for every given graph $G$, every sufficiently
large complete graph with edges colored by a constant number of colors
contains a monochromatic copy of $G$. We study the analogue of Ramsey’s
theorem for graphs with ordered vertex sets. The concept of ordered graphs
appeared earlier in the literature [29, 30, 34, 36], but we are not aware of
any Ramsey-type results for such graphs except for the case of monotone paths
and hyperpaths [6, 15, 21, 34, 35].

The main goal of this paper is to understand the effects of different vertex
orderings on the ordered Ramsey number of a given graph, and to compare the
ordered and unordered Ramsey numbers. We state our results after introducing
the necessary notation and presenting a few examples that provide the
motivation.

During the preparation of this paper, we learned that some of our results have
been independently obtained by Conlon, Fox, Lee and Sudakov [13].

Throughout the paper, we omit the ceiling and floor signs whenever they are
not crucial. Unless indicated otherwise, all logarithms in this paper are base
2.

#### Hypergraphs

In this paper, we consider only finite graphs and hypergraphs with no multiple
edges and no loops (that is, one-element edges). We prove all our results only
for graphs.

An edge coloring of a hypergraph $H=(V,E)$, briefly a coloring, is a mapping
$f\colon E\to C$ where $C$ is a finite set of colors. A coloring with $c$
colors is called a $c$-coloring. The complete $k$-uniform hypergraph on $n$
vertices, denoted by $K_{n}^{k}$, is a hypergraph whose edges are all
$k$-element subsets of the $n$ vertices. An extended Ramsey’s theorem says
that for given positive integers $c$, $k$ and $n$, if $N$ is sufficiently
large, then every $c$-coloring of the edges of $K^{k}_{N}$ contains a
monochromatic copy of $K_{n}^{k}$. The minimum such $N$ is called the Ramsey
number and we denote it by $\operatorname{R}_{k}(K^{k}_{n};c)$. For graphs we
write $\operatorname{R}(K_{n};c)$ instead of $\operatorname{R}_{2}(K_{n};c)$.
Classical results of Erdős [16] and Erdős and Szekeres [17] give the
exponential bounds

$2^{n/2}\leq\operatorname{R}(K_{n};2)\leq 2^{2n}.$ (1)

Despite many improvements during the last sixty years (see [11] for example),
the constant factors in the exponents remain the same.

Since every $k$-uniform hypergraph on $n$ vertices is contained in
$K^{k}_{n}$, we can consider the following generalization of Ramsey numbers.
Let $c$ be a positive integer and let ${H}_{1},\ldots,{H}_{c}$ be finite
$k$-uniform hypergraphs. Ramsey’s theorem then implies that there exists the
smallest number $\operatorname{R}_{k}({H}_{1},\ldots,{H}_{c})$ such that every
$c$-coloring of edges of a complete $k$-uniform hypergraph with at least
$\operatorname{R}_{k}({H}_{1},\ldots,{H}_{c})$ vertices contains a
monochromatic copy of ${H}_{i}$ in color $i$ for some
$i\in\\{1,2,.\ldots,c\\}$. If all the hypergraphs ${H}_{1},\ldots,{H}_{c}$ are
isomorphic to ${H}$, we just write $\operatorname{R}_{k}({H};c)$.

#### Ordered hypergraphs

An ordered hypergraph $\mathcal{H}$ is a pair $({H},\prec)$ where $H$ is a
hypergraph and $\prec$ is a total ordering of its vertex set. The ordering
$\prec$ is called a vertex ordering. Many notions related to hypergraphs, such
as vertex degrees or a coloring, can be defined analogously for ordered
hypergraphs. In addition, we introduce a few more notions specific to ordered
hypergraphs.

For an ordered hypergraph $\mathcal{H}=(H,\prec)$ and its vertices $x,y$, we
say that $y$ is a left neighbor of $x$ and that $x$ is a right neighbor of $y$
if $x$ and $y$ belong to a common edge and $y\prec x$. We say that two ordered
hypergraphs $(H_{1},\prec_{1})$ and $(H_{2},\prec_{2})$ are isomorphic if
$H_{1}$ and $H_{2}$ are isomorphic via a one-to-one mapping $g\colon
V(H_{1})\to V(H_{2})$ that also preserves the orderings; that is, for every
$x,y\in V(H_{1})$, $x\prec_{1}y\Leftrightarrow g(x)\prec_{2}g(y)$. An ordered
(hyper)graph $\mathcal{H}=({H},\prec_{1})$ is an ordered sub(hyper)graph of
$\mathcal{G}=({G},\prec_{2})$, written $\mathcal{H}\subseteq\mathcal{G}$, if
${H}$ is a sub(hyper)graph of ${G}$ and $\prec_{1}$ is a suborder of
$\prec_{2}$.

We now introduce Ramsey numbers of ordered hypergraphs. For given ordered
$k$-uniform hypergraphs $\mathcal{H}_{1},\ldots,\mathcal{H}_{c}$, we denote by
$\operatorname{\overline{R}}_{k}(\mathcal{H}_{1},\ldots,\mathcal{H}_{c})$ the
smallest number $N$ such that every $c$-coloring of the edges of the complete
ordered $k$-uniform hypergraph with $N$ vertices contains, for some $i$, a
monochromatic copy of $\mathcal{H}_{i}$ in color $i$ as an ordered
subhypergraph. If all $\mathcal{H}_{i}$ are isomorphic to $\mathcal{H}$, we
write the ordered Ramsey number as
$\operatorname{\overline{R}}_{k}(\mathcal{H};c)$. In the case of graphs (that
is, if $k=2$) we write
$\operatorname{\overline{R}}(\mathcal{H}_{1},\allowbreak\ldots,\allowbreak\mathcal{H}_{c})$
or $\operatorname{\overline{R}}(\mathcal{H};c)$, respectively. If a coloring
$f$ of a hypergraph $\mathcal{G}$ contains no monochromatic copy of
$\mathcal{H}$, we say that $f$ avoids $\mathcal{H}$.

Up to isomorphism, there is only one ordered complete $k$-uniform hypergraph
on $n$ vertices, which we denote as $\mathcal{K}_{n}^{k}$, or
$\mathcal{K}_{n}$ if $k=2$. Therefore,
$\operatorname{\overline{R}}_{k}(\mathcal{K}^{k}_{r_{1}},\ldots,\mathcal{K}^{k}_{r_{c}})=\operatorname{R}_{k}(K^{k}_{r_{1}},\ldots,K^{k}_{r_{c}})$
for arbitrary positive integers $k,c,r_{1},\ldots,r_{c}$. Since every ordered
$k$-uniform hypergraph on $r$ vertices is an ordered subhypergraph of
$\mathcal{K}^{k}_{r}$, we get
$\operatorname{\overline{R}}_{k}(\mathcal{H}_{1},\ldots,\mathcal{H}_{c})\leq\operatorname{\overline{R}}_{k}(\mathcal{K}^{k}_{r_{1}},\ldots,\mathcal{K}^{k}_{r_{c}})$
where $r_{i}$ is the number of vertices of $\mathcal{H}_{i}$. We have thus
proved the following fact.

######  Observation 1.

Let $c$ and $k$ be arbitrary positive integers and let
$\mathcal{H}_{1}=(H_{1},\prec_{1}),\ldots,\mathcal{H}_{c}=(H_{c},\prec_{c})$
be an arbitrary collection of ordered $k$-uniform hypergraphs. Then we have

$\operatorname{R}_{k}(H_{1},\ldots,H_{c})\leq\operatorname{\overline{R}}_{k}(\mathcal{H}_{1},\ldots,\mathcal{H}_{c})\leq\operatorname{R}_{k}\left(K^{k}_{|V(H_{1})|},\ldots,K^{k}_{|V(H_{c})|}\right).$

To study the asymptotic growth of ordered Ramsey numbers, we introduce
ordering schemes for some classes of hypergraphs. An ordering scheme is a
particular rule for ordering the vertices of the hypergraphs consistently in
the whole class. For example, a $k$-uniform monotone hyperpath
$(P^{k}_{n},\lhd_{mon})$ is a $k$-uniform hypergraph with vertices
$v_{1}\lhd_{mon}\ldots\lhd_{mon}v_{n}$ and $n-k+1$ edges, each consisting of
$k$ consecutive vertices; see Figure 1 for an example. Throughout the paper we
use a symbol $\lhd$ instead of $\prec$ to emphasize the fact that the vertex
ordering follows some ordering scheme.

Figure 1: Examples of $2$-uniform and $3$-uniform monotone hyperpaths on seven
vertices.

For an ordered graph $(G,\prec)$, we say that a vertex $v$ of $G$ is to the
left (right, respectively) of a subset $U$ of vertices of $G$ if $v$ precedes
(is preceded by, respectively) every vertex of $U$ in $\prec$. More generally,
for two subsets $U$ and $W$ of vertices of $G$, we say that $U$ is to the left
of $W$ and $W$ is to the right of $U$ if every vertex of $U$ precedes every
vertex of $W$ in $\prec$.

For an ordered graph $(G,\prec)$, we say that a subset $I$ of vertices of $G$
is an interval if for every pair of vertices $u$ and $v$ of $I$, $u\prec v$,
every vertex $w$ of $G$ satisfying $u\prec w\prec v$ is contained in $I$.

###  1.1 Motivation

In this subsection we show various examples in which Ramsey-type problems on
ordered hypergraphs appear. The examples consist of both classical and recent
results. Some results and definitions are also used later in the paper.

#### Erdős–Szekeres lemma

This well-known statement says that for a given positive integer $k$ one can
find a decreasing or increasing subsequence of length $k$ in every sequence of
at least $(k-1)^{2}+1$ distinct integers. It is easy to see that this bound is
sharp. The Erdős–Szekeres lemma has many proofs [38] and it is also a special
case of a more general Ramsey-type result for ordered graphs.

Given a sequence $S=(s_{1},\ldots,s_{N})$ of integers we construct an ordered
graph $(K_{N},\prec)$ with vertex set $S$ and the ordering of the vertices
given by their positions in $S$. That is, for $s_{i},s_{j}\in S$ we have
$s_{i}\prec s_{j}$ if $i<j$. Then we color an edge $\\{s_{i},s_{j}\\}$ with
$i<j$ red if $s_{i}<s_{j}$ and blue otherwise. Afterwards, red monotone paths
correspond to increasing subsequences of $S$ and blue monotone paths to
decreasing subsequences of $S$. The lemma now follows from the following
result by Choudum and Ponnusamy [6] (see Milans et al. [34] for a proof in the
language of ordered Ramsey theory).

######  Proposition 2 ([6]).

For arbitrary monotone ordered paths
$(P_{r_{1}},\lhd_{mon}),\ldots,(P_{r_{c}},\lhd_{mon})$, we have
$\operatorname{\overline{R}}((P_{r_{1}},\lhd_{mon}),\ldots,(P_{r_{c}},\lhd_{mon}))=1+\prod_{i=1}^{c}(r_{i}-1)$.

#### Integer partitions

Ramsey numbers of monotone hyperpaths recently attracted the attention of many
researchers [15, 21, 34, 35]. Moshkovitz and Shapira [35] discovered a
connection between Ramsey numbers of monotone hyperpaths and high-dimensional
integer partitions. A $d$-dimensional partition is a $d$-dimensional
(hyper)matrix $A$ of nonnegative integers such that $A$ is decreasing in each
line. That is, $A_{i_{1},\ldots,i_{t},\ldots,i_{d}}\geq
A_{i_{1},\ldots,i_{t}+1,\ldots,i_{d}}$ for every possible $i_{1},\ldots,i_{d}$
and $1\leq t\leq d$. For example, a $1$-dimensional partition is just a non-
increasing sequence of nonnegative integers $a_{1}\geq a_{2}\geq\ldots$, and
it is also called a line partition.

Let $P_{d}(n)$ denote the number of $n\times n$ $d$-dimensional partitions
with entries from $\\{0,\ldots,n\\}$. Observe that $P_{1}(n)={2n\choose n}$,
since we can represent a line partition as a lattice path in $\mathbb{Z}^{2}$
starting at $(0,n)$, ending at $(n,0)$, and going only right or down in each
step.

######  Theorem 3 ([35]).

For every $c\geq 2$ and $n\geq 2$ we have
$\operatorname{\overline{R}}_{3}((P^{3}_{n},\lhd_{mon});c)=P_{c-1}(n-2)+1$.

#### Erdős–Szekeres theorem

The Erdős–Szekeres theorem was one of the earliest results that contributed to
the development of Ramsey theory. A finite set of points in the plane is in
general position if no three of the points are collinear, and in convex
position if the points form a vertex set of a convex polygon.

######  Theorem 4 ([17]).

For every $k\in\mathbb{N}$ there is a finite number $\operatorname{ES}(k)$
such that every set of at least $\operatorname{ES}(k)$ points in the plane in
general position contains $k$ points in convex position.

As noted by Erdős and Szekeres, this result can be proved using Ramsey theorem
for (unordered) 4-uniform hypergraphs. However the upper bound for
$\operatorname{ES}(k)$ obtained by this approach is astronomically large. In
their original paper Erdős and Szekeres proved a more reasonable bound
$\operatorname{ES}(k)\leq{{2k-4}\choose{k-2}}+1$. Moshkovitz and Shapira
showed [35] that the same bound can be derived from Theorem 3 with $c=2$ in
the following way.

Suppose that we have a set $S\subset\mathbb{R}^{2}$ of
$N\geq\operatorname{ES}(k)$ points in general position. Let
$(K^{3}_{N},\prec)$ be an ordered 3-uniform hypergraph with vertex set $S$
where the ordering of the vertices is given by their $x$-coordinates. An edge
$\\{x,y,z\\}$ is then colored red if the triangle $xyz$ is oriented
counterclockwise and blue otherwise. In this coloring a monochromatic monotone
3-uniform path corresponds to a (special) convex $k$-gon in $S$ (sometimes
called a $k$-cup or a $k$-cap). Theorem 3 gives us the upper bound
$\operatorname{ES}(k)\leq{{2k-4}\choose{k-2}}+1$.

#### Discrete geometry

In some Ramsey-type problems of discrete geometry, ordered Ramsey numbers
arise quite naturally, as we illustrate on the example of geometric Ramsey
numbers [10, 27, 28]. The authors of this paper arrived at studying Ramsey
numbers of ordered graphs while working on a variant of the Erdős-Szekeres
problem for so called 2-page drawings of $K_{n}$ [7]. 111A $2$-page drawing of
$K_{n}$ is a drawing where vertices of $K_{n}$ are placed on a horizontal line
(the _spine_), edges between consecutive vertices are subsegments of the line
and each of the remaining edges goes either above or below the line. The edges
going above the line are _red_ and the edges going below are _blue_. Let
$v_{1},\ldots,v_{n}$ be the vertices in the order in which they occur on the
line. Analogously to the above mentioned proof of Theorem 4, a triple $v_{i}$,
$v_{j}$, $v_{k}$, where $i<j<k$ is colored red if $v_{j}$ lies below the edge
$v_{i}v_{k}$ and blue otherwise. The color of $v_{i}v_{j}v_{k}$ is thus equal
to the color of $v_{i}v_{k}$. A monochromatic monotone $3$-uniform path
corresponds to a monochromatic ($2$-uniform) ordered graph with pairs vertices
connected if and only if they are at distance $2$. Although this direction of
research did not give any interesting results on $2$-page drawings, it lead to
Theorem 10.

For a finite set of points $P\subset\mathbb{R}^{2}$ in general position (no
three points are collinear), we denote as $K_{P}$ the complete geometric graph
on $P$ which is a complete graph with vertex set $P$ whose edges are straight-
line segments between pairs of points of $P$. The graph $K_{P}$ is convex if
the points from $P$ are in convex position. The geometric Ramsey number of
$G$, denoted by $\operatorname{Rg}(G)$, is the smallest integer $N$ such that
every complete geometric graph $K_{P}$ on $N$ vertices with edges colored by
two colors contains a monochromatic non-crossing copy of $G$. If we consider
only convex complete geometric graphs $K_{P}$ in the definition, then we get
so called convex geometric Ramsey number $\operatorname{Rc}(G)$. Note that
these numbers are finite only if $G$ is outerplanar and that we have
$\operatorname{Rc}(G)\leq\operatorname{Rg}(G)$ for every outerplanar graph
$G$.

For the cycles $C_{n}$, $n\geq 3$, Károlyi et al. [28] showed an upper bound
$\operatorname{Rg}(C_{n})\leq 2n^{2}-6n+6=2(n-2)(n-1)+2$ and also observed
that $\operatorname{Rc}(C_{n})\geq(n-1)^{2}+1$ holds.

A monotone cycle $(C_{n},\lhd_{mon})$ on $n$ vertices consists of a monotone
path on vertices $v_{1}\lhd_{mon}\ldots\lhd_{mon}v_{n}$ and the edge
$\\{v_{1},v_{n}\\}$. See Figure 2 for an example. Later, we show that the
geometric and convex geometric Ramsey numbers of cycles are equal to ordered
Ramsey numbers of monotone cycles. Here, we prove the equivalence of the
ordered and convex geometric Ramsey numbers of cycles.

Figure 2: The monotone cycle $(C_{6},\lhd_{mon})$.

######  Observation 5.

For every integer $n\geq 3$, we have
$\operatorname{Rc}(C_{n})=\operatorname{\overline{R}}((C_{n},\lhd_{mon});2)$.

###### Proof.

Consider a set of $n$ points in convex position. Order the points
$v_{1}\prec\cdots\prec v_{n}$ in the clockwise (or counterclockwise) order
starting at an arbitrary vertex. The observation follows from the fact that
the cycle $C_{n}$ on $v_{1},\ldots,v_{n}$ is non-crossing if and only if it is
the monotone cycle. ∎

#### Extremal problems on matrices

The last motivation example shows a connection between extremal theory of
$\\{0,1\\}$-matrices (see [9, 22], for example) and ordered Turán numbers of
ordered bipartite graphs. We use some results from this area in Section 2.2.

A $\\{0,1\\}$-matrix $A$ contains an $r\times s$ submatrix $M$ if $A$ contains
a submatrix $M$ which has ones on all the positions where $M$ does. A matrix
$A$ avoids $M$ if it does not contain $M$. The extremal function of $M$ is the
maximum number $\operatorname{ex}_{M}(m,n)$ of 1-entries in an $m\times n$
$\\{0,1\\}$-matrix avoiding $M$.

Let $K_{n_{1},\ldots,n_{p}}$ denote the complete $p$-partite graph with color
classes of size $n_{1},\ldots,n_{p}$. In the case $n_{1}=\cdots=n_{p}=n$, we
simply write $K_{n}(p)$. We use $\mathcal{K}_{n_{1},\ldots,n_{p}}$ to denote
the ordering of $K_{n_{1},\ldots,n_{p}}$ in which the color classes form
consecutive disjoint intervals such that the interval of size $n_{i}$ is the
$i$th such interval. Note that the ordering of indices $n_{1},\ldots,n_{p}$ in
$\mathcal{K}_{n_{1}\ldots,n_{p}}$ is important. Again, if all the sizes
$n_{1},\ldots,n_{p}$ are equal to $n$, we write $\mathcal{K}_{n}(p)$ instead.
See Figure 3 for an example.

Let $\mathcal{G}$ and $\mathcal{H}$ be ordered graphs. The Turán number of
$\mathcal{G}$ in $\mathcal{H}$ is the maximum number of edges in a subgraph
$\mathcal{H^{\prime}}$ of $\mathcal{H}$ such that $\mathcal{G}$ is not a
subgraph of $\mathcal{H^{\prime}}$.

Let $\mathcal{G}=((A\cup B,E),\prec)$, $|A|=r$ and $|B|=s$, be a a subgraph of
$\mathcal{K}_{r,s}$. Then $\mathcal{G}$ corresponds to an $r\times s$
$\\{0,1\\}$-matrix $M(\mathcal{G})$ where $M(\mathcal{G})_{i,j}=1$ if the
$i$th vertex in $A$ and the $j$th vertex in $B$ are adjacent and 0 otherwise.
It is easy to see that the Turán number of $\mathcal{G}$ in
$\mathcal{K}_{m,n}$ is exactly the value of
$\operatorname{ex}_{M(\mathcal{G})}(m,n)$.

Figure 3: The ordered complete bipartite graph $\mathcal{K}_{4,3}$ with
distinguished color classes.

###  1.2 Our results

We are interested in the effects of vertex orderings on Ramsey numbers of
various classes of graphs. As can be seen in the motivation examples, for an
ordering $\mathcal{G}$ of a graph $G$ we can get asymptotic difference between
$\operatorname{R}(G;c)$ and $\operatorname{\overline{R}}(\mathcal{G};c)$. For
example, Proposition 2 implies that $\operatorname{R}(P_{n};c)$ is linear in
$n$ while $\operatorname{\overline{R}}((P_{n},\lhd_{mon});c)$ is quadratic.

Even a larger gap can be obtained for hypergraphs. Let $t_{h}$ denote a tower
function of height $h$ defined by $t_{1}(x)=x$ and $t_{h}(x)=2^{t_{h-1}(x)}$.
It is known that Ramsey numbers $\operatorname{R}_{k}({H};2)$ of sparse
unordered $k$-uniform hypergraphs ${H}$ are linear with respect to the number
of vertices ${H}$. Formally, for positive integers $\Delta$ and $k$, there
exists a constant $C(\Delta,k)$ such that if ${H}$ is a $k$-uniform hypergraph
with $n$ vertices and maximum degree $\Delta$, then
$\operatorname{R}_{k}(H;2)\leq C(\Delta,k)n$ [12]. On the other hand,
Moshkovitz and Shapira [35] showed that for every $k\geq 3$ we have
$\operatorname{\overline{R}}_{k}((P^{k}_{n},\lhd_{mon});2)=t_{k-1}((2-o(1))n)$
where the $o(1)$ term goes to zero with $n$. Thus there are $k$-uniform
hypergraphs $H$ and their orderings $\mathcal{H}$ such that
$\operatorname{\overline{R}}_{k}(\mathcal{H};2)$ grow as a tower of height
$k-1$ in $n$ while $\operatorname{R}_{k}(H;2)$ remain linear in $n$.

In the first part of this paper we derive bounds for Ramsey numbers of
specific classes of ordered graphs: stars, paths and cycles. First, we show
that Ramsey numbers of all ordered stars are linear with respect to the number
of vertices.

######  Theorem 6.

For positive integers $c$ and $r_{1},\ldots,r_{c}$ and for a collection of
ordered stars $\mathcal{S}_{1},\ldots,\mathcal{S}_{c}$ where $r_{i}$ is the
number of vertices of $\mathcal{S}_{i}$ there is a constant $C=C(c)$ such that

$\operatorname{\overline{R}}(\mathcal{S}_{1},\ldots,\mathcal{S}_{c})\leq
C\cdot\max\\{r_{1},\ldots,r_{c}\\}.$

Considering the multi-colored case, we find a graphs $G$ and their vertex
orderings $\lhd$ and $\lhd^{\prime}$ such that the Ramsey numbers of
$(G,\lhd)$ and $(G,\lhd^{\prime})$ differ exponentially in the number of
colors (Proposition 15).

In Section 2.2 we show an ordering of the path $P_{n}$ whose ordered Ramsey
number is linear in $n$ (Proposition 18). In Section 2.3 we discuss ordered
cycles. First, we show Ramsey numbers for all possible orderings of $C_{4}$
(Proposition 21). Then we derive an exact formula for ordered Ramsey numbers
of monotone cycles.

######  Theorem 7.

For integers $r\geq 2$ and $s\geq 2$ we have

$\operatorname{\overline{R}}((C_{r},\lhd_{mon}),(C_{s},\lhd_{mon}))=2rs-3r-3s+6.$

As a consequence of this theorem we obtain tight bounds for so called
geometric and convex geometric Ramsey numbers of cycles which were introduced
by Károlyi et al. [27, 28], see Corollary 23.

The second part of the paper contains general bounds for ordered Ramsey
numbers. We use a standard existence argument to find a lower bound for
ordered Ramsey numbers of every ordered graph $\mathcal{G}$ which depends on
the number of edges of $\mathcal{G}$. See Proposition 24 which implies the
following statement.

######  Proposition 8.

Let $c\geq 2$ be a positive integer and let $\mathcal{G}$ be an ordered graph
with $n$ vertices and $n^{1+\varepsilon}$ edges for some $\varepsilon>0$. Then
$\operatorname{\overline{R}}(\mathcal{G};c)=\Omega(nc^{n^{\varepsilon}})$.

Ramsey numbers of unordered $n$-vertex graphs with maximum degree of a
constant size are linear in $n$ [12]. In a sharp contrast to this result, we
show that Ramsey numbers of ordered matchings may grow faster than any
polynomial.

######  Theorem 9.

There are arbitrarily large ordered matchings $\mathcal{M}_{n}$ on $n$
vertices such that

$\operatorname{\overline{R}}(\mathcal{M}_{n};2)\geq
n^{\frac{\log{n}}{5\log\log{n}}}.$

Combining this result with the fact that there are ordered $n$-vertex
matchings with ordered Ramsey numbers that are linear in $n$, we get that
there are orderings $\lhd_{1}$ and $\lhd_{2}$ of an $n$-vertex matching $M$
such that
$\operatorname{\overline{R}}((M,\lhd_{1});2)/\operatorname{\overline{R}}((M,\lhd_{2});2)=n^{\Omega(\log{n}/\log\log
n)}$.

In the following we give polynomial upper bounds on ordered Ramsey numbers for
two classes of sparse ordered graphs. First, we derive a polynomial upper
bound for ordered Ramsey numbers of ordered graphs which admit the following
decomposition.

For given positive integers $k$ and $q\geq 2$ we say that an ordered graph
$\mathcal{G}=(G,\prec)$ is $(k,q)$-decomposable if $\mathcal{G}$ has at most
$k$ vertices or if it admits the following recursive decomposition: there is a
nonempty interval $I$ with at most $k$ vertices of $\mathcal{G}$ such that the
interval $I_{L}$ of vertices of $\mathcal{G}$ that are to the left of $I$ and
the interval $I_{R}$ of vertices of $\mathcal{G}$ that are to the right of $I$
satisfy $|I_{L}|,|I_{R}|\leq|V(G)|\cdot\frac{q-1}{q}$ and there is no edge
between $I_{L}$ and $I_{R}$. Moreover, the ordered graphs
$(G[I_{L}],\prec\restriction_{I_{L}})$ and
$(G[I_{R}],\prec\restriction_{I_{R}})$ are $(k,q)$-decomposable.

######  Theorem 10.

For fixed positive integers $k$, $q\geq 2$ and $(k,q)$-decomposable ordered
graphs $\mathcal{G}$ and $\mathcal{H}$ we have

$\operatorname{\overline{R}}(\mathcal{G},\mathcal{H})\leq C_{k}\cdot
2^{64k(\lceil\log_{q/(q-1)}{r}\rceil+\lceil\log_{q/(q-1)}{s}\rceil)}$

where $r$ is the number of vertices of $\mathcal{G}$, $s$ is the number of
vertices of $\mathcal{H}$ and $C_{k}$ is a sufficiently large constant
dependent on $k$.

We say that the length of an edge $\\{u,v\\}$ in an ordered graph $(G,\prec)$
is $|i-j|$ if $u$ is the $i$th vertex and $v$ is the $j$th vertex of $G$ in
the ordering $\prec$.

######  Corollary 11.

For a fixed positive integer $k$, every $n$-vertex ordered graph $\mathcal{G}$
with all edge lengths at most $k$ satisfies

$\operatorname{\overline{R}}(\mathcal{G};2)\leq C_{k}\cdot
2^{256k\lceil\log{n}\rceil}$

where $C_{k}$ is a sufficiently large constant dependent on $k$.

###### Proof.

Every ordered graph $\mathcal{G}$ with maximum edge length $k$ is
$(k,2)$-decomposable, so we can apply Theorem 10 for $\mathcal{G}$ with
$r\mathrel{\mathop{:}}=n$, $s\mathrel{\mathop{:}}=n$,
$q\mathrel{\mathop{:}}=2$, and $p\mathrel{\mathop{:}}=2$. ∎

The last result is a polynomial upper bound for ordered Ramsey numbers of
ordered graphs with constant degeneracy and constant interval chromatic
number. For an ordered graph $\mathcal{G}$, the interval chromatic number of
$\mathcal{G}$ is the minimum number of intervals the vertex set of
$\mathcal{G}$ can be partitioned into such that there is no edge between
vertices of the same interval.

######  Theorem 12.

For positive integers $k$ and $p$, every $k$-degenerate ordered graph
$\mathcal{G}$ with $n$ vertices and interval chromatic number $p$ satisfies

$\operatorname{\overline{R}}(\mathcal{G};2)\leq
n^{(1+2/k)(k+1)^{\lceil\log{p}\rceil}-2/k}.$

This result is a corollary of a stronger statement, Theorem 29. See Section
4.2.

#### The work of Conlon et al.

While presenting this paper at the conference Summit 240, we learned about a
recent work of Conlon, Fox, Lee and Sudakov [13] who independently
investigated Ramsey numbers of ordered graphs. There are some overlaps with
our results.

Among many other results, the authors of [13] proved that as $n$ goes to
infinity, almost every ordering $\mathcal{M}_{n}$ of a matching on $n$
vertices satisfies $\operatorname{\overline{R}}(\mathcal{M}_{n};2)\geq
n^{\frac{\log{n}}{20\log\log{n}}}$ which gives asymptotically the same bound
as Theorem 9, which shows only existence of such matchings.

They also showed that there exists a constant $c$ such that every $n$-vertex
ordered graph $\mathcal{G}$ with degeneracy $k$ and interval chromatic number
$p$ satisfies $\operatorname{\overline{R}}(\mathcal{G};2)\leq n^{ck\log{p}}$.
This gives a stronger estimate than Theorem 12.

On the other hand, Corollary 11 gives a solution to Problem 6.9 in [13] by
showing that for every natural number $k$ there exists a constant $c_{k}$ such
that $\operatorname{\overline{R}}(\mathcal{G};2)\leq n^{c_{k}}$ for every
ordered graph $\mathcal{G}$ on $n$ vertices with bandwidth at most $k$. Here,
the notion of bandwidth of an ordered graph $\mathcal{G}$ corresponds to the
maximum edge length in $\mathcal{G}$.

##  2 Ordered Ramsey numbers for specific classes of graphs

In this section we compute Ramsey numbers for various classes of ordered
graphs such as ordered stars, cycles and paths. We also compare the obtained
formulas and bounds with known Ramsey numbers of corresponding unordered
graphs.

###  2.1 Stars

A star is a complete bipartite graph $K_{1,n-1}$. Ramsey numbers of unordered
stars are known exactly [4] and they are given by

$\operatorname{R}(K_{1,n-1};c)=\begin{cases}c(n-2)+1&\text{if }c\equiv
n-1\equiv 0\;(\bmod\;2),\\\ c(n-2)+2&\text{otherwise}.\end{cases}$

The position of the central vertex of a star determines the ordering of the
star uniquely up to isomorphism. We denote as $\mathcal{S}_{r,s}$ the ordered
star which has $r-1$ vertices to the right and $s-1$ vertices to the left of
the central vertex, see Figure 4. Note that $\mathcal{S}_{r,s}$ has $r+s-1$
vertices. For $c,r_{1},\ldots,r_{c}\in\mathbb{N}$, determining
$\operatorname{\overline{R}}(\mathcal{S}_{1,r_{1}},\ldots,\mathcal{S}_{1,r_{c}})$
is a simple observation.

Figure 4: The ordered star $\mathcal{S}_{r,s}$.

######  Observation 13.

For positive integers $c,r_{1},\ldots,r_{c}$ we have

$\operatorname{\overline{R}}(\mathcal{S}_{1,r_{1}},\ldots,\mathcal{S}_{1,r_{c}})=2(1-c)+\sum_{i=1}^{c}r_{i}.$

###### Proof.

Assume that we have a complete ordered graph $\mathcal{K}_{N}$ with $N\geq
2(1-c)+\sum_{i=1}^{c}r_{i}$ vertices and $c$-colored edges. Then, according to
the pigeonhole principle, the first vertex in $\mathcal{K}_{N}$ has at least
$r_{i}-1$ right neighbors in color $i$. This forms a monochromatic copy of
$\mathcal{S}_{1,r_{i}}$.

On the other hand, we can construct a $c$-coloring of the edges of
$\mathcal{K}_{N}$ with $N\mathrel{\mathop{:}}=1-2c+\sum_{i=1}^{c}r_{i}$ which
does not contain any forbidden star. It suffices to divide the right neighbors
of each vertex $v$ into $c$ parts where the $i$th part has size at most
$r_{i}-2$ and each of its vertices is adjacent to $v$ with an edge colored
with $i$. ∎

Thus the ordered Ramsey numbers
$\operatorname{\overline{R}}(\mathcal{S}_{1,n};c)$ are almost the same as
$\operatorname{R}(K_{1,n-1};c)$ for every $n$ and $c$. They differ by one only
if $c\equiv n-1\equiv 0\;(\bmod\;2)$.

Obviously, we have
$\operatorname{\overline{R}}(\mathcal{S}_{1,r},\mathcal{S}_{s,1})=\operatorname{\overline{R}}(\mathcal{S}_{r,1},\mathcal{S}_{1,s})=\operatorname{\overline{R}}(\mathcal{S}_{1,s},\mathcal{S}_{r,1})$
and $\operatorname{\overline{R}}(\mathcal{S}_{r,1},\mathcal{S}_{1,2})=r$ for
every pair $r,s\geq 2$ of positive integers. The ordered Ramsey numbers of an
arbitrary pair of ordered stars are determined by results of Choudum and
Ponnusamy [6].

######  Theorem 14 ([6]).

For positive integers $r_{1},r_{2}\geq 2$ we have

$\operatorname{\overline{R}}(\mathcal{S}_{1,r_{1}},\mathcal{S}_{r_{2},1})=\left\lfloor\frac{-1+\sqrt{1+8(r_{1}-2)(r_{2}-2)}}{2}\right\rfloor+r_{1}+r_{2}-2.$

Moreover, for integers $r_{1},r_{2},s_{1},s_{2}\geq 2$ we have

$\operatorname{\overline{R}}(\mathcal{S}_{1,r_{1}},\mathcal{S}_{r_{2},s_{2}})=\operatorname{\overline{R}}(\mathcal{S}_{1,r_{1}},\mathcal{S}_{r_{2},1})+r_{1}+s_{2}-3$

and

$\operatorname{\overline{R}}(\mathcal{S}_{r_{1},s_{1}},\mathcal{S}_{r_{2},s_{2}})=\operatorname{\overline{R}}(\mathcal{S}_{r_{1},1},\mathcal{S}_{r_{2},s_{2}})+\operatorname{\overline{R}}(\mathcal{S}_{1,s_{1}},\mathcal{S}_{r_{2},s_{2}})-1.$

Now we show Theorem 6 which says that ordered Ramsey numbers of an arbitrary
collection of ordered stars are linear with respect to the size of the stars.
Formally, let $c,r_{1},\ldots,r_{c},s_{1},\ldots,s_{c}$ be positive integers
and let $\mathcal{S}_{r_{1},s_{1}},\ldots,\mathcal{S}_{r_{c},s_{c}}$ be
ordered stars. Then there is a positive integer $C=C(c)$ such that

$\operatorname{\overline{R}}(\mathcal{S}_{r_{1},s_{1}},\ldots,\mathcal{S}_{r_{c},s_{c}})\leq
C\cdot\max\\{r_{1},\ldots,r_{c},s_{1},\ldots,s_{c}\\}.$

###### Proof of Theorem 6.

Let $r\mathrel{\mathop{:}}=\max\\{r_{1},\ldots,r_{c},s_{1},\ldots,s_{c}\\}$
and let $\mathcal{K}_{N}$ be an ordered complete graph on
$N\mathrel{\mathop{:}}=Cr$ vertices with edges colored with colors from
$\\{1,2,\ldots,c\\}$ where $C$ is a sufficiently large positive integer. Let
$A_{0}$ be the vertex set of $\mathcal{K}_{N}$. We want to find a copy of
$\mathcal{S}_{r,r}$ of color $i$ for some $i\in\\{1,\ldots,c\\}$, as then
there is a copy of $\mathcal{S}_{r_{i},s_{i}}\subseteq\mathcal{S}_{r,r}$ of
color $i$ in $\mathcal{K}_{N}$. So suppose for a contradiction that there is
no monochromatic copy of $\mathcal{S}_{r,r}$ in $\mathcal{K}_{N}$.

Note that every vertex which is at least $(c(r-1)+2)$th in the ordering of
$\mathcal{K}_{N}$ (taken from left) has, according to the pigeonhole
principle, at least $r-1$ left neighbors of the same color. Thus we have at
least $Cr-c(r-1)-1$ vertices with at least $r-1$ monochromatic left neighbors.
We consider a set $A_{1}$ of vertices which have at least $r-1$ left neighbors
of color $1$. Without loss of generality we may assume that
$|A_{1}|\geq(Cr-c(r-1)-1)/c$.

From the assumption there is no vertex in $A_{1}$ with at least $r-1$ right
neighbors of color $1$, as otherwise we would have $\mathcal{S}_{r,r}$ of
color $1$. Thus between vertices in $A_{1}$ there is less than $(r-1)|A_{1}|$
edges of color $1$, since every one of them is counted for its left endpoint.
Also we see that $A_{1}$ contains at least $(|A_{1}|-(c(r-1)-1))/c$ vertices
which have at least $r-1$ right neighbors in $A_{1}$ all of the same color $i$
(without loss of generality, let $i=2$). We denote this set as $A_{2}$. From
the assumption the vertices in $A_{2}$ have less than $r-1$ left neighbors of
color $2$ in $\mathcal{K}_{N}$ and thus there is less than $(r-1)|A_{2}|$
edges of color $2$ (and $1$, since $A_{2}\subseteq A_{1}$) between vertices in
$A_{2}$.

We repeat this process analogously, bounding the number of edges of colors
$1,\ldots,i$ in $A_{i}$ by $(r-1)|A_{i}|$ and keeping
$|A_{i}|\geq(|A_{i-1}|-c(r-1)-1)/c$ for $i\geq 1$. After all colors are
processed we get, summing over all colors, that the number of all edges is
strictly less than $c(r-1)|A_{c}|$. The total number of edges connecting
vertices from $A_{i}$ is exactly ${|A_{i}|\choose 2}$. Altogether, we obtain
$|A_{c}|(|A_{c}|-1)/2<c(r-1)|A_{c}|$ which can be rewritten as
$|A_{c}|<2c(r-1)+1$. However $|A_{c}|=\Omega(Cr/c^{c})$ and thus we can choose
$C$ large enough so that the upper bound on $A_{c}$ does not hold and obtain a
contradiction. ∎

We know that Ramsey numbers for unordered stars and ordered Ramsey numbers of
$\mathcal{S}_{1,r}$ and $\mathcal{S}_{r,1}$ are linear even with respect to
the number of colors. The following proposition shows that this is not the
case for other orderings of stars.

######  Proposition 15.

Let $c$, $r_{1},\ldots,r_{c}$, and $d\geq 3$ be positive integers and let
$\mathcal{G}_{1},\ldots,\mathcal{G}_{c}$ be ordered graphs such that
$(P_{d},\lhd_{mon})\subseteq\mathcal{G}_{i}$ and every $\mathcal{G}_{i}$ has
$r_{i}$ vertices for every $i=1,\ldots,c$. Then we have

$\operatorname{\overline{R}}(\mathcal{G}_{1},\ldots,\mathcal{G}_{c})>(d-1)^{c-1}(\max\\{r_{1},\ldots,r_{c}\\}-1).$

###### Proof.

For $r\mathrel{\mathop{:}}=\max\\{r_{1},\ldots,r_{c}\\}$, let
$\mathcal{K}_{N}$ be an ordered complete graph with
$N\mathrel{\mathop{:}}=(d-1)^{c-1}(r-1)$. Without loss of generality, we
assume $r=r_{1}$. We construct a $c$-coloring of the edges of
$\mathcal{K}_{N}$ with colors from the set $\\{1,\ldots,c\\}$ such that there
is no copy of $\mathcal{G}_{i}$ of color $i$ in $\mathcal{K}_{N}$ for every
$i=1,\ldots,c$.

The coloring is constructed by induction on $c$. For $c=1$ we have
$\mathcal{K}_{r-1}$ with all edges colored $1$. For $c>1$ we partition the
vertex set of $\mathcal{K}_{n}$ into $d-1$ consecutive intervals each of size
$(d-1)^{(c-2)}(r-1)$. Every such interval induces a clique which we color with
the $(c-1)$-coloring obtained in the previous step. Then we color all edges
between distinct cliques with the color $c$ and obtain a $c$-coloring of all
edges of $\mathcal{K}_{N}$. See Figure 5.

Clearly, the $1$-coloring of $K_{r-1}$ avoids a copy of $\mathcal{G}_{1}$ of
color $1$. Using the inductive hypothesis, it suffices to show that the
constructed $c$-coloring of $\mathcal{K}_{N}$, $c>1$, avoids a copy of
$\mathcal{G}_{c}$ in color $c$. This follows from the fact that
$(P_{d},\lhd_{mon})$ is an ordered subgraph of $\mathcal{G}_{c}$, while
$(P_{d},\lhd_{mon})$ is not contained in the ordered graph
$\mathcal{K}_{(d-1)^{(c-2)}(r-1)}(d-1)$ which is induced by the edges colored
with $c$. ∎

Figure 5: The construction in the proof of Proposition 15 for $d=3$ and $c=4$.

######  Corollary 16.

Let $c$ and $r_{1},\ldots,r_{c},s_{1},\ldots,s_{c}\geq 2$ be positive
integers. Then we have

$\operatorname{\overline{R}}(\mathcal{S}_{r_{1},s_{1}},\ldots,\mathcal{S}_{r_{c},s_{c}})>2^{c-1}(\max\\{r_{1}+s_{1}-1,\ldots,r_{c}+s_{c}-1\\}-1).\qed$

######  Corollary 17.

Let $c$ and $r_{1},\ldots,r_{c}\geq 3$ be positive integers and let
$\mathcal{G}_{1},\ldots,\mathcal{G}_{c}$ be ordered graphs on
$r_{1},\ldots,r_{c}$ vertices respectively. If no $\mathcal{G}_{i}$ has a
bipartite underlying graph, then we have

$\operatorname{\overline{R}}(\mathcal{G}_{1},\ldots,\mathcal{G}_{c})>2^{c-1}(\max\\{r_{1},\ldots,r_{c}\\}-1).$

###### Proof.

According to Proposition 15, it suffices to show that $(P_{3},\lhd_{mon})$ is
contained in every given ordered graph $\mathcal{G}_{i}$. Every
$\mathcal{G}_{i}$ contains an ordered odd cycle, as its underlying graph is
not bipartite. The rest follows from the fact that every ordered odd cycle
contains $(P_{3},\lhd_{mon})$. ∎

###  2.2 Paths

In the unordered case, the problem of finding the exact formula for
$\operatorname{R}(P_{r},P_{s})$ has been settled by Gerencsér and Gyárfás [23]
who showed that we have

$\operatorname{R}(P_{r},P_{s})=s-1+\left\lfloor\frac{r}{2}\right\rfloor$

for $2\leq r\leq s$. The multi-color case turned out to be more difficult, but
some partial results are known, see [19, 25].

In this section we show an ordering of the path $P_{n}$ whose ordered Ramsey
number is linear in $n$. Let $v_{1},\ldots,v_{n}$ be vertices of the path
$P_{n}$ and let $\\{v_{1},v_{2}\\}$,
$\\{v_{2},v_{3}\\},\ldots,\\{v_{n-1},v_{n}\\}$ be the edges of $P_{n}$. We
define an alternating path $(P_{n},\lhd_{alt})$ as an ordered path with
$v_{1}\lhd_{alt}v_{3}\lhd_{alt}v_{5}\lhd_{alt}\ldots\lhd_{alt}v_{n}\lhd_{alt}v_{n-1}\lhd_{alt}v_{n-3}\lhd_{alt}\ldots\lhd_{alt}v_{2}$
for $n$ odd and
$v_{1}\lhd_{alt}v_{3}\lhd_{alt}v_{5}\lhd_{alt}\ldots\lhd_{alt}v_{n-1}\lhd_{alt}v_{n}\lhd_{alt}v_{n-2}\lhd_{alt}\ldots\lhd_{alt}v_{2}$
for $n$ even. See part a) of Figure 6. Note that, unlike monotone paths, the
alternating path $(P_{n},\lhd_{alt})$ is an ordered subgraph of
$\mathcal{K}_{\lceil n/2\rceil,\lfloor n/2\rfloor}$.

Figure 6: The alternating path $(P_{7},\lhd_{alt})$ and its corresponding
matrix $M(P_{7},\lhd_{alt})$.

######  Proposition 18.

For every positive integer $n>2$ we have

$2n-2\leq\operatorname{\overline{R}}((P_{n},\lhd_{alt});2)\leq(4n-3+\sqrt{8n^{2}-8n-7})/2.$

Thus the numbers $\operatorname{\overline{R}}(P_{n},\lhd_{alt};2)$ are linear
in $n$. By Proposition 2, the ordered Ramsey numbers
$\operatorname{\overline{R}}((P_{n},\lhd_{mon});2)$ grow quadratically with
respect to $n$. Thus there are two orderings of $P_{n}$ such that the
corresponding ordered Ramsey numbers differ in an asymptotically relevant
term.

A similar result can be derived by considering a matching $M_{n}$, which is a
graph on $n$ vertices consisting of $\lfloor n/2\rfloor$ disjoint pairs of
edges, and the two orderings of $M_{n}$ from Figure 7. Using a coloring
similar to the one from Proposition 2, we see that ordered Ramsey numbers of
the first ordered matching grow quadratically with respect to $n$ while for
the second one its ordered Ramsey number remains linear in $n$. For other
orderings of $M_{n}$ the asymptotic difference can be much larger, see Theorem
9.

Figure 7: Two orderings of $M_{n}$ with asymptotically different ordered
Ramsey numbers.

To prove Proposition 18 we use a result from extremal theory of
$\\{0,1\\}$-matrices which was mentioned in the motivation (Section 1.1). The
following definitions are taken from [9]. We say that an $r\times s$ matrix
$M$ is minimalist if $\operatorname{ex}_{M}(m,n)=(s-1)m+(r-1)n-(r-1)(s-1)$. If
the matrix $M^{\prime}$ was created from a matrix $M$ by adding a new row (or
a column) as the new first or last row (column) and this new row (column)
contains a single 1-entry next to a 1-entry of $M$, then we say the
$M^{\prime}$ was created by an elementary operation from $M$.

######  Lemma 19 ([22]).

Let $M$ be an $r\times s$ minimalist matrix and let $M^{\prime}$ be an
$r^{\prime}\times s^{\prime}$ nonempty matrix obtained from $M$ by applying
several elementary operations. Then $M^{\prime}$ is minimalist.

###### Proof of proposition 18.

For the lower bound we color the edge between the $i$th and $j$th vertex of
$\mathcal{K}_{2n-3}$ red if $|i-j|$ is even and blue otherwise. Suppose that
there is a red copy of $(P_{n},\lhd_{alt})$ in this coloring. Then the number
of vertices between the first and the last vertex of this alternating path is
at least $2n-4$. This is not possible, as there are only $2n-3$ vertices in
total. An analogous argument works for a blue copy of $(P_{n},\lhd_{alt})$.

Let $N$ be an integer satisfying $N\geq(4n-3+\sqrt{8n^{2}-8n-7})/2$. To show
the upper bound we find a monochromatic copy of $(P_{n},\lhd_{alt})$ in the
given graph $\mathcal{K}_{\lceil N/2\rceil,\lfloor N/2\rfloor}$ with 2-colored
edges. Without loss of generality, at least half of the edges are red. Since
$(P_{n},\lhd_{alt})$ is an ordered subgraph of $\mathcal{K}_{\lceil
N/2\rceil,\lfloor N/2\rfloor}$, we can consider the $\lceil
n/2\rceil\times\lfloor n/2\rfloor$ $\\{0,1\\}$-matrix $M(P_{n},\lhd_{alt})=M$
introduced in the motivation. An example of such a matrix can be found in
Figure 6, part b). By Lemma 19, all such matrices are minimalist.

Therefore we have

$\operatorname{ex}_{M}(\lceil N/2\rceil,\lfloor N/2\rfloor)=(\lfloor
n/2\rfloor-1)\lceil N/2\rceil+(\lceil n/2\rceil-1)\lfloor N/2\rfloor-(\lceil
n/2\rceil-1)(\lfloor n/2\rfloor-1)$

and this is at most $\frac{1}{4}(2nN+4n-3N-4-n^{2})$. Thus every $K_{\lceil
N/2\rceil,\lfloor N/2\rfloor}$ which does not contain $(P_{n},\lhd_{alt})$ as
an ordered subgraph must contain at most that many edges. On the other hand,
our graph formed by red edges has at least $\frac{1}{2}\lceil
N/2\rceil\cdot\lfloor N/2\rfloor\geq N(N-1)/8$ edges. Thus to avoid
$(P_{n},\lhd_{alt})$ the inequality

$\frac{2nN+4n-3N-4-n^{2}}{4}\geq N(N-1)/8$

must be satisfied. Consequently, we obtain $N\leq(4n-5+\sqrt{8n^{2}-8n-7})/2$
and the result follows. ∎

There is still a place for improvement, as the multiplicative factor in
$\operatorname{\overline{R}}((P_{n},\lhd_{alt});2)$ is between $2$ and
$2+\sqrt{2}$. Computer experiments indicate that the right values of
$\operatorname{\overline{R}}(P_{n},\lhd_{alt};2)$ could be of the form
$\lfloor(n-2)\frac{1+\sqrt{5}}{2}\rfloor+n$. See Table 1.

$n$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$
---|---|---|---|---|---|---|---|---|---|---|---|---
$\operatorname{\overline{R}}((P_{n},\lhd_{alt});2)$ | $2$ | $4$ | $7$ | $9$ | $12$ | $15$ | $17$ | $\geq 20$ | $\geq 22$ | $\geq 25$ | $\geq 28$ | $\geq 30$
Table 1: Estimates for Ramsey numbers
$\operatorname{\overline{R}}((P_{r},\lhd_{alt});2)$ for $r\leq 13$.

For general ordered paths not much is known currently. Cibulka et al. [10]
showed that for every ordered path $\mathcal{P}_{r}$ and the clique
$\mathcal{K}_{s}$ we have

$\operatorname{\overline{R}}(\mathcal{P}_{r},\mathcal{K}_{s})\leq
2^{\lceil\log s\rceil(\lceil\log r\rceil+1)}.$

That is, for every ordered path $\mathcal{P}_{n}$ we have
$\operatorname{\overline{R}}(\mathcal{P}_{n};2)\leq n^{O(\log n)}$.

###  2.3 Cycles

It is a folklore result in Ramsey theory that
$\operatorname{R}(C_{3};2)=\operatorname{R}(C_{4};2)=6$ holds [8]. The first
results on Ramsey numbers of cycles were obtained by Chartrand and Chuster
[5], and Bondy and Erdős [3]. These were later extended by Rosta [37], and
Faudree and Schelp [18]. Eventually, the Ramsey numbers for cycles in the two-
color case were completely determined:

$\operatorname{R}(C_{r},C_{s})=\begin{cases}2r-1&\textrm{if
}(r,s)\neq(3,3)\textrm{ and }3\leq s\leq r,s\textrm{ is odd},\\\
r+s/2-1&\textrm{if }(r,s)\neq(4,4)\textrm{ and }4\leq s\leq r,r\textrm{ and
}$s$\textrm{ are even},\\\ \max\\{r+s/2-1,2s-1\\}&\textrm{if }4\leq
s<r,s\textrm{ is even and }r\textrm{ is odd}.\end{cases}$

The multicolor case is more demanding [14, 32, 33], but the following is
known.

######  Theorem 20 ([33]).

For every $c\geq 4$ and $n$ odd, we have $\operatorname{R}(C_{n};c)\leq
c2^{c}n+o(n)$, and for every $c\geq 2$ and $n$ even, we have
$\operatorname{R}(C_{n};c)\leq cn+o(n)$ as $n\to\infty$.

For ordered cycles, the first nontrivial case is $C_{4}$ which has three
possible orderings up to isomorphism. See Figure 8. In the following, we
determine the ordered Ramsey numbers for all orderings of $C_{4}$.

Figure 8: Possible orderings of $C_{4}$.

######  Proposition 21.

We have

  1. 1.

$\operatorname{\overline{R}}((C_{4},\prec_{A});2)=14$,

  2. 2.

$\operatorname{\overline{R}}((C_{4},\prec_{B});2)=10$,

  3. 3.

$11\leq\operatorname{\overline{R}}((C_{4},\prec_{C});2)\leq 13$.

###### Proof.

The lower bounds follow from the colorings presented in Figure 9, thus it
remains to show the upper bounds for each ordering. Suppose that
$\mathcal{K}_{N}$ is an ordered complete graph with 2-colored edges (red and
blue) where $N$ is relevant to each case.

Figure 9: Colorings for the lower bounds in the proof of Proposition 21.

  1. 1.

This result is implied by more general statement, Theorem 7, which is proved
bellow.

  2. 2.

Assume for a contradiction that $\mathcal{K}_{10}$ does not contain a
monochromatic copy of $(C_{4},\prec_{B})$. That is, no two vertices of
$\mathcal{K}_{10}$ share two right neighbors of the same color. We claim that
there is no vertex with monochromatic right degree greater than five in the
coloring of $\mathcal{K}_{10}$.

Otherwise there is, without loss of generality, a vertex $v$ with right red
degree at least six. Let $R$ be the set of the right red neighbors of $v$. The
leftmost vertex $w$ of $R$ has a blue right degree at least four, as it cannot
have more than one red right neighbor in $R$. However then the blue
neighborhood of $w$ contains a vertex with either red or blue right degree at
least two. In any case we obtain $(C_{4},\prec_{B})$.

Thus every vertex has monochromatic right degree of size at most five. From
the assumptions, every pair of vertices has at most one common right neighbor
in every color. Without loss of generality we assume that the first vertex
$v_{1}$ in $\mathcal{K}_{10}$ has a red right degree five and a blue right
degree four.

The second vertex $v_{2}$ in $\mathcal{K}_{10}$ has at most one (right) red
neighbor among the red neighbors of $v_{1}$ and the remaining at least three
are its blue neighbors. Then the third vertex $v_{3}$ has at least two common
right monochromatic neighbors either with $v_{1}$ or $v_{2}$ between these
three vertices.

  3. 3.

The first vertex $v_{1}$ in $\mathcal{K}_{13}$ has either six blue and six red
neighbors, or at least seven monochromatic neighbors. In any case, since every
pair of vertices can have at most a single common neighbor of the same color
between them, there is, without loss of generality, at least five vertices
which are red right neighbors of $v_{1}$ and blue left neighbors of $v_{13}$.
By Theorem 14 we have
$\operatorname{\overline{R}}(\mathcal{S}_{1,3},\mathcal{S}_{3,1})=5$.
Therefore we find either a vertex with red left degree at least two or a
vertex with blue right degree at least two in the clique formed by those five
vertices. In both cases we obtain a monochromatic copy of $(C_{4},\prec_{C})$.

∎

Using exhaustive computer search, we have derived that the lower bound in the
third case is tight, i.e.,
$\operatorname{\overline{R}}((C_{4},\prec_{C});2)=11$ holds.

In the rest of the section we establish the precise value of ordered Ramsey
numbers for monotone cycles. Specifically, we prove the equality

$\operatorname{\overline{R}}((C_{r},\lhd_{mon}),(C_{s},\lhd_{mon}))=2rs-3r-3s+6$

for every $r,s\geq 2$. Note that this formula is somewhat simpler than the one
for $\operatorname{R}(C_{r},C_{s})$.

The following lemma is a simple observation which is implicitly proved in
[27]. We include its proof for completeness.

######  Lemma 22.

For positive integers $r$ and $s$, we have

$\operatorname{\overline{R}}((P_{r},\lhd_{mon}),\mathcal{K}_{s})=\operatorname{\overline{R}}((P_{r},\lhd_{mon}),(P_{s},\lhd_{mon}))=(r-1)(s-1)+1.$

###### Proof.

The lower bound can be obtained from the same construction as in the proof of
Proposition 2, see [38]. For the upper bound we use induction on $r$. If
$r=2$, then this statement holds since we either have a monochromatic copy of
$\mathcal{K}_{s}$, or a blue edge. Suppose that $r>2$ and let
$\mathcal{K}_{(r-1)(s-1)+1}$ be an ordered complete graph with edges colored
red and blue. Assume that it does not contain a blue copy of $\mathcal{K}_{s}$
nor a red copy of $(P_{r},\lhd_{mon})$. Using the inductive hypothesis, we
know that there is at least

$(r-1)(s-1)+1-(r-2)(s-1)=s$

distinct vertices which are the last vertices of a red copy of
$(P_{r-1},\lhd_{mon})$. From the assumption every edge between such vertices
is blue, otherwise we would extend one of these paths. However this yields a
blue copy of $K_{s}$, a contradiction. ∎

A simple corollary is that for every $s$-vertex ordered graph $\mathcal{G}$
which contains a monotone Hamiltonian path we have
$\operatorname{\overline{R}}((P_{r},\lhd_{mon}),\mathcal{G})=(r-1)(s-1)+1$.

###### Proof of Theorem 7.

First, we show the upper bound which can be also derived from the results of
Károlyi et al. [28] who studied geometric Ramsey numbers of cycles.

In an ordered complete graph $\mathcal{K}_{N}$ with 2-colored edges and with
$N\mathrel{\mathop{:}}=2rs-3r-3s+6$ vertices the first vertex $v_{1}$ has
either at least $(r-2)(s-1)+1$ red neighbors or at least $(r-1)(s-2)+1$ blue
neighbors. In the first case there is, according to Lemma 22, a red copy of
$(P_{r-1},\lhd_{mon})$ which forms red $(C_{r},\lhd_{mon})$ together with
$v_{1}$ or a blue copy of $(C_{s},\lhd_{mon})$. The second case with large
blue neighborhood is analogous and we thus always get either red
$(C_{r},\lhd_{mon})$ or blue $(C_{s},\lhd_{mon})$.

For the lower bound we show a coloring of $(K_{N},\prec)$ where
$N\mathrel{\mathop{:}}=2rs-3r-3s+5$, which avoids a red copy of
$(C_{r},\lhd_{mon})$ and a blue copy of $(C_{s},\lhd_{mon})$. An example of
such coloring for $r=s=4$ can be found in Figure 9, part a).

Consider a partition of the vertex set of $(K_{N},\prec)$ into the following
consecutive (in the ordering $\prec$) intervals $I_{i}$, $i=1,2,\ldots,2r-3$.
If $r$ is odd, then the first and last $(r-1)/2$ intervals $I_{i}$ in $\prec$
have size $s-1$ and the remaining $r-2$ intervals $I_{i}$ have size $s-2$. If
$r$ is even, then the first and last $(r-2)/2$ intervals $I_{i}$ contain $s-2$
vertices and the remaining $r-1$ intervals $I_{i}$ have $s-1$ vertices. Note
that in both cases we have $N$ vertices in total. We assume that the vertices
of $I_{i}$ are of the form $v^{i}_{j}$ where $j=1,\ldots,|I_{i}|$ and
$v^{i}_{j}\prec v^{i}_{k}$ whenever $j<k$. We also refer to the index $j$ as
the index of a vertex $v^{i}_{j}$.

The coloring of the edges is defined as follows. First, we color all edges
between vertices from the same interval $I_{i}$ blue. Next, we introduce four
types of pairs $(I_{i},I_{j})$, $i<j$, according to which we color edges
between vertices from intervals $I_{i}$ and $I_{j}$. We say that
$(I_{i},I_{j})$, $i<j$, is of the type:

  * •

$T_{<}$ if $j-i\leq r-2$ and $|I_{i}|\leq|I_{j}|$. In this case we color an
edge $\\{v^{i}_{k},v^{j}_{l}\\}$ blue if $k<l$ and red otherwise.

  * •

$T_{\geq}$ if $j-i>r-2$ and $|I_{i}|<|I_{j}|$. Then an edge
$\\{v^{i}_{k},v^{j}_{l}\\}$ is colored blue if $k\geq l$ and red otherwise.

  * •

$T_{>}$ if $j-i>r-2$ and $|I_{i}|\geq|I_{j}|$. Then an edge
$\\{v^{i}_{k},v^{j}_{l}\\}$ is colored blue if $k>l$ and red otherwise.

  * •

$T_{\leq}$ if $j-i\leq r-2$ and $|I_{i}|>|I_{j}|$. Then an edge
$\\{v^{i}_{k},v^{j}_{l}\\}$ is colored blue if $k\leq l$ and red otherwise.

The main idea is that for the types $T_{<}$ and $T_{\leq}$ we color blue the
edges between vertices such that their indices are increasing or non-
decreasing (i.e., those vertices are relatively far from each other), while
for $T_{>}$ and $T_{\geq}$ the indices are decreasing or non-increasing (such
vertices are relatively close to each other). For red edges, the indices
behave exactly opposite. The distribution of the types of pairs, as well as
the definition of those types, is illustrated on small examples in the
following two figures.

Figure 10: The types of pairs $(I_{i},I_{j})$ for $s=5$ and colorings of
corresponding edges. Figure 11: Distribution of types of pairs $(I_{i},I_{j})$
for $r=3$ (part a) and $r=4$ (part b).

It remains to show that this coloring avoids forbidden cycles. We claim that
our coloring does not contain a red copy of $(C_{r},\lhd_{mon})$. To prove
this claim, suppose for a contradiction that there is such a copy. Note that
it contains at most one vertex from every interval $I_{i}$, because the
intervals induce blue cliques. The monotone path of length $r$ induced by a
red cycle also cannot have an edge which connects vertices from $I_{i}$ and
$I_{j}$ where $(I_{i},I_{j})$ is of type $T_{>}$ or $T_{\geq}$, because in
both cases we skip vertices from at least $r-2$ intervals $I_{k}$. This leaves
at most $2r-3-(r-2)=r-1$ intervals and from each such interval we can use a
single vertex. However this is not possible, as $(C_{r},\lhd_{mon})$ contains
$r$ vertices. Hence the vertex indices on this monotone path are non-
increasing, as the path uses red edges between pairs $(I_{i},I_{j})$ only of
types $T_{<}$ or $T_{\leq}$.

Since the number of intervals $I_{i}$ of size $s-1$ as well as the number
intervals of size $s-2$ is less than $r$, we must use vertices from both of
those variants. If we have an edge between $(I_{i},I_{j})$ of type $T_{\leq}$
in the monotone path, then the vertex indices decrease at least once (as they
are connected with a red edge). However the longest edge in our red cycle is
between intervals of type $T_{>}$ or $T_{\geq}$ and thus it connects vertices
whose indices are non-decreasing. This is a contradiction, because from our
observations their indices should decrease.

The other possibility is that all edges of the red monotone path are between
pairs of types $T_{<}$. Then the longest edge of the red cycle is of type
$T_{\geq}$, because it has to connect $I_{i}$ with $I_{j}$ where
$|I_{i}|<|I_{j}|$. Here we have used the specific distribution of small and
large intervals $I_{i}$. However then the vertex indices have to increase at
least once and we already observed that this is not possible. A contradiction.

Now we prove that there is no blue copy of $(C_{s},\lhd_{mon})$ in the
coloring. Again, suppose that there is such a blue cycle. This time, we can
use edges whose both endpoints are in the same $I_{i}$. However the blue cycle
has to use vertices from at least two intervals $I_{i}$, because neither of
them contains $s$ vertices. We distinguish a few cases.

  1. 1.

Suppose first that the blue monotone path of length $s$ does not contain an
edge between a pair $(I_{i},I_{j})$ of type $T_{>}$ or $T_{\geq}$. Then the
vertex indices are non-decreasing. According to the distribution of small and
large intervals $I_{i}$, there is at most one edge between vertices with the
same vertex index. Such an edge corresponds to a jump from a larger $I_{i}$ to
a smaller $I_{j}$, i.e., a pair of type $T_{\leq}$. Therefore the length of
every such blue monotone path is at most vertex index of its last vertex plus
one, where the additional one is added only when we use the previously
described jump. Since every vertex has index at most $s-1$, we see that the
path uses exactly one pair of type $T_{\leq}$. Then the vertices of the path
cannot remain in the smaller intervals $I_{i}$, as their indices would be at
most $s-2$. However then the edge $e$ between the first and the last vertex of
the path must be of type $T_{>}$, because we need to jump from a larger
interval to a smaller one and then conversely (for $r$ even this is already
impossible). That is, $e$ connects vertices from $I_{i}$ and $I_{j}$ where
$|I_{i}|=|I_{j}|$ and $j-i>r-2$. Consequently, the indices on the path
decrease at least once which is impossible.

  2. 2.

The second case to analyze is when the blue monotone path uses (exactly once)
an edge $e$ between $I_{i}$ and $I_{j}$ with $j-i>r-2$, i.e., a pair of type
$T_{>}$ or $T_{\geq}$. Such an edge is at most one, as it skips at least $r-2$
intervals while we have only $2r-3$ intervals in total. All the other edges of
the path are either between pairs $(I_{i},I_{j})$ of types $T_{<}$ or
$T_{\leq}$ or they connect vertices from the same interval. That is, except of
the edge $e$ the indices of all other vertices are non-decreasing and the only
case when vertex indices are not increasing is when we jump from a larger
interval to a smaller one. This can happen at most once, as we have already
observed. The construction implies that the longest edge of the blue monotone
cycle is between a pair of type $T_{>}$ or $T_{\geq}$, therefore the index of
the last vertex is at most as large as the index of the first vertex.

    1. (a)

Suppose that the path does not use a pair of type $T_{\leq}$. Then the indices
on the path increase by at least $s-2$, as we use $s-2$ pairs of type $T_{<}$
or edges within the same $I_{i}$. The only possibility for the indices to
decrease is on the edge of type $T_{>}$, because the decrease must be by at
least $s-2$. Thus we need to jump from a vertex with index $s-1$ to a vertex
with index $1$. We cannot do this with an edge of type $T_{\geq}$, as it jumps
from a smaller interval where the indices are at most $s-2$. Now, consider the
longest edge in the cycle. It must be of type $T_{>}$ or $T_{\geq}$ as it
skips at least $r-2$ intervals. However neither of the possibilities can
occur. The edge of type $T_{>}$ would connect vertices whose indices decrease,
but the last vertex has index of size at least as large as the index of the
first one, according to the size of the total decrease and increase. The
longest edge of type $T_{\geq}$ would connect a vertex from a smaller interval
with a vertex from larger and this is impossible according to the distribution
of the intervals, since we have used an edge of type $T_{>}$ on the path.

    2. (b)

Assume that we have used (exactly once) an edge of type $T_{\leq}$ to jump
between vertices whose indices are the same. Such an edge connects a larger
interval with a smaller one and thus, according to their distribution, the
longest edge in the cycle is of type $T_{>}$. This means that the index of the
first vertex is strictly larger than the index of the last one. The total
decrease of indices must be also strictly larger than their increase which is
at least $s-3$, as at least $s-3$ edges of the path are of type $T_{<}$ or are
between edges from the same $I_{i}$. To finish the proof, note that we cannot
use an edge of type $T_{>}$ on the path together with the edge of type
$T_{\leq}$. This is again because of the distribution of the intervals. Thus
the total decrease is at most $s-3$, as edges of type $T_{\geq}$ jump from a
smaller to a larger interval.

∎

Note that we have proved a stronger statement, because in our coloring no red
monotone cycle of length at least $r$ nor a blue monotone cycle of length at
least $s$ can appear. It could be interesting to extend this theorem to a
multicolored case.

As noted by Cibulka et al. [10], the constructed coloring can be used to show
the exact formula for geometric and convex geometric Ramsey numbers for cycles
(see Section 1.1 for definitions).

######  Corollary 23.

For every integer $n\geq 3$, we have
$\operatorname{Rc}(C_{n})=\operatorname{Rg}(C_{n})=2(n-2)(n-1)+2$.

###### Proof.

According to the upper bound of Károlyi et al. [28] and the fact
$\operatorname{Rc}(C_{n})\leq\operatorname{Rg}(C_{n})$, it suffices to show
that $\operatorname{Rc}(C_{n})\geq 2(n-2)(n-1)+2$ which is an immediate
corollary of Observation 5 and Theorem 7. ∎

##  3 Lower bounds

The following proposition, whose proof is based on a standard existence
argument, gives us a general lower bound on Ramsey numbers of ordered graphs.
Using this result, we can derive a lower bound for dense graphs which is
exponential in the number of vertices. Proposition 8 is a special case of this
assertion since a graph $G$ on $n$ vertices with $\Omega(n^{1+\varepsilon})$
edges for some $\varepsilon>0$ satisfies
$\operatorname{\overline{R}}((G,\prec);2)=\Omega(n2^{n^{\varepsilon}})$ for
every vertex ordering $\prec$ of $G$.

######  Proposition 24.

Let $c$, $r$, and $s$ be positive integers and let
$\prec_{1},\ldots,\prec_{c}$ be vertex orderings of a graph $G$ with $n$
vertices and $m$ edges. Then we have

$\operatorname{\overline{R}}((G,\prec_{1}),\ldots,(G,\prec_{c}))\geq({2\pi
n})^{1/n}\left(\frac{n}{e}\right)c^{(m-1)/n}$

where $e$ is the base of the natural logarithm.

###### Proof.

Let $(K_{N},\prec)$ be a complete ordered graph and let $G=(V,E)$ be the given
graph. We $c$-color the edges of $(K_{N},\prec)$ independently at random with
probability $1/c$ for each color. The probability that a set $S\subset V$ of
size $n$ induces a copy of $(G,\prec_{i})$ in color $i$ is $(1/c)^{m}$, since
the ordering $\prec_{i}$ determines the set of edges of $(G,\prec_{i})$.

Using the Union bound we derive

$\displaystyle\Pr[\textrm{there is }i\in\\{1,\ldots,c\\}$
$\displaystyle\textrm{ such that }(G,\prec_{i})\subseteq(K_{N},\prec)\textrm{
in color }i]\leq{N\choose{n}}\cdot c\cdot\left(\frac{1}{c}\right)^{m}=$
$\displaystyle{N\choose{n}}\left(\frac{1}{c}\right)^{m-1}\leq\frac{N^{n}}{n!}\left(\frac{1}{c}\right)^{m-1}.$

With Stirling’s approximation formula $k!=\sqrt{2\pi
k}\left(\frac{k}{e}\right)^{k}\cdot(1+o(1))$ we can bound this probability
from above by

$\frac{N^{n}}{\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}c^{m-1}}.$

This expression is strictly smaller than 1 for $N<\sqrt[n]{2\pi
n}(n/e)c^{(m-1)/n}$. Therefore for such $N$ there exists a $c$-coloring of
edges of $(K_{N},\prec)$ which avoids $(G,\prec_{i})$ for all $i=1,\ldots,c$.
∎

###  3.1 Proof of Theorem 9

So far we have seen examples of ordered paths and matchings where the ratio
between ordered and unordered Ramsey numbers grew linearly with $n$. Now we
show a much stronger estimate, Theorem 9, which says that there are
arbitrarily large ordered matchings $\mathcal{M}$ with $n$ vertices satisfying
$\operatorname{\overline{R}}(\mathcal{M};2)=n^{\Omega(\log n/5\log\log n)}$.

Let $r\geq 3$ be a positive integer and let
$R\mathrel{\mathop{:}}=\operatorname{R}(K_{r};2)-1$. We construct a sequence
of ordered matchings $\mathcal{M}_{k}$ with $n_{k}$ vertices and a sequence of
$2$-colorings $c_{k}$ of ordered complete graphs $\mathcal{G}_{k}$ with
$N_{k}$ vertices such that $c_{k}$ avoids a monochromatic copy of
$\mathcal{M}_{k}$.

First, we show an inductive construction of the colorings $c_{k}$. Let
$N_{1}\mathrel{\mathop{:}}=R$ and let $c_{1}$ be a $2$-coloring of
$\mathcal{G}_{1}\mathrel{\mathop{:}}=\mathcal{K}_{R}$ avoiding
$\mathcal{K}_{r}$. Let $k\geq 1$ and suppose that a coloring $c_{k}$ of
$\mathcal{G}_{k}$ has been constructed. Let
$N_{k+1}\mathrel{\mathop{:}}=R\cdot N_{k}$ and let $\mathcal{G}_{k}$ be the
complete graph on $N_{k+1}$ vertices. Partition the vertex set of
$\mathcal{G}_{k+1}$ into $R$ disjoint consecutive intervals $I_{1},\allowbreak
I_{2},\allowbreak\dots,\allowbreak I_{R}$, each of size $N_{k}$. Color the
subgraph induced by each $I_{i}$ by $c_{k}$. The remaining edges form a
complete $R$-partite ordered graph $\mathcal{F}_{k+1}$, which can be colored
to avoid $\mathcal{K}_{r}$, in the following way. Suppose that
$v_{1},v_{2},\dots,v_{R}$ are the vertices of $\mathcal{G}_{1}$. Then for
every $i,j$, $1\leq i<j\leq R$, and for every edge $e$ of $\mathcal{F}_{k+1}$
with one vertex in $I_{i}$ and the other vertex in $I_{j}$, let
$c_{k+1}(e)\mathrel{\mathop{:}}=c_{1}(\\{v_{i},v_{j}\\})$. Clearly,
$N_{k}=R^{k}$.

The matchings $\mathcal{M}_{k}$ are also constructed inductively. The basic
building block is a matching $\mathcal{M}$ obtained by splitting the vertices
of $\mathcal{K}_{r}$ completely and taking many shifted copies of the
resulting matching; see Figure 12. More precisely, consider the integers
$1,2,\dots,r^{2}R$ as vertices, and let $l_{i}\mathrel{\mathop{:}}=(i-1)rR$,
for $1\leq i\leq r$. For every pair $i,j$, where $1\leq i<j\leq r$, we add the
$R$ edges
$\\{l_{i}+j,l_{j}+i\\},\allowbreak\\{l_{i}+j+r,l_{j}+i+r\\},\allowbreak\\{l_{i}+j+2r,l_{j}+i+2r\\},\allowbreak\dots,\allowbreak\\{l_{i}+j+(R-1)r,l_{j}+i+(R-1)r\\}$.
Note that the vertices $l_{i}+i+kr$, where $1\leq i\leq r$ and $0\leq k<R$ are
isolated and after their removal, we obtain the ordered matching $\mathcal{M}$
with $t\mathrel{\mathop{:}}=r(r-1)R$ vertices.

Figure 12: The matching $\mathcal{M}$ for $r=3$.

Let $n_{1}\mathrel{\mathop{:}}=t$ and
$\mathcal{M}_{1}\mathrel{\mathop{:}}=\mathcal{M}$. Now let $k\geq 1$ and
suppose that $\mathcal{M}_{k}$ has been constructed. Let $J_{1},\allowbreak
L_{1},\allowbreak J_{2},\allowbreak L_{2},\allowbreak\dots,\allowbreak
L_{r-1},\allowbreak J_{r}$ be an ordered sequence of disjoint intervals of
vertices, of size $|L_{i}|=n_{k}$ and $|J_{i}|=(r-1)R)$. The matching
$\mathcal{M}_{k+1}$ is obtained by placing a copy of $\mathcal{M}_{k}$ on each
of the $r-1$ intervals $L_{i}$ and a copy of $\mathcal{M}$ on the union of the
$r$ intervals $J_{i}$. See Figure 13. We have $n_{k+1}=(r-1)n_{k}+t$.

Figure 13: Construction of $\mathcal{M}_{k+1}$ for $r=3$.

Now we show that for every $k$, the coloring $c_{k}$ of $\mathcal{G}_{k}$
avoids $\mathcal{M}_{k}$. Trivially, $c_{1}$ avoids $\mathcal{M}_{1}$ since
$n_{1}=t>R=N_{1}$. Let $k\geq 1$ and suppose that $c_{k}$ avoids
$\mathcal{M}_{k}$. Let $I_{1},\dots,I_{s}$ be the intervals of vertices from
the construction of $\mathcal{G}_{k+1}$ and let $J_{1},\allowbreak
L_{1},\allowbreak\dots,\allowbreak L_{r-1},\allowbreak J_{r}$ be the intervals
of vertices from the construction of $\mathcal{M}_{k+1}$. Assume that
$\mathcal{M}_{k+1}$ is an arbitrary subgraph of $\mathcal{G}_{k+1}$. If two
intervals $J_{j}$ and $J_{j+1}$ intersect some interval $I_{i}$, then
$L_{j}\subset I_{i}$. Since $L_{j}$ induces $\mathcal{M}_{k}$ in
$\mathcal{M}_{k+1}$ and $I_{i}$ induces $\mathcal{G}_{k}$ colored with $c_{k}$
in $\mathcal{G}_{k+1}$, the matching $\mathcal{M}_{k+1}$ is not monochromatic
by induction. Thus we may assume that every interval $I_{i}$ is intersected by
at most one interval $J_{j}$.

Partition each interval $J_{j}$ into $R$ intervals $J_{j}^{1},\allowbreak
J_{j}^{2},\allowbreak\dots,\allowbreak J_{j}^{R}$ of length $r-1$, in this
order. At most $R-1$ of the $rR$ intervals $J_{j}^{l}$, $1\leq j\leq r$,
$1\leq l\leq R$, contain vertices from at least two intervals $I_{i}$, $1\leq
i\leq R$. Thus there is an $l$ such that for every $j$, $1\leq j\leq r$, the
whole interval $J_{j}^{l}$ is contained in some interval $I_{i(j)}$. Moreover,
all the intervals $I_{i(j)}$ are pairwise distinct by our assumption. By the
construction of $\mathcal{M}_{k+1}$, there is exactly one edge
$e_{j,j^{\prime}}$ in $\mathcal{M}_{k+1}$ between every two intervals
$J_{j}^{l}$ and $J_{j^{\prime}}^{l}$. By the coloring of $\mathcal{F}_{k+1}$,
we have $c_{k+1}(e_{j,j^{\prime}})=c_{1}(\\{v_{i(j)},v_{i(j^{\prime})}\\})$.
Since the edges $\\{v_{i(j)},v_{i(j^{\prime})}\\}$ form a complete subgraph
with $r$ vertices in $\mathcal{G}_{1}$ and $c_{1}$ avoids $\mathcal{K}_{r}$,
we conclude that our copy of $\mathcal{M}_{k+1}$ in $\mathcal{G}_{k+1}$ is not
monochromatic. It follows that $c_{k+1}$ avoids $\mathcal{M}_{k+1}$.

Solving the recurrence for $n_{k}$, we get

$n_{k}=(1+(r-1)+\cdots+(r-1)^{k-1})\cdot t<(r-1)^{k}\cdot t<r^{k+2}\cdot R.$

Let $c\mathrel{\mathop{:}}=(\log{R})/r$. By (1), we have $c\in[1/2,2)$. Let
$k\mathrel{\mathop{:}}=\lfloor(cr/\log{r})-2\rfloor=(cr/\log{r})-2-\varepsilon$,
where $\varepsilon\in[0,1)$. Let $n\mathrel{\mathop{:}}=n_{k}$,
$N\mathrel{\mathop{:}}=N_{k}$ and
$\mathcal{M}_{n}\mathrel{\mathop{:}}=\mathcal{M}_{k}$. We have

$n=n_{k}<r^{k+2}\cdot R\leq 2^{cr+\log R}=2^{2cr}\hskip 8.5359pt\text{ and
}\hskip 8.5359ptN=N_{k}=R^{k}=2^{crk}>2^{(c^{2}r^{2}/\log{r})-3cr}.$

Using these bounds together with the trivial bound $2^{cr}=R<n$, we derive

$\displaystyle\log{N}-\frac{\log^{2}{n}}{5\log\log{n}}$
$\displaystyle>\frac{c^{2}r^{2}}{\log{r}}-3cr-\frac{4c^{2}r^{2}}{5(\log{r}+\log{c})}$
$\displaystyle=c^{2}r^{2}\left(\frac{1}{\log{r}}-\frac{3}{cr}-\frac{4}{5(\log{r}+\log{c})}\right)$
$\displaystyle>0$

if $r$ is large enough. The theorem follows. ∎

We remark that our colorings $c_{k}$ of the graphs $\mathcal{G}_{k}$ are not
constructive, since we use the probabilistic lower bound from Ramsey’s
theorem.

Let us recall that unordered graphs with maximum degree of constant size have
linear Ramsey numbers with respect to the number of vertices. From Theorem 9
we therefore get that the ratio between ordered and unordered Ramsey numbers
of the same graph can grow super-polynomially.

Combining the example of ordered matchings with linear ordered Ramsey numbers
(see the second part of Figure 7) with Theorem 9 we see that there are
$n$-vertex graphs $G_{n}$ with two vertex ordering schemes $\lhd_{1}$ and
$\lhd_{2}$ such that $\operatorname{\overline{R}}(G_{n},\lhd_{1})$ remains
linear while $\operatorname{\overline{R}}(G_{n},\lhd_{2})$ is super-polynomial
in $n$.

##  4 Upper Bounds

This section is divided into two parts. In each part we prove a polynomial
upper bound for ordered Ramsey numbers of a certain class of sparse ordered
graphs.

###  4.1 Proof of Theorem 10

In this part we prove Theorem 10. That is, we show that for fixed positive
integers $k$, $q\geq 2$ and $(k,q)$-decomposable ordered graphs $\mathcal{G}$
and $\mathcal{H}$ we have

$\operatorname{\overline{R}}(\mathcal{G},\mathcal{H})\leq C_{k}\cdot
2^{64k(\lceil\log_{q/(q-1)}{r}\rceil+\lceil\log_{q/(q-1)}{s}\rceil)}$

where $r$ is the number of vertices of $\mathcal{G}$, $s$ is the number of
vertices of $\mathcal{H}$ and $C_{k}$ is a sufficiently large constant
dependent on $k$.

######  Lemma 25.

Let $\mathcal{K}_{N}$ be a complete ordered graph with edges colored red and
blue. Then there is a set $U$ with at least $\lfloor N/(16\cdot
10^{5})\rfloor$ vertices of $\mathcal{K}_{N}$ satisfying one of the following:

  1. 1.

every vertex of $U$ has at least $N/11$ blue neighbors to the left and to the
right of $U$,

  2. 2.

every vertex of $U$ has at least $N/11$ red neighbors to the left and to the
right of $U$.

###### Proof.

We assume $N\geq 16\cdot 10^{5}$, as otherwise the statement is trivial.
First, we show that there is a set $W$ with at least $N/2000$ vertices
satisfying one of the following:

  1. 1.

every vertex of $W$ has at least $\frac{20}{217}N$ blue left and at least
$\frac{20}{217}N$ blue right neighbors,

  2. 2.

every vertex of $W$ has at least $\frac{20}{217}N$ red left and at least
$\frac{20}{217}N$ red right neighbors.

Let $B$ be the set of vertices of $\mathcal{K}_{N}$ that satisfy the first
claim for $W$ and let $R$ be the set of vertices of $\mathcal{K}_{N}$ that
satisfy the second claim for $W$. Suppose that $|B|<N/2000$ and $|R|<N/2000$,
as otherwise we are done.

Consider the complete ordered graph $\mathcal{K^{\prime}}$ induced by the
vertex set of $\mathcal{K}_{N}$ with vertices from $B$ and $R$ removed. From
the assumptions $\mathcal{K^{\prime}}$ has more than
$(1-\frac{2}{2000})N=\frac{999}{1000}N$ vertices and it does not contain a
monochromatic ordered star $\mathcal{S}_{t,t}$ for
$t\mathrel{\mathop{:}}=\left\lceil\frac{20}{217}N\right\rceil+1$. Therefore
the number of vertices of $\mathcal{K^{\prime}}$ is less than
$\operatorname{\overline{R}}(\mathcal{S}_{t,t},\mathcal{S}_{t,t})$.

Using Theorem 14 and the fact that
$\operatorname{\overline{R}}(\mathcal{S}_{t,1},\mathcal{S}_{t,t})=\operatorname{\overline{R}}(\mathcal{S}_{1,t},\mathcal{S}_{t,t})$
we have

$\displaystyle\operatorname{\overline{R}}(\mathcal{S}_{t,t},\mathcal{S}_{t,t})$
$\displaystyle=\operatorname{\overline{R}}(\mathcal{S}_{t,1},\mathcal{S}_{t,t})+\operatorname{\overline{R}}(\mathcal{S}_{1,t},\mathcal{S}_{t,t})-1=2(\operatorname{\overline{R}}(\mathcal{S}_{1,t},\mathcal{S}_{t,1})+2t-3)-1$
$\displaystyle=2\left(\left\lfloor\frac{-1+\sqrt{1+8(t-2)^{2}}}{2}\right\rfloor+2t-2+2t-3\right)-1<(8+2\sqrt{2})t.$

Altogether we have
$|V(\mathcal{K^{\prime}})|>\frac{999}{1000}N>(8+2\sqrt{2})(\left\lceil\frac{20}{217}N\right\rceil+1)>|V(\mathcal{K^{\prime}})|$,
a contradiction. Thus there is a set $W$ satisfying one of the claims, say the
first one.

Now, we find $U$ as a subset of $W$. To do so, partition the vertex set of
$\mathcal{K}_{N}$ into $\frac{16\cdot 10^{5}}{2000}=800$ intervals
$I_{1},\ldots,I_{800}$ such that each contains at least $\lfloor N/(16\cdot
10^{5})\rfloor$ vertices of $W$. This is possible as $|W|\geq N/2000$.
Clearly, there is an interval $I_{i}$ in $\mathcal{K}_{N}$ with at most
$N/800$ vertices of $\mathcal{K}_{N}$ which contains at least $\lfloor
N/(16\cdot 10^{5})\rfloor$ vertices of $W$ and we can set
$U\mathrel{\mathop{:}}=I_{i}\cap W$.

Since every vertex of $U$ has at least $\frac{20}{217}N$ blue left neighbors,
then it also contains at least $\frac{20}{217}N-N/800>N/11$ blue neighbors
that are to the left of $I_{i}$ and hence to the left of $U$ as well.
Analogous statement holds for blue right neighbors of every vertex from $U$
and hence $U$ satisfies the first part of the lemma. ∎

The following two statements are used in the proof of Theorem 10. The first
one is a classical result, called the Kövari-Sós-Turán theorem [31], which
estimates the maximum number of edges in a bipartite graph which does not
contain a given complete bipartite graph as a subgraph. The second one is an
upper bound on non-diagonal Ramsey numbers of complete graphs proved by Ajtai,
Komlós, and Szemerédi [1].

######  Theorem 26 ([2, 26, 31]).

Let $\mathrm{Z}(m,n;s,t)$ be the maximum number of edges in a bipartite graph
$G=(A\cup B,E)$, $|A|=m$, $|B|=n$, which does not contain $K_{s,t}$ as a
subgraph with $s$ vertices in $A$ and $t$ vertices in $B$. Assuming $2\leq
s\leq m$ and $2\leq t\leq n$, we have

$\mathrm{Z}(m,n,;s,t)<(s-1)^{1/t}(n-t+1)m^{1-1/t}+(t-1)m.$

######  Lemma 27 ([1]).

For a fixed integer $p\geq 2$, we have
$\operatorname{R}(K_{p},K_{n})\leq(5000)^{p}n^{p-1}/(\ln n)^{p-2}$ for $n$
sufficiently large (dependent on $p$).

The bound from Lemma 27 holds also for ordered complete graphs, as
$\operatorname{R}(K_{p},K_{n})=\operatorname{\overline{R}}(\mathcal{K}_{p},\mathcal{K}_{n})$
for every pair $(\mathcal{K}_{p},\mathcal{K}_{n})$ of ordered complete graphs.

###### Proof of Theorem 10.

Let $\mathcal{G}$ and $\mathcal{H}$ be ordered graphs satisfying the
assumptions for given $k$. Let $N=N_{k,q}(r,s)\mathrel{\mathop{:}}=C_{k}\cdot
2^{64k(\lceil\log_{q/(q-1)}{r}\rceil+\lceil\log_{q/(q-1)}{s}\rceil)}$ where
$C_{k}$ is a large constant dependent on $k$ and let $\mathcal{K}_{N}$ be a
complete ordered graph with edges colored red and blue. We want to find a blue
copy of $\mathcal{G}$ or a red copy of $\mathcal{H}$ in $\mathcal{K}_{N}$.

We proceed by induction on $\lceil\log_{q/(q-1)}{r}\rceil$ and
$\lceil\log_{q/(q-1)}{s}\rceil$. Suppose that
$\lceil\log_{q/(q-1)}{r}\rceil\leq\log_{q/(q-1)}{k}$. If $s$ is not
sufficiently large with respect to $k$ to satisfy the assumptions of Lemma 27
for $p\mathrel{\mathop{:}}=2k$ and $n\mathrel{\mathop{:}}=s$, then we use
Ramsey’s theorem. Having $C_{k}$ sufficiently large, we then find a blue copy
of $\mathcal{K}_{r}$ or a red copy of $\mathcal{K}_{s}$ in $\mathcal{K}_{N}$.
For other values of $s$ we can apply Lemma 27 with $p\mathrel{\mathop{:}}=2k$
and $n\mathrel{\mathop{:}}=s$, as we have $N>(5000)^{2k}s^{2k-1}/(\ln
s)^{2k-2}$ for $C_{k}$ sufficiently large. Since $r<2k$, we find a blue copy
of $\mathcal{K}_{r}$ or a red copy of $\mathcal{K}_{s}$ in $\mathcal{K}_{N}$.
The case $\lceil\log_{q/(q-1)}{s}\rceil\leq\log_{q/(q-1)}{k}$ is analogous.

Suppose that $\lceil\log{r}\rceil,\lceil\log{s}\rceil>\log_{q/(q-1)}{k}$ and
that the bound holds for every pair $\mathcal{G}^{\prime}$ and
$\mathcal{H}^{\prime}$ of ordered graphs satisfying the assumptions and having
$r^{\prime}$ and $s^{\prime}$ vertices, respectively, where either
$\lceil\log_{q/(q-1)}{r^{\prime}}\rceil<\lceil\log_{q/(q-1)}{r}\rceil$ or
$\lceil\log_{q/(q-1)}{s^{\prime}}\rceil<\lceil\log_{q/(q-1)}{s}\rceil$.

Let $U$ be the set from Lemma 25 and suppose that it satisfies the first part
of this lemma. That is, $U$ is a set with at least $\lfloor N/(16\cdot
10^{5})\rfloor$ vertices of $\mathcal{K}_{N}$ such that every vertex of $U$
has at least $N/11$ blue neighbors to the left and to the right of $U$.

If $s$ is not sufficiently large with respect to $k$ to satisfy the
assumptions of Lemma 27 for $p\mathrel{\mathop{:}}=61k$ and
$n\mathrel{\mathop{:}}=s$, then we use Ramsey’s theorem to the subgraph of
$\mathcal{K}_{N}$ induced by $U$. Having $C_{k}$ sufficiently large, we then
find a blue copy of $\mathcal{K}_{61k}$ or a red copy of $\mathcal{K}_{s}$.
For other values of $s$ we can apply Lemma 27 with $p\mathrel{\mathop{:}}=61k$
and $n\mathrel{\mathop{:}}=s$, as we have $|U|\geq N/(16\cdot
10^{5})>(5000)^{61k}s^{61k-1}/(\ln s)^{61k-2}$ for $C_{k}$ sufficiently large.
Again, we find either a red copy of $\mathcal{K}_{s}$ or a blue copy of
$\mathcal{K}_{61k}$ in the subgraph of $\mathcal{K}_{N}$ induced by $U$.
Suppose that we have found a blue copy of $\mathcal{K}_{61k}$, as otherwise we
are done, and let $U_{1}\subset U$ be its vertex set.

We now apply Theorem 26 twice to obtain a set $V\subset U_{1}$ of size $k$
which induces a blue copy of $\mathcal{K}_{k}$ and whose vertices have a
common blue neighborhood of size at least $N/2^{64k}$ to the left of $V$ and
also to the right of $V$.

Denote by $J_{L}$ the interval of vertices of $\mathcal{K}_{N}$ that are to
the left of $U_{1}$ and by $J_{R}$ the interval of vertices of
$\mathcal{K}_{N}$ that are to the right of $U_{1}$. A trivial estimate gives
us $N/11\leq|J_{L}|,|J_{R}|$. At least one of the intervals $J_{L}$ and
$J_{R}$ has size at most $N/2$ and by symmetry we may assume that $|J_{R}|\leq
N/2$. For the size of $J_{L}$ we have the estimate $|J_{L}|\leq\frac{10\cdot
N}{11}$, as $|J_{R}|\geq N/11$ and $J_{R}$ and $J_{L}$ are disjoint.

The number of blue edges between $U_{1}$ and $J_{L}$ is at least
$|U_{1}|\cdot|J_{L}|/10$, as every vertex of $U_{1}$ has at least $N/11$ blue
neighbors in $J_{L}$ and $|J_{L}|\leq\frac{10\cdot N}{11}$. For every
$C_{1}>0$ we have

$(|J_{L}|/C_{1}-1)^{1/6k}(|U_{1}|-6k+1)|J_{L}|^{1-1/6k}+(6k-1)|J_{L}|<|J_{L}|(|U_{1}|/C_{1}^{1/6k}+6k).$

If we choose $C_{1}\mathrel{\mathop{:}}=2^{10\cdot 6k}=2^{60k}$, then the
right side of this inequality is at most $|U_{1}|\cdot|J_{L}|/10$, as
$|U_{1}|=61k>\frac{C_{1}^{1/6k}}{C_{1}^{1/6k}-10}\cdot 60k$.

Thus, according to Theorem 26, the number of blue edges between $U_{1}$ and
$J_{L}$ is larger than $\mathrm{Z}(|J_{L}|,|U_{1}|;|J_{L}|/C_{1},6k)$ and we
can find a complete bipartite graph $K_{6k,|J_{L}|/C_{1}}$ in the (unordered)
bipartite graph induced by $U_{1}$ and $J_{L}$ where edges correspond to blue
edges of $\mathcal{K}_{N}$ between those two sets. Since $J_{L}$ is to the
left of $U_{1}$, this complete bipartite graph corresponds to a blue copy of
$\mathcal{K}_{|J_{L}|/C_{1},6k}$ with the first color class in $J_{L}$ and the
other one in $U_{1}$. We let $U_{2}\subset U_{1}$ be the set of $6k$ vertices
induced by the second color class.

Now, the number of blue edges between $U_{2}$ and $J_{R}$ is at least
$|U_{2}|\cdot|J_{R}|\cdot\frac{2}{11}$, as every vertex in $U_{2}$ has at
least $N/11$ blue neighbors in $J_{R}$ and $|J_{R}|\leq N/2$. Similarly as
before, for every $C_{2}>0$ we have

$(|J_{R}|/C_{2}-1)^{1/k}(|U_{2}|-k+1)|J_{R}|^{1-1/k}+(k-1)|J_{R}|<|J_{R}|(|U_{2}|/C_{2}^{1/k}+k).$

Choosing $C_{2}\mathrel{\mathop{:}}=2^{7k}$, the right side of this inequality
is at most $|U_{2}|\cdot|J_{R}|\cdot\frac{2}{11}$, as
$|U_{2}|=6k>\frac{C_{2}^{1/k}}{C_{2}^{1/k}-11/2}\cdot\frac{11}{2}k$. By
Theorem 26 the number of blue edges between $U_{2}$ and $J_{R}$ is larger than
$\mathrm{Z}(|J_{R}|,|U_{2}|;|J_{R}|/C_{2},k)$. Similarly as before, we obtain
a blue copy of $\mathcal{K}_{k,|J_{R}|/C_{2}}$ between $U_{2}$ and $J_{R}$.

The color class of size $k$ in the obtained complete bipartite graph forms a
set $V\subset U_{2}$ with $k$ vertices that induce a blue copy of
$\mathcal{K}_{k}$. Moreover, as $N/11\leq|J_{L}|,|J_{R}|$, the vertices of $V$
have at least $N/2^{(60+4)k}=N/2^{64k}$ common blue neighbors to the left and
also to the right of $V$.

We now use the facts that $\mathcal{G}$ is $(k,q)$-decomposable and that
$r\geq k$. We partition vertices of $\mathcal{G}$ into three intervals
$I_{L}$, $I$ and $I_{R}$ where $0<|I|\leq k$ and
$|I_{L}|,|I_{R}|\leq|V(G)|\cdot\frac{q-1}{q}=\frac{r(q-1)}{q}$ such that $I$
is to the right of $I_{L}$ and to the left of $I_{R}$. Moreover, intervals
$I_{L}$ and $I_{R}$, induce $(k,q)$-decomposable ordered graphs
$\mathcal{G}_{L}$ and $\mathcal{G}_{R}$, respectively, and there is no edge
between $\mathcal{G}_{L}$ and $\mathcal{G}_{R}$ (although vertices of
$\mathcal{G}_{L}$ and $\mathcal{G}_{R}$ may have neighbors in $I$).

From our choice of $N$, we have

$\displaystyle N/2^{64k}$ $\displaystyle=C_{k}\cdot
2^{64k(\lceil\log_{q/(q-1)}{r}\rceil+\lceil\log_{q/(q-1)}{s}\rceil-1)}$
$\displaystyle=C_{k}\cdot
2^{64k(\lceil\log_{q/(q-1)}{r(q-1)/q}\rceil+\lceil\log_{q/(q-1)}{s}\rceil)}\geq
N_{k,q}(\lfloor r(q-1)/q\rfloor,s)$

and so
$N/2^{64k}\geq\operatorname{\overline{R}}(\mathcal{G}_{L},\mathcal{H}),\operatorname{\overline{R}}(\mathcal{G}_{R},\mathcal{H})$.
Therefore we can find either a red copy of $\mathcal{H}$ or a blue copy of
$\mathcal{G}_{L}$ in the common blue left neighborhood of $V$, using the
inductive assumption. Similarly, we can find a red copy of $\mathcal{H}$ or a
blue copy of $\mathcal{G}_{R}$ in the common blue right neighborhood of $V$.
Suppose that we do not obtain a red copy of $\mathcal{H}$ in any of these two
cases. Then we find a blue copy of $\mathcal{G}$ by choosing $|I|$ vertices of
$V$ as a copy of $I$ and connect it to the blue copies of $\mathcal{G}_{L}$
and $\mathcal{G}_{R}$.

If the set $U$ from Lemma 25 satisfies the second part of the lemma, then the
proof would proceed analogously. The main differences are that we use the
$(k,q)$-decomposability of the graph $\mathcal{H}$ instead of $\mathcal{G}$
and estimates $N/2^{64k}\geq N_{k,q}(r,\lfloor s(q-1)/q\rfloor)$ and
$\frac{N}{16\cdot 10^{5}}\geq(5000)^{61k}r^{61k-1}/(\ln r)^{61k-2}$. ∎

###  4.2 Proof of Theorem 12

Here we prove Theorem 12 which says that for every ordered graph $\mathcal{G}$
of constant degeneracy and constant interval chromatic number the ordered
Ramsey number $\operatorname{\overline{R}}(\mathcal{G};2)$ is polynomial in
the number of vertices of $\mathcal{G}$.

In fact, we prove a stronger statement, Theorem 29, and derive Theorem 12 as
an immediate corollary of this result.

######  Lemma 28.

Let $k$ be a positive integer and let $\mathcal{G}$ be a $k$-degenerate
ordered graph with $n$ vertices. Then in every complete ordered graph
$\mathcal{K}_{N}$, $N\geq n^{2}$, with edges colored red and blue we find
either a blue copy of $\mathcal{G}$ or a red copy of $\mathcal{K}_{t,t}$ for
$t\mathrel{\mathop{:}}=(N/n^{2})^{1/(k+1)}$.

###### Proof.

Let $\mathcal{G}=(G,\prec)$ and $\mathcal{K}_{N}$ be ordered graphs satisfying
the assumptions for given $k$ and let
$t\mathrel{\mathop{:}}=(N/n^{2})^{1/(k+1)}$. Since $N\geq n^{2}$, we have
$t\geq 1$. We partition the vertices of $\mathcal{K}_{N}$ into $n$ disjoint
consecutive intervals of length $N/n$. The $i$th such interval is denoted by
$I(v)$ where $v$ is the $i$th vertex of $\mathcal{G}$ in the ordering $\prec$.

We try to construct a blue copy $h(\mathcal{G})$ of $\mathcal{G}$ in
$\mathcal{K}_{N}$, We show that in each step of the construction of
$h(\mathcal{G})$ it is either possible to find a new image $h(w)$ of a vertex
$w$ of $\mathcal{G}$ or we have a red copy of $\mathcal{K}_{t,t}$ in
$\mathcal{K}_{N}$.

For every vertex $v$ of $\mathcal{G}$ that does not have an image $h(v)$ yet,
we keep a set $U(v)\subseteq V(\mathcal{K}_{N})$ of possible candidates for
$h(v)$. At the beginning we set $U(v)\mathrel{\mathop{:}}=I(v)$ for every
$v\in V(G)$.

Let $\lessdot$ be an ordering of the vertices of $\mathcal{G}$ such that every
vertex $v$ of $\mathcal{G}$ has at most $k$ left neighbors in $\lessdot$. This
ordering exists as $\mathcal{G}$ is $k$-degenerate. Note that the ordering
$\lessdot$ might differ from the ordering $\prec$.

Let $w$ be the first vertex of $\mathcal{G}$ in the ordering $\lessdot$ that
does not have an image $h(w)$ yet. Suppose that $u_{1},\ldots,u_{s}\in V(G)$
are the right neighbors of $w$ in the ordering $\lessdot$. Clearly, we have
$s\leq n$. We show how to find the image $h(w)$ or a red copy of
$\mathcal{K}_{t,t}$ in $\mathcal{K}_{N}$.

Let $i$ be an arbitrary element of the set $\\{1,,\ldots,s\\}$. We claim that
in $U(w)$ every vertex except of at most $t-1$ vertices has at least
$\frac{|U(u_{i})|}{t}$ blue neighbors in $U(u_{i})$ or that we can find a red
copy of $\mathcal{K}_{t,t}$ with one color class in $U(w)$ and the other in
$U(u_{i})$.

Suppose first that there is a subset $W$ of $U(w)$ with $t$ vertices such that
each vertex of $W$ has less than $\frac{|U(u_{i})|}{t}$ blue neighbors in
$U(u_{i})$. In such a case we delete from $U(u_{i})$ every vertex that is a
blue neighbor of some vertex of $W$. Afterwards, there is still at least

$|U(u_{i})|-|W|\cdot\left(\frac{|U(u_{i})|}{t}-1\right)=|U(u_{i})|-t\cdot\left(\frac{|U(u_{i})|}{t}-1\right)=t$

vertices left in $U(u_{i})$ and every such vertex has no blue neighbors in
$W$. Therefore we have a red copy of $\mathcal{K}_{t,t}$ in $\mathcal{K}_{N}$.

Therefore we either have a red copy of $\mathcal{K}_{t,t}$ in
$\mathcal{K}_{N}$ or there is a set $C_{w}$ with at least
$|U(w)|-s(t-1)>|U(w)|-nt$ vertices in $U(w)$ such that every vertex of $C_{w}$
has at least $\frac{|U(u_{i})|}{t}$ blue neighbors in $U(u_{i})$ for every
$i=1,\ldots,s$. We may assume that the second case occurs, as otherwise we are
done.

We choose an arbitrary vertex $h(w)$ of $C_{w}$ to be the image of $w$ in the
constructed blue copy $h(\mathcal{G})$ of $\mathcal{G}$. We show that $C_{w}$
is nonempty and that this is possible at the end of the proof. We update the
sets $U(u_{1}),\ldots,U(u_{s})$ by setting $U(u_{i})$ to be the set of at
least $|U(u_{i})|/t$ blue neighbors of $h(w)$ in $U(u_{i})$ for every
$i=1,\ldots,s$.

After these updates, we, again, choose the first vertex in $\lessdot$ that
does not have an image yet and proceed as before. If there is no such vertex,
then we have found a blue copy $h(\mathcal{G})$ of $\mathcal{G}$ in
$\mathcal{K}_{N}$ as there is an image of every vertex of $\mathcal{G}$.

It remains to show that the set $C_{w}$ is nonempty. We know that before
choosing the image $h(w)$ the size of $C_{w}$ is strictly larger than
$|U(w)|-nt$. In the previous steps of the construction of $h(\mathcal{G})$ we
have updated $U(w)$ at most $k$ times, as $w$ has at most $k$ left neighbors
in $\lessdot$. The size of $U(w)$ is divided by at most $t$ in every update.

Since the size of $U(w)$ is exactly $N/n$ at the beginning of the construction
of $h(\mathcal{G})$, the inequality $(N/n)\cdot(1/t)^{k}-nt\geq 0$ implies
that there is at least one vertex in $C_{w}$. This inequality can be rewritten
as $t\leq(N/n^{2})^{1/(k+1)}$ which is satisfied by the choice of $t$. This
finishes the proof. ∎

######  Theorem 29.

For positive integers $k$ and $p$, let $\mathcal{G}$ be a $k$-degenerate
ordered graph with $n$ vertices. Then we have

$\operatorname{\overline{R}}(\mathcal{G},\mathcal{K}_{n}(p))\leq
n^{(1+2/k)(k+1)^{\lceil\log{p}\rceil}-2/k}.$

###### Proof.

First, we define the function $f_{k,n}(l)\colon\mathbb{N}\to\mathbb{N}$ as

$f_{k,n}(l)\mathrel{\mathop{:}}=n^{(1+2/k)(k+1)^{l}-2/k}.$

Note that this function satisfies the recurrence equation
$f_{k,n}(l)=n^{2}\cdot f_{k,n}(l-1)^{k+1}$ with the initial condition
$f(1)=n^{k+3}$.

Without loss of generality we may assume that $p$ is a power of two. That is,
we have $p=2^{l}$ for some positive integer $l$. We proceed by induction on
$l$. The first step $l=1$ follows immediately from Lemma 28 applied to
$\mathcal{K}_{N}$ with $N\mathrel{\mathop{:}}=f_{k,n}(1)=n^{k+3}$.

Suppose that we have $l\geq 2$. Let $\mathcal{K}_{N}$ be an ordered complete
graph with $N\mathrel{\mathop{:}}=f_{k,n}(l)$ vertices and edges colored red
and blue. We show that there is always either a blue copy of $\mathcal{G}$ or
a red copy of $\mathcal{K}_{n}(p)$ in $\mathcal{K}_{N}$.

According to Lemma 28, there is either a blue copy of $\mathcal{G}$ or a red
copy of $\mathcal{K}_{t,t}$ for $t\mathrel{\mathop{:}}=(N/n^{2})^{1/(k+1)}$.
In the first case we are done, so suppose that the second case occurs.

Let $A$ ($B$, respectively) be the left (right, respectively) color class of
size $t$ in the red copy of $\mathcal{K}_{t,t}$. We use $\mathcal{K}[A]$ and
$\mathcal{K}[B]$ to denote the two complete ordered subgraphs of
$\mathcal{K}_{N}$ induced by $A$ and $B$, respectively. These subgraphs are
considered together with the corresponding red-blue colorings of their edges.

From the choice of $N$, the ordered subgraph $\mathcal{K}[A]$ contains at
least $f_{k,n}(l-1)$ vertices. Therefore there is either a blue copy of
$\mathcal{G}$ or a red copy of $\mathcal{K}_{n}(p/2)$ in $\mathcal{K}[A]$ by
the inductive assumption. An analogous statement holds for the ordered
subgraph $\mathcal{K}[B]$.

Thus, if we do not find a blue copy of $\mathcal{G}$ in $\mathcal{K}[A]$ nor
in $\mathcal{K}[B]$, then the two red copies of $\mathcal{K}_{n}(p/2)$
together with the red edges between $\mathcal{K}[A]$ and $\mathcal{K}[B]$ give
us a red copy of $\mathcal{K}_{n}(p)$ in $\mathcal{K}_{N}$. ∎

###### Proof of Theorem 12.

Theorem 12 follows immediately from Theorem 29 and the fact that every ordered
graph $\mathcal{G}$ with $n$ vertices and with interval chromatic number $p$
is an ordered subgraph of $\mathcal{K}_{n}(p)$. ∎

##  5 Open problems

Studying ordered graphs in Ramsey theory offers a plenty of new questions. We
still do not know exact formulas for a wide spectrum of graphs, but it might
be more interesting to ask questions which concern the structure of optimal
colorings.

For example, we can ask what properties of vertex orderings make ordered
Ramsey numbers grow slower or faster and whether there is some
characterization of ordered graphs with small ordered Ramsey numbers.

Let us define the maximum ordered Ramsey number
$\operatorname{\overline{R}}_{max}(G)$ for a graph $G$ as the maximum of
$\operatorname{\overline{R}}((G,\prec);2)$ taken over all possible vertex
orderings of $G$. Analogously, we can define the minimum ordered Ramsey number
$\operatorname{\overline{R}}_{min}(G)$ of a graph $G$. An interesting question
is whether there is a formula for the numbers
$\operatorname{\overline{R}}_{max}(G_{n})$ or
$\operatorname{\overline{R}}_{min}(G_{n})$ where $G_{n}$ are graphs on $n$
vertices from some specified class of graphs (such as paths, cycles, cliques,
etc.). Also for which orderings of $G$ are these values attained. We can
answer this question for stars using Theorem 14.

We might also ask whether for every $n$-vertex bounded-degree graph $G$ there
is an ordering of its vertices with the ordered Ramsey number linear in $n$.

######  Question 1.

Is it true that for every graph $G$ on $n$ vertices with degrees bounded by a
constant $\Delta$ there exists an ordering $\prec$ such that
$\operatorname{\overline{R}}((G,\prec);2)\leq C\cdot n$ where $C=C(\Delta)$ is
a constant which depends on $\Delta$?

This result, if true, would be a natural strengthening of the fact that
bounded-degree (unordered) graphs have linear Ramsey numbers. If the answer is
negative, then there is a graph with bounded degrees and super-linear ordered
Ramsey numbers for every ordering of its vertices.

Theorem 12 implies that ordered Ramsey numbers of bounded-degree graphs with
constant-size interval chromatic number are polynomial in the number of
vertices. We do not know whether this bound is tight, as we have no non-
trivial lower bounds.

######  Question 2.

For positive integers $\Delta$ and $p$, are there $n$-vertex ordered graphs
$\mathcal{G}_{n}$ with maximum degree at most $\Delta$ and with interval
chromatic number two such that
$\operatorname{\overline{R}}(\mathcal{G}_{n};2)=n^{\Omega(\Delta)}$?

Similarly, it would be interesting to find some non-trivial lower bounds for
ordered Ramsey numbers of ordered graphs with edge lengths of constant size.

## Acknowledgments

The authors would like to thank to Jiří Matoušek for many helpful comments.

## References

  * [1] M. Ajtai, J. Komlós, and E. Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A, 29(3) (1980), 354–360.
  * [2] B. Bollobás, Extremal Graph Theory, New York: Dover publications. ISBN 978-0-486-43596-1, 2004.
  * [3] J. A. Bondy and P. Erdős, Ramsey numbers for cycles in graphs, J. Combin. Theory Ser. B 14(1) (1973), 46–54.
  * [4] S. A. Burr and J. A. Roberts, On Ramsey numbers for stars, Utilitas Math. 4 (1973), 217–220.
  * [5] G. Chartrand and S. Schuster, On the existence of specified cycles in complementary graphs, Bull. Amer. Math. Soc. 77 (1971), 995–998.
  * [6] S. A. Choudum and B. Ponnusamy, Ordered Ramsey numbers, Discrete Math. 247(1–3) (2002), 79–92.
  * [7] F. R. K. Chung, F. T. Leighton, and A. L. Rosenberg, Embedding graphs in books: a layout problem with applications to VLSI design, SIAM Journal on Algebraic Discrete Methods 8(1) (1987): 33–58.
  * [8] V. Chvátal and F. Harary, Generalized Ramsey theory for graphs, II, Small diagonal numbers, Proc. Amer. Math. Soc. 32(2) (1972), 389–394.
  * [9] J. Cibulka, Extremal combinatorics of matrices, sequences and sets of permutations, Ph.D. Thesis, Charles University, Prague, 2013.
  * [10] J. Cibulka, P. Gao, M. Krčál, T. Valla, and P. Valtr, On the geometric Ramsey number of outerplanar graphs, arXiv:1310.7004v3, 2013.
  * [11] D. Conlon, A new upper bound for diagonal Ramsey numbers, Ann. of Math. 170 (2009), 941–960.
  * [12] D. Conlon, J. Fox, and B. Sudakov, Ramsey numbers of sparse hypergraphs, Random Structures Algorithms 35(1) (2009), 1–14.
  * [13] D. Conlon, J. Fox, C. Lee, and B. Sudakov, Ordered Ramsey numbers, arXiv:1410.5292, 2014.
  * [14] T. Dzido, A. Nowik, and P. Szuca, New lower bound for multicolor Ramsey numbers for even cycles, Electron. J. Combin. 12 (2005).
  * [15] M. Eliáš and J. Matoušek, Higher-order Erdős–Szekeres theorems, Adv. Math. 244 (2013), 1–15.
  * [16] P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53(4) (1947), 292–294.
  * [17] P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compos. Math. 2 (1935), 463–470.
  * [18] R. J. Faudree and R. H. Schelp, All Ramsey numbers for cycles in graphs, Discrete Math. 8(4) (1974), 313–329.
  * [19] R. J. Faudree and R. H. Schelp, Path Ramsey numbers in multicolorings, J. Combin. Theory Ser. B 19(2) (1975), 150–160.
  * [20] J. Fox and B. Sudakov, Dependent random choice, Random Structures Algorithms 38 (2011), 68–99.
  * [21] J. Fox, J. Pach, B. Sudakov, and A. Suk, Erdős–Szekeres-type theorems for monotone paths and convex bodies, Proc. London Math. Soc. 105 (2012), 953–982.
  * [22] Z. Füredi and P. Hajnal, Davenport-Schinzel theory of matrices, Discrete Math. 103(3) (1992), 233–251.
  * [23] L. Gerencsér and L. Gyárfás, On Ramsey-type problems, Ann. Univ. Sci. Eötvös Sect. Math. 10 (1967), 167–170.
  * [24] J. E. Graver and J. Yackel, Some graph theoretic results associated with Ramsey’s theorem, Journal of Combin. Theory 4(2) (1968), 125–175.
  * [25] A. Gyárfás, M. Ruszinkó, G. N. Sárközy, and E. Szemerédi, Three-color Ramsey numbers for paths, Combinatorica 27(1) (2007), 35–69.
  * [26] C. Hyltén-Cavallius, On a combinatorial problem, Colloq. Math., 6 (1958), 59–65.
  * [27] G. Károlyi, J. Pach, and G. Tóth, Ramsey-type results for geometric graphs, I, Discrete Comput. Geom. 18(3) (1997), 247–255.
  * [28] G. Károlyi, J. Pach, G. Tóth, and P. Valtr, Ramsey-type results for geometric graphs, II, Discrete Comput. Geom. 20(3) (1998), 375–388.
  * [29] M. Klazar, Extremal problems for ordered (hyper)graphs: applications of Davenport–Schinzel sequences, European J. Combin. 25(1) (2004), 125–140.
  * [30] M. Klazar, Extremal problems for ordered hypergraphs: small patterns and some enumeration, Discrete Appl. Math. 143(1–3) (2004), 144–154.
  * [31] T. Kövari, V. Sós, and P. Turán, On a problem of Zarankiewicz, Colloq. Math., 3 (1954), 50–57.
  * [32] Yusheng Li and Ko-Wei Lih, Multi-color Ramsey numbers of even cycles, European J. Combin. 30(1) (2009), 114–118.
  * [33] T. Luczak, M. Simonovits, and J. Skokan, On the multi-colored Ramsey numbers of cycles, J. Graph Theory 69(2) (2012), 169–175.
  * [34] K. G. Milans, D. Stolee, and D. B. West, Ordered Ramsey theory and track representations of graphs, to appear, 2012.
  * [35] G. Moshkovitz and A. Shapira, Ramsey theory, integer partitions and a new proof of the Erdős–Szekeres Theorem, Adv. in Math. 262 (2014), 1107–1129.
  * [36] J. Pach and G. Tardos, Forbidden paths and cycles in ordered graphs and matrices, Israel J. Math. 155(1) (2006), 359–380.
  * [37] V. Rosta, On a Ramsey type problem of J.A. Bondy and P. Erdős, J. Combin. Theory Ser. B 15(1) (1973), 94–120.
  * [38] J. M. Steele, Variations on the monotone subsequence theme of Erdős and Szekeres, in: Discrete Probability and Algorithms, the IMA Volumes in Mathematics and Its Applications 72 (1995), 111–131.