# Online Ramsey numbers of ordered paths and cycles

Felix Christian Clemen111Department of Mathematics, Karlsruhe Institute of
Technology, 76131 Karlsruhe, Germany, Email<EMAIL_ADDRESS>Emily
Heath222Department of Mathematics, Iowa State University, Ames, Iowa 50011,
USA, Email<EMAIL_ADDRESS>Research partially supported by NSF RTG Grant
DMS-1839918. Mikhail Lavrov333Department of Mathematics, Kennesaw State
University, Marietta, Georgia 30067, USA, Email<EMAIL_ADDRESS>
###### Abstract

An ordered graph is a graph with a linear ordering on its vertices. The online
Ramsey game for ordered graphs $G$ and $H$ is played on an infinite sequence
of vertices; on each turn, Builder draws an edge between two vertices, and
Painter colors it red or blue. Builder tries to create a red $G$ or a blue $H$
as quickly as possible, while Painter wants the opposite. The online ordered
Ramsey number $r_{o}(G,H)$ is the number of turns the game lasts with optimal
play.

In this paper, we consider the behavior of $r_{o}(G,P_{n})$ for fixed $G$,
where $P_{n}$ is the monotone ordered path. We prove an $O(n\log n)$ bound on
$r_{o}(G,P_{n})$ for all $G$ and an $O(n)$ bound when $G$ is $3$-ichromatic;
we partially classify graphs $G$ with $r_{o}(G,P_{n})=n+O(1)$. Many of these
results extend to $r_{o}(G,C_{n})$, where $C_{n}$ is an ordered cycle obtained
from $P_{n}$ by adding one edge.

##  1 Introduction

The _Ramsey number_ $r(G,H)$ of two graphs $G$ and $H$ is the least $n$ such
that any red-blue edge-coloring of the complete graph $K_{n}$ contains a red
copy of $G$ or a blue copy of $H$. Finding bounds on such Ramsey numbers has
been an important problem in graph theory for many years; see [6] for a survey
of known bounds on Ramsey numbers.

The online version of the Ramsey problem considers a setting where the red-
blue coloring is not given at once, but is revealed gradually. To consider the
worst-case scenario, we model this setting as a game between two players,
Builder and Painter, on an infinitely large set of vertices. Again, we pick
two graphs $G$ and $H$. On each turn, Builder draws an edge between two
vertices and Painter colors it red or blue. The game ends when a red copy of
$G$ or a blue copy of $H$ is formed; Builder seeks to minimize the number of
turns, and Painter seeks to maximize it.

The _online Ramsey number_ is the number of rounds in this game, assuming
optimal play. Equivalently, it is the minimum number of edge queries necessary
to find a red copy of $G$ or a blue copy of $H$ in an infinite complete graph,
assuming a worst-case scenario for the outcome of these queries. Online Ramsey
numbers are also called _online size Ramsey numbers_ in the literature, since
they track the size (number of edges) used. Introduced independently by [3]
and [11], these numbers have since been studied by many authors including [1],
[4], [7], and [10].

###  1.1 Ordered graphs

In this paper, we consider online Ramsey numbers of ordered graphs. An
_ordered graph_ is a graph with a linear ordering on its vertices. We think of
the vertices of an ordered graph as being arranged on a horizontal line in
order from left to right. Subgraphs of an ordered graph $G$ inherit the
ordering on $V(G)$, and isomorphisms between ordered graphs must be order-
preserving.

From now on, we assume that all graphs are ordered graphs. We will borrow the
notation $P_{n}$, $C_{n}$, $K_{n}$, $K_{n_{1},\dots,n_{k}}$ to use for ordered
graphs, by giving their vertices a standard ordering:

  * •

The ordered path $P_{n}$ has $n$ vertices $v_{1}<v_{2}<\dots<v_{n}$ and edges
$v_{i}v_{i+1}$ for $i=1,\dots,n-1$.

  * •

The ordered cycle $C_{n}$ is obtained from $P_{n}$ by adding the edge
$v_{1}v_{n}$.

  * •

The ordered complete graph $K_{n}$ has all edges between $n$ vertices
$v_{1}<v_{2}<\dots<v_{n}$. (Here, all orderings of the vertices yield
isomorphic ordered graphs.)

  * •

The ordered complete $k$-partite graph $K_{n_{1},n_{2},\dots,n_{k}}$ has $k$
parts with $n_{1},n_{2},\dots,n_{k}$ vertices respectively; for each $i$, the
$n_{i}$ vertices in the $i$th part are consecutive in the vertex ordering.

Ramsey problems on ordered graphs are motivated by the Erdős–Szekeres theorem
[8]. This result asserts that any sequence of $(r-1)(s-1)+1$ distinct real
numbers contains either an increasing subsequence of length $r$ or a
decreasing subsequence of length $s$, while a sequence of length $(r-1)(s-1)$
is not enough.

The Erdős–Szekeres theorem has many proofs [15], most of which easily extend
to the stronger result that the ordered Ramsey number of $P_{r}$ versus
$P_{s}$ is $(r-1)(s-1)+1$. Given a sequence of distinct real numbers
$x_{1},x_{2},\dots,x_{n}$, we color $K_{n}$ by coloring $v_{i}v_{j}$ red if
$x_{i}<x_{j}$, and blue if $x_{i}>x_{j}$. A red $P_{r}$ or blue $P_{s}$ in
$K_{n}$ corresponds to an increasing or decreasing subsequence of the desired
length. Not all colorings of $K_{n}$ originate from a sequence
$x_{1},x_{2},\dots,x_{n}$, but this turns out not to affect the result.

We will write $r_{o}(G,H)$ for the online Ramsey number for ordered graphs $G$
and $H$. These were first studied in the case $r_{o}(P_{r},P_{s})$ by [2] and
[14]. Just as in the case of unordered graphs, the online Ramsey number is
defined by a game played between Builder and Painter on an infinite set of
vertices. Here, we assume that the vertex set is $\mathbb{N}$ with the usual
ordering.

It will sometimes be convenient, when describing a strategy for Builder, to
assume that between any two vertices that have already been used, another
vertex can be found. This can be guaranteed even on vertex set $\mathbb{N}$
with foresight on Builder’s part: if Builder’s strategy wins in $t$ turns,
then at most $2t$ distinct vertices are used, so Builder may choose the
$i^{\text{th}}$ vertex to be an element of $\mathbb{N}$ divisible by
$2^{2t-i}$ but not by $2^{2t-i+1}$. This will be needed, for example, in the
proof of Theorem 1.2.

The online Ramsey game for ordered graphs is closely related to a sorting
problem: given an infinite sequence $x_{1},x_{2},\dots$ of distinct real
numbers, how many comparisons are needed to locate an increasing subsequence
of length $r$ or a decreasing subsequence of length $s$? However, Painter has
more flexibility in coloring edges, since edge colors do not have to obey
transitivity; it is unknown whether the two problems are equivalent.

###  1.2 Our results

In this paper, we consider online ordered Ramsey numbers of the form
$r_{o}(G,P_{n})$ for various ordered graphs $G$. We are especially interested
in how $r_{o}(G,P_{n})$ varies with $n$ when $G$ is fixed.

Theorem 2.1 in [2] gives an upper bound on $r_{o}(P_{m},P_{n})$ of the form
$O(mn\log n)$. Our first result is a generalization of this upper bound to
$r_{o}(G,P_{n})$. Here, let $\Delta^{-}(G)$ denote the _maximum left degree_
of $G$: the maximum number of edges between any vertex $v$ and vertices that
precede $v$.

######  Theorem 1.1.

For any ordered graph $G$, $r_{o}(G,P_{n})\leq\Delta^{-}(G)|V(G)|n\lg n$.

By symmetry, the same bound applies with left degree replaced by right degree.

Note that in Theorem 2.1 of [2], we are free to swap $m$ and $n$, so for fixed
$m$, when $n$ is large, it also gives an upper bound of $O(mn\log m)$ which is
linear in $n$. However, Theorem 1.1 does not allow the same flexibility. This
motivates the question: for which $G$ is $r_{o}(G,P_{n})$ linear in $n$, when
$G$ is fixed?

An _interval coloring_ of an ordered graph $G$ is a proper vertex coloring of
$G$ in which each color class is a set of consecutive vertices: if $u,w\in
V(G)$ are assigned the same color, then every vertex $v$ between $u$ and $w$
must also be assigned that color. The _interval chromatic number_
$\chi_{i}(G)$ of an ordered graph $G$ is the minimum number of colors in an
interval coloring of $G$. We say that $G$ is _$k$ -ichromatic_ if
$\chi_{i}(G)\leq k$.

The interval chromatic number has played a key role in Ramsey and Turán
problems for ordered graphs; see for example [5], [9], [13] and [12]. We are
able to prove a linear upper bound on $r_{o}(G,P_{n})$ for any $3$-ichromatic
$G$.

######  Theorem 1.2.

For any ordered graph $G$ such that $\chi_{i}(G)\leq 3$,
$r_{o}(G,P_{n})=O(n|V(G)|^{2}\log|V(G)|)$.

It is certainly not the case that the interval chromatic number tells the
whole story: for example, $r_{o}(P_{k},P_{n})=O(n)$ for any fixed $k$ even
though $\chi_{i}(P_{k})=k$. On the other hand, we do not have a linear upper
bound even on $r_{o}(C_{4},P_{n})$.

When we look at smaller and sparser graphs $G$, another transition emerges.
Let $M_{k}$ denote the _serial $k$-edge matching_: the ordered graph with
$E(M_{k})=\\{v_{1}w_{1},v_{2}w_{2},\dots,v_{k}w_{k}\\}$ and
$v_{1}<w_{1}<v_{2}<w_{2}<\dots<v_{k}<w_{k}$.

######  Theorem 1.3.

For $n\geq 4$ and $k\geq 2$, $r_{o}(M_{k},P_{n})\leq n+2k-4$, and if $n\geq
3k-3$, then $r_{o}(M_{k},P_{n})=n+2k-4$.

On the other hand, we have stronger lower bounds on $r_{o}(G,P_{n})$ even in
the case of three two-edge graphs: the path $P_{3}$, the intersecting matching
$X$, and the $2$-pronged claw $K_{1,2}$ (shown in Figure 1).

######  Theorem 1.4.

The following bounds hold:

  1. (a)

$2n-2\leq r_{o}(P_{3},P_{n})\leq\frac{8}{3}n-\frac{10}{3}$;

  2. (b)

$\frac{3}{2}n-\frac{3}{2}<r_{o}(X,P_{n})\leq\frac{5}{3}n+10$;

  3. (c)

$r_{o}(K_{1,2},P_{n})=2n$ (and by symmetry, $r_{o}(K_{2,1},P_{n})=2n$).

(a) The path graph $P_{3}$

(b) The intersecting matching $X$

(c) The $2$-pronged claw $K_{1,2}$

Figure 1: The three two-edge graphs of Theorem 1.4

In particular, $r_{o}(G,P_{n})\geq\frac{3}{2}n$ for any $G$ that contains any
of $P_{3}$, $X$, $K_{1,2}$, or $K_{2,1}$ as a subgraph. If $G$ does not
contain any of $P_{3}$, $K_{1,2}$, and $K_{2,1}$, then $G$ must be a matching
(possibly with isolated vertices, which don’t affect $r_{o}(G,P_{n})$). We say
that an ordered matching $M$ is _intersection-free_ if it also does not
contain $X$.

We conjecture that having one of the two-edge graphs in Theorem 1.4 as a
subgraph is the only reason why a bound of the form $r_{o}(G,P_{n})=n+O(1)$
would not hold.

######  Conjecture 1.1.

For every intersection-free matching $M$, there is a constant $c$ such that
$r_{o}(M,P_{n})\leq n+c$.

We can rephrase Conjecture 1.1 in terms of a more concrete sequence of Ramsey
problems. Let the _St. Ives matching_ 444We named this ordered matching after
the town St. Ives from the rhyme “As I was going to St. Ives,” which, in an
early version, first appeared in 1730 in a manuscript by Harley. $S_{k}$ be
the ordered matching defined recursively as follows. $S_{0}$ is simply an
ordered edge. $S_{k}$ is constructed from two disjoint consecutive copies of
$S_{k-1}$ by adding an edge $u_{k}v_{k}$ such that both copies of $S_{k-1}$
are to the right of $u_{k}$ and to the left of $v_{k}$. A diagram of $S_{2}$
is shown in Figure 2(a).

(a) The St. Ives matching $S_{2}$

(b) The partial St. Ives matching $S_{2}^{\prime}$

Figure 2: Examples of the St. Ives matching and the partial St. Ives matching

Every intersection-free matching $M$ on $k$ edges is a subgraph of $S_{k}$,
which can be shown recursively. If $M$ splits into two matchings $M^{\prime}$,
$M^{\prime\prime}$ where every vertex of $M^{\prime}$ lies before every vertex
of $M^{\prime\prime}$, we can find $M$ and $M^{\prime}$ within the two
different copies of $S_{k-1}$ inside $S_{k}$. If $M$ does not split in this
way, then it has an edge $vw$ where $v$ is the leftmost vertex of $M$ and $w$
is the rightmost vertex. Then we can find a copy of $M-vw$ inside one copy of
$S_{k-1}$ inside $S_{k}$; together with edge $u_{k}v_{k}$ of $S_{k}$, it
becomes a subgraph isomorphic to $M$.

As a result, Conjecture 1.1 is equivalent to the following statement.

######  Conjecture 1.2.

For all $k\geq 1$, there is a constant $c_{k}$ such that for all $n\geq 1$,
$r_{o}(S_{k},P_{n})\leq n+c_{k}$.

In partial support of Conjecture 1.2, we show it for a less general sequence
of graphs. First, let the _nested matching_ $N_{k}$ be the ordered graph with
vertices $v_{1}<\dots<v_{k}<w_{k}<\dots<w_{1}$ and edges
$v_{1}w_{1},\dots,v_{k}w_{k}$. The _partial St. Ives matching_
$S_{k}^{\prime}$ is then ordered matching obtained from $N_{k}$ by adding $k$
more consecutive copies of $N_{k}$ between vertices $v_{k}$ and $w_{k}$. A
diagram of $S_{2}^{\prime}$ is shown in Figure 2(b).

######  Theorem 1.5.

For all $k\geq 1$, there is a constant $c_{k}$ such that for all $n\geq 1$,
$r_{o}(S_{k}^{\prime},P_{n})\leq n+c_{k}$.

In fact, Builder’s strategy in the proof of Theorem 1.5 can be repeated to
extend a path in two directions, obtaining either a blue $P_{n}$ or two
consecutive copies of $S_{k}^{\prime}$. The graph consisting of three
consecutive copies of $S_{k}^{\prime}$ is the simplest matching for which we
are unable to prove that Conjecture 1.1 holds.

All of the results above are bounds on $r_{o}(G,P_{n})$. However, when we
replace $P_{n}$ by the ordered cycle $C_{n}$, the same classification into
$O(n\log n)$ and $O(n)$ upper bounds holds, due to the following result.

######  Theorem 1.6.

For any ordered graph $G$, there is a constant $c$ such that
$r_{o}(G,C_{n})\leq r_{o}(G,P_{m})+c$, where $m=(n-1)(|V(G)|-1)+1$.

The remainder of the paper is organized as follows. In Section 2, we prove
$O(n\log n)$ bounds on $r_{o}(G,P_{n})$ and $r_{o}(G,C_{n})$ that apply to any
ordered graph $G$: Theorem 1.1 and Theorem 1.6. In Section 3, we prove Theorem
1.2, which applies to $3$-ichromatic graphs $G$, for which we can prove $O(n)$
bounds. In Section 4, we prove the three cases of Theorem 1.4, dealing with
small graphs for which we can still do no better than $O(n)$. Finally, in
Section 5, we prove Theorem 1.3 and Theorem 1.5: two cases in which
$r_{o}(G,P_{n})=n+O(1)$.

##  2 Results for general $G$

###  2.1 An $O(n\log n)$ bound

###### Proof of Theorem 1.1.

Builder maintains a list of graphs $G_{1},G_{2},\dots,G_{n-1}$, where:

  * •

Each $G_{i}$ is a monochromatic red subgraph of the graph built so far.

  * •

Each $G_{i}$ is isomorphic to an “initial subgraph of $G$”: the subgraph
obtained by taking the leftmost $v(G_{i})$ vertices of $G$.

  * •

Each vertex of $G_{i}$ is the rightmost endpoint of a blue $P_{i}$.

Initially, every $G_{i}$ is the null graph (with $0$ vertices). Figure 3(a)
shows an example of an intermediate stage of Builder’s strategy, with graphs
$G_{1},G_{2},G_{3},G_{4}$ which are all subgraphs of $G=K_{4}$.

BBBBBBBBBBBBBBBBRRRRRRRR$G_{1}$:$G_{2}$:$G_{3}$:$G_{4}$: (a) An example of
graphs $G_{1},G_{2},G_{3},G_{4}$ and
the required blue paths

BBBBBBBBBBBBBBBBRRRRRRRRRBRRR$G_{1}$:$G_{2}$:$G_{3}$:$G_{4}$:$u$ (b) Comparing
$u$ to $G_{2}$ and $G_{3}$: the result is $G_{2}<u$ and $u\leq G_{3}$, so $u$
can be added to $G_{3}$

Figure 3: Builder’s strategy for Theorem 1.1, where $G=K_{4}$. The vertical
positions of vertices are only varied for clarity; in fact, the vertices on
different blue paths or in different $G_{i}$ are not required to be in any
particular order relative to each other, or even to be distinct.

Builder performs many iterations of adding a new vertex to some $G_{i}$. The
new vertex $u$ must be to the right of every previously considered vertex.

Each iteration consists of many steps we’ll call “comparing $u$ to $G_{i}$”.
To compare $u$ to $G_{i}$, Builder draws all the edges between $G_{i}$ and $u$
that make $G_{i}\cup\\{u\\}$ isomorphic to an initial subgraph of $v(G_{i})+1$
vertices of $G$; an example is shown in Figure 3(b). We say that the result of
the comparison is “$G_{i}<u$” if one of these edges is blue, and “$u\leq
G_{i}$” if all of these edges are red. Note that each comparison requires
drawing at most $\Delta^{-}(G)$ edges.

In $\lceil\lg n\rceil$ comparisons, Builder can find an $i$ such that
$G_{i-1}<u\leq G_{i}$, in which case $u$ can be added to $G_{i}$. (Since
$G_{i-1}<u$, $u$ is the leftmost vertex of a blue $P_{i}$; since $u\leq
G_{i}$, $G_{i}\cup\\{u\\}$ is monochromatic red.) As a special case, if $u\leq
G_{1}$, then $u$ can be added to $G_{1}$. As another special case, if
$G_{n-1}<u$, then $u$ is the leftmost endpoint of a blue $P_{n}$, and Builder
wins immediately.

After $(|V(G)|-1)(n-1)+1$ iterations, if Builder does not win earlier, then
some $G_{i}$ will have $|V(G)|$ vertices, and there is a red copy of $G$. ∎

Thus for any fixed graph $G$, we have $r_{o}(G,P_{n})=O(n\log n)$.

###  2.2 Replacing the path by the cycle

In this section, we prove Theorem 1.6 that $r_{o}(G,C_{n})$ may be bounded in
terms of $r_{o}(G,P_{m})$ up to a small additive constant. In fact, we can
make the following more precise claim. For all $k\geq 1$, there is a constant
$c_{k}$ such that if $G$ is any $k$-vertex ordered graph, then
$r_{o}(G,C_{n})\leq r_{o}(G,P_{kn-n-k+2})+c_{k}$.

To prove this theorem, we begin with three claims about steps in Builder’s
strategy. There is a common idea in all three proofs: if Builder draws an edge
$vw$ between two vertices of a blue cycle, and Painter colors it blue, then a
shorter blue cycle is created by skipping all vertices of the original cycle
between $v$ and $w$. We say that such an edge $vw$ has _length_ $\ell$ if
there are $\ell-1$ vertices of the cycle between $v$ and $w$.

To force Painter to color such edges blue, Builder may draw a copy of $G$
using vertices of the cycle. We say that such a copy of $G$ is _scaled by_
$\ell$ if there are $\ell-1$ vertices of the cycle between any two consecutive
vertices of $G$. Edges in such a copy of $G$ can have length
$\ell,2\ell,\dots,(k-1)\ell$. We will assume that Painter never colors a copy
of $G$ entirely red, because then Builder would win.

Builder may draw multiple scaled copies of $G$ on the same cycle to obtain
multiple blue edges, before skipping any vertices. In such a case, each copy
of $G$ is drawn to the right of all previous copies, so that all of the blue
edges (or only some of them) can be used to skip vertices together.

######  Claim 2.1.

For all $\epsilon>0$, if $n$ is sufficiently large, then starting from a blue
ordered cycle with length between $(1+2\epsilon)n$ and $kn$, Builder can force
either a blue ordered cycle with length between $(1+\epsilon)n$ and
$(1+2\epsilon)n$ or a red $G$ in $O(1)$ steps.

###### Proof.

Suppose that there is a blue $C_{(1+\epsilon)n+t}$ for some $t\geq\epsilon n$.
Builder draws a copy of $G$ scaled by $\left\lfloor\frac{t}{k-1}\right\rfloor$
on the cycle, obtaining a blue edge of length at least
$\left\lfloor\frac{t}{k-1}\right\rfloor$ and at most $t$. Builder uses this
edge to obtain a cycle with length at least $(1+\epsilon)n$ and at most
$(1+\epsilon)n+t-\left\lfloor\frac{t}{k-1}\right\rfloor$. For sufficiently
large $n$, this upper bound is at most $(1+\epsilon)n+(1-\frac{1}{k})t$.

After repeating this procedure up to $j$ times, Builder obtains a cycle with
length at least $(1+\epsilon)n$ and at most
$(1+\epsilon)n+(1-\frac{1}{k})^{j}t$. For
$j\geq\frac{\log(k/\epsilon)}{\log(k/(k-1))}$, the length of this cycle is
guaranteed to be in the range we want. ∎

######  Claim 2.2.

If $n$ is sufficiently large, then starting from a blue ordered cycle with
length between $(1+\frac{1}{2k^{2}})n$ and $(1+\frac{1}{k^{2}})n$, Builder can
force either a blue $C_{n+t}$ with $k^{3}\leq t\leq k^{3}+2(k-1)!$ or a red
$G$ in $O(1)$ steps.

###### Proof.

Let the given blue cycle have length $C_{n+k^{3}+\ell}$.

We assume that $n\geq 2k^{5}+2k^{2}(k-1)!$, so that $\ell\geq(k-1)!$. This
means that Builder can draw copies of $G$ scaled by
$\lfloor\ell/(k-1)!\rfloor$ on the cycle. Builder draws $k!$ such copies of
$G$; each one occupies fewer than $k\ell/(k-1)!$ vertices, for at most
$k^{2}\ell<n$ vertices.

For some $j\leq k-1$, at least $(k-1)!$ of these copies of $G$ give blue edges
of length $j\lfloor\ell/(k-1)!\rfloor$. Builder uses $(k-1)!/j$ of these edges
to shorten the cycle, removing
$\frac{(k-1)!}{j}(j\lfloor\ell/(k-1)!\rfloor-1)=(k-1)!\lfloor\ell/(k-1)!\rfloor-(k-1)!/j$
vertices total: between $\ell$ and $\ell-2(k-1)!$.

The result is a cycle of length between $n+k^{3}$ and $n+k^{3}+2(k-1)!$. ∎

######  Claim 2.3.

If $n$ is sufficiently large, then starting from a blue $C_{n+t}$ with $t\geq
k^{3}$, Builder can force either a blue $C_{n}$ or a red $G$ in $O(t)$ steps.

###### Proof.

Builder begins by drawing $kt$ copies of $G$ scaled by $1$ (that is, using
consecutive vertices of $C_{n+t}$). For some $j<k$, at least $t$ of these
copies give an edge of length $j$; let $E_{1}$ be a set of $t$ such edges.
Before using any of these edges, Builder continues by drawing $k$ copies of
$G$ scaled by $j-1$. Each of these gives an edge whose length is a multiple of
$j-1$; let $E_{2}$ be the set of all $k$ of these edges.

Each edge in $E_{2}$ can be used to decrease the length of the cycle by
$i(j-1)-1$ for $1\leq i\leq k-1$; this is at most $k^{2}$, and one less than a
multiple of $j-1$. Builder uses enough edges from $E_{2}$ to shorten the cycle
to length $C_{n+t^{\prime}}$ where $t^{\prime}\equiv 0\pmod{j-1}$; since
$t\geq k^{3}$, $t^{\prime}\geq 0$. Finally, Builder uses $t^{\prime}/(j-1)$ of
the edges from $E_{1}$ to shorten the cycle to length exactly $n$. ∎

###### Proof of Theorem 1.6.

In cases where $n$ is not large enough to apply Claim 2.1, Claim 2.2, or Claim
2.3, then $n$ is bounded by a function of $k$, and we can handle all such
cases by choosing $c_{k}$ large enough.

Otherwise, Builder first uses the $r_{o}(G,P_{nk-n-k+2})$ strategy to force
either a red $G$ (and win) or a blue $P_{nk-n-k+2}$, whose vertices we will
label $0,1,2,\dots,(k-1)(n-1)$. Then, Builder draws $G$ at vertices
$0,n-1,2(n-1),\dots,(k-1)(n-1)$.

If all edges of this copy of $G$ are red, then Builder immediately wins.
Otherwise, there is a blue edge between vertices $i(n-1)$ and $j(n-1)$ for
some $i<j$.

If $j=i+1$, then there is a blue $C_{n}$ and Builder also immediately wins.
Otherwise, one of the other edges drawn in the second step is red, and there
is a blue cycle with at least $2n-1$ and at most $kn-n-k$ vertices.

In this case:

  1. 1.

Builder executes the strategy of Claim 2.1, taking
$\epsilon=\frac{1}{2k^{2}}$, obtaining a blue ordered cycle with length
between $(1+\frac{2}{k^{2}})n$ and $(1+\frac{1}{k^{2}})n$.

  2. 2.

Builder executes the strategy of Claim 2.2, obtaining a blue ordered cycle
with length between $n+k^{3}$ and $n+k^{3}+2(k-1)!$.

  3. 3.

Builder executes the strategy of Claim 2.3; since $2(k-1)!=O(1)$, this also
takes $O(1)$ steps.

This procedure ends with either a blue $C_{n}$ or a red $G$. ∎

Remark: We make no effort to optimize the constant $c_{k}$ in this proof. The
length of $P_{nk-n-k+2}$ can also be improved in some cases; this exact length
is only required in the first step of the proof of the theorem. In particular,
if $G$ is $2$-ichromatic, then a path of length $n+k^{3}+k$ is enough. Builder
can draw $G$ using the first and last vertices of the path, such that all its
edges have length at least $n+k^{3}$, and then skip directly to applying Claim
2.3.

##  3 Results for $3$-ichromatic graphs

The results in the previous section bound $r_{o}(G,P_{n})$ for general ordered
graphs $G$. In this section, we show improved bounds when $G$ is
$3$-ichromatic. Equivalently, $G$ is a subgraph of $K_{a,b,c}$, an ordered
complete tripartite graph.

######  Lemma 3.1.

For all $a,b,c,d\geq 1$ and $n\geq a+b+c+2d$, suppose $G$ is a subgraph of
$K_{a,b,c}$ with $|E(G)|=m$. Then

$r_{o}(G,P_{n})\leq n\cdot\frac{2}{d}\cdot(m+r_{o}(G,P_{a+b+c+2d})).$

###### Proof.

For convenience, let $R=r_{o}(G,P_{a+b+c+2d})$; we will eventually use Theorem
1.1 to bound $R$. To keep track of Builder’s progress, we say that the graph
built so far is in state $(x,y)$ when it contains a blue $P_{x}$ followed by a
blue $P_{y}$, where $\min\\{x,y\\}\geq a+c$.

At the beginning of the game, Builder takes $R$ moves to create either a red
$G$ (and win) or a blue $P_{a+b+c+2d}$; then, Builder takes $R$ more moves to
do this again to the right of the previous $P_{a+b+c+2d}$. This results in
state $(a+b+c+2d,a+b+c+2d)$.

In state $(x,y)$, Builder first takes $R$ moves to create either a red $G$
(and win) or a blue $P_{a+b+c+2d}$ between the blue $P_{x}$ and the blue
$P_{y}$. Then, define sets $A,B,C$ as follows:

  * •

$A$: the last $a$ vertices of the blue $P_{x}$.

  * •

$B$: vertices $1+c+d$ through $b+c+d$ of the blue $P_{a+b+c+2d}$.

  * •

$C$: the first $c$ vertices of the blue $P_{y}$.

Builder takes $m$ moves to draw a copy of $G$ on vertex set $A\cup B\cup C$;
all edges of $G$ have their endpoints in two different sets.

If all these edges are red, Builder wins. If there is a blue edge between $A$
and $B$, it can be used to replace the blue $P_{x}$ by a blue path with at
least $x+d+2$ vertices, resulting in the state $(x+d+2,y)$. If there is a blue
edge between $B$ and $C$, it can be used to replace the blue $P_{y}$ by a blue
path with at least $y+d+2$ vertices, resulting in the state $(x,y+d+2)$.

Finally, if there is a blue edge between $A$ and $C$, it can be used to
combine the two blue paths into a single path with at least $x+y-a-c+2$
vertices. Then, Builder takes $R$ more moves to create either a red
$K_{a,b,c}$ (and win) or a blue $P_{a+b+c+2d}$ to the right of this single
path. This results in the state $(x+y-a-c+2,a+b+c+2d)$. (Note that
$x+y-a-c+2\geq a+c$, the minimum length we required.)

Altogether, one of two things has happened:

  * •

In $R+m$ moves from state $(x,y)$, Builder obtains a state
$(x^{\prime},y^{\prime})$ with $x^{\prime}+y^{\prime}=x+y+d+2$.

  * •

In $2R+m$ moves from state $(x,y)$, Builder obtains a state
$(x^{\prime},y^{\prime})$ with $x^{\prime}+y^{\prime}=x+y+b+2d+2$.

As the game goes on, the sum $x+y$ increases at a rate of at least $d$ every
$R+m$ moves, and the first $2R$ moves yield a state $(x,y)$ with $x+y>4d$. To
reach a state with $x+y\geq 2n$, it takes at most $\frac{2n}{d}-2$ repetitions
of $R+m$ moves; allowing for a final sequence of $2R+m$ moves to finish, at
most $\frac{2n}{d}\cdot(R+m)$ moves are required.

Therefore after Builder’s strategy is followed for $\frac{2n}{d}\cdot(R+m)$
moves, $x+y$ is at least $2n$, which means that either the blue $P_{x}$ or the
blue $P_{y}$ contains the $P_{n}$ we want. This results in a victory for
Builder. ∎

###### Proof of Theorem 1.2.

To deduce Theorem 1.2 from Lemma 3.1, first set $d=\frac{a+b+c}{2}$; then

$r_{o}(G,P_{n})\leq\frac{4n}{a+b+c}\left(m+r_{o}(G,P_{2a+2b+2c})\right)\leq\frac{8n}{a+b+c}\cdot
r_{o}(G,P_{2a+2b+2c})$

where the second inequality holds because $r_{o}(G,P_{2a+2b+2c})$ must
certainly be at least $m=|E(G)|$. By Theorem 1.1,
$r_{o}(G,P_{2a+2b+2c})\leq\Delta^{-}(G)|V(G)|(2a+2b+2c)\log(2a+2b+2c)$.
Recalling that $|V(G)|=a+b+c$, we obtain

$r_{o}(G,P_{n})\leq 16n\Delta^{-}(G)|V(G)|\log(2|V(G)|),$

which is $O(n|V(G)|^{2}\log|V(G)|)$. ∎

##  4 Small graphs vs $P_{n}$

In this section, we prove Theorem 1.4, giving us bounds on $r_{o}(G,P_{n})$
when $G$ is one of three small “bad” graphs: the path $P_{3}$, the
intersecting matching $X$, and the $2$-pronged claw $K_{1,2}$.

###  4.1 The first bad graph: $P_{3}$

To prove a lower bound on $r_{o}(P_{3},P_{n})$, we give a strategy for Painter
in Lemma 4.1. The upper bound in Lemma 4.2 is a strategy for Builder.

######  Lemma 4.1.

For all $n\geq 1$, $r_{o}(P_{3},P_{n})\geq 2n-2$.

###### Proof.

Let Painter use the following strategy: color an edge red if this does not
create a red $P_{3}$, blue otherwise.

Each blue edge that appears in the graph must therefore be adjacent to a red
edge. We call a blue edge $vw$ with $v<w$ _left-forced_ if $v$ has a red edge
from a preceding vertex, and _right-forced_ if $w$ has a red edge to a
following vertex. In either case, we say that the red edge _forces_ $vw$. Each
blue edge must be either left-forced or right-forced, or else it could have
been colored red. (It’s possible that a blue edge is both).

Suppose that the game continues until a blue $P_{n}$ is created. Let $uv,vw$
with $u<v<w$ be two consecutive edges of that path. Then it is impossible for
$uv$ to be right-forced and $vw$ to be left-forced; in that case, $v$ would
have a red edge both from a preceding vertex and to a following vertex, and a
red $P_{3}$ would already have existed.

Therefore, the blue $P_{n}$ must consist of a segment (possibly empty) of
left-forced edges, followed by a segment (possibly empty) of right-forced
edges.

Each left-forced edge is forced by a red edge to its first endpoint from a
preceding vertex, and these edges are all different (because their second
endpoint is different). Each right-forced edge is forced by a red edge from
its second endpoint to a following vertex, and these edges are all different
(because their first endpoint is different). The red edges forcing the left-
forced edges must be different from the red edges forcing the right-forced
edges, because each of the former edges ends to the left of where each of the
latter edges begins.

Therefore the $n-1$ blue edges of the blue $P_{n}$ are forced by $n-1$
distinct red edges, and there must be at least $2(n-1)$ edges total. ∎

######  Lemma 4.2.

For all $n\geq 1$, $r_{o}(P_{3},P_{n})\leq\frac{8}{3}n-\frac{10}{3}.$

For this proof, we define the _claw strategy_ for Builder to be the following.
At all times, Builder keeps track of a $k$-vertex blue path, and $\ell$
vertices which are the right endpoints of a red edge: we call these _leftover
vertices_. The strategy may start with $k=1$ and $\ell=0$ by picking any
vertex to be the single vertex of a blue $P_{1}$.

On each step of the claw strategy, Builder draws an edge from the rightmost
vertex of the blue path to the leftmost vertex Builder is not yet tracking. If
it is blue, then the blue path is extended; if it is red, then there is an
additional leftover vertex. As a result, after $s$ steps, $k+\ell\geq s+1$.
(Conversely, it takes at most $k_{0}+\ell_{0}-2$ steps to guarantee that
either $k\geq k_{0}$ or that $\ell\geq\ell_{0}$.) One possible result of
several steps of the claw strategy is shown in Figure 4.

RRRRRBBBBLLLLL Figure 4: One possible outcome of the claw strategy after $9$
steps, resulting in a $5$-vertex blue path and $5$ leftover vertices (marked
with an L)

The claw strategy may be performed in reverse: extending a path from the left,
and obtaining leftover vertices which are the left endpoints of a red edge.

###### Proof of Lemma 4.2.

The first phase of Builder’s strategy follows the claw strategy for $n-1$
steps, creating a blue path of length $k$ and $n-k$ leftover vertices, where
$1\leq k\leq n$. The value of $k$ is under Painter’s control.

The second phase of Builder’s strategy follows the claw strategy in reverse,
skipping ahead far enough that all vertices used in the second phase are to
the right of all vertices used in the first phase. It lasts for a variable
number of steps, depending on $k$:

  * •

When $k\geq\frac{n+1}{3}$, the second phase lasts $n-2$ steps, creating either
a blue $k$-vertex path or $n-k$ leftover vertices.

  * •

When $k\leq\frac{n}{3}$, the second phase lasts $2k-2$ steps, creating either
a blue $k$-vertex path or $k$ leftover vertices.

The final phase of Builder’s strategy depends on the outcome of the second
phase.

Case 1: $k\geq\frac{n+1}{3}$ and a blue $k$-vertex path is created in the
second phase. In this case, Builder’s last $n-k$ moves extend this path
through all the leftover vertices of the first phase. If Painter colors any of
these edges red, a red $P_{3}$ is formed; otherwise, a blue $P_{n}$ is formed.
The total number of steps is $(n-1)+(n-2)+(n-k)=3n-k-3\leq\frac{8n-10}{3}$.

Case 2: $k\leq\frac{n}{3}$ and a blue $k$-vertex path is created in the second
phase. Builder’s follow-up is the same as in case 1. The total number of steps
is $(n-1)+(2k-2)+(n-k)=2n+k-2\leq\frac{7n-6}{3}$.

Case 3: $k\geq\frac{n+1}{3}$ and $n-k$ leftover vertices are created in the
second phase. In this case, Builder’s last $n-k$ moves extend the blue
$k$-vertex path from the first phase through the leftover vertices of the
second phase. If Painter colors any of these edges red, a red $P_{3}$ is
formed; otherwise, a blue $P_{n}$ is formed. The total number of steps is
$(n-1)+(n-2)+(n-k)=3n-k-3\leq\frac{8n-10}{3}$.

Case 4: $k\leq\frac{n}{3}$ and $k$ leftover vertices are created in the second
phase. In this case, Builder’s last $n-1$ moves build a path through the
leftover vertices of both phases: $n$ vertices total. If any of these edges
are red, a red $P_{3}$ is formed; otherwise, a blue $P_{n}$ is formed. The
total number of steps is $(n-1)+(2k-2)+(n-1)\leq\frac{8n-12}{3}$.

In all cases, Builder wins in at most $\frac{8}{3}n-\frac{10}{3}$ steps. ∎

###  4.2 The second bad graph: $X$

######  Lemma 4.3.

We have

$\frac{3(n-1)}{2}\leq r_{o}(X,P_{n})\leq\frac{5}{3}n+10.$

###### Proof.

To prove the lower bound, assume Painter follows the strategy of coloring each
edge red unless a red copy of $X$ is created. Builder wins the game when
Painter creates a blue copy of $P_{n}$. Each edge of this blue path must
intersect a red edge, and each red edge can intersect at most two of the blue
path edges. Therefore, there must be a total of at least $n-1$ blue edges and
$\frac{n-1}{2}$ red edges when Builder wins, giving
$r_{o}(X,P_{n})\geq\frac{3(n-1)}{2}$.

For the upper bound, we present a strategy for Builder which will keep track
of a long blue path $P$. For $k\geq 1$, we say that we are in state $k$ if
there is a blue copy of $P_{k}$ and at most $\frac{5}{3}(k-1)$ edges have been
presented so far. Note that initially we are in state 1. By the following
argument we can reach state 2 or 3. Builder plays some edge $bd$. If it is
blue, we reach state 2 immediately. If it is red, Builder plays edges $ac$ and
$ce$ where $a<b<c<d<e$. If one of those two edges is red, a red copy of $X$
has been created and Builder wins. If both of them are blue, we reach state 3.

Assume that Builder is in state $k$ for some $k\geq 2$. Then there exists a
blue $P_{k}$: $v_{1},v_{2},\ldots,v_{k}$. We will show that either a red $X$
is created by playing at most $10$ edges, or we reach some state $k^{\prime}$
for $k<k^{\prime}\leq n+4$. Thus, by repeating this procedure often enough,
Builder wins the game in at most $\frac{5}{3}n+10$ moves.

$v_{1}$$\cdots$$v_{k}$$y$$a$$z$$b$RBBBB (a) $e=yz$ is red

$v_{1}$$\cdots$$v_{k}$$\cdots$$x^{\prime}$$u_{\ell}$$x^{\prime\prime}$$u_{\ell+1}$$x$$y$$z$BBBBBRBBBB
(b) $e=yz$ is blue, $e^{\prime}=xy$ is blue

$v_{1}$$\cdots$$v_{k}$$x$$\beta$$y$$z$$\alpha_{1}$$\alpha_{2}$BBBBBBR (c)
$e=yz$ is blue, $e^{\prime}=xy$ is red, $e_{3}=\alpha_{1}\alpha_{2}$ is blue

$v_{1}$$\cdots$$v_{k}$$x$$\beta$$y$$z$$\gamma_{1}$$\alpha_{1}$$\gamma_{2}$$\alpha_{2}$$\alpha_{3}$$\alpha_{4}$BBBBBBBBRR
(d) $e=yz$ is blue, $e^{\prime}=xy$ is red, $e_{3}=\alpha_{1}\alpha_{2}$ is
red, $e_{4}=\alpha_{3}\alpha_{4}$ is blue

$v_{1}$$\cdots$$v_{k}$$x$$w_{1}$$y$$z$$w_{2}$$\alpha_{1}$$w_{3}$$\alpha_{2}$$w_{4}$$\alpha_{3}$$w_{5}$$\alpha_{4}$$w_{6}$BBBBBBBBBRRR
(e) $e=yz$ is blue, $e^{\prime}=xy$ is red, $e_{3}=\alpha_{1}\alpha_{2}$ is
red, $e_{4}=\alpha_{3}\alpha_{4}$ is red

Figure 5: All major cases of Builder’s strategy in the proof of Lemma 4.3
(cases where a red copy of $X$ is created are not shown)

Builder presents an edge $e=yz$ where $v_{k}<y<z$. If $e$ is red, then Builder
plays the edges $v_{k}a$ and $ab$, where $v_{k}<y<a<z<b$. If one of those two
edges is red, a red copy of $X$ is created. Thus, $v_{k}a$ and $ab$ are blue,
extending $P$ by two and having played in total at most
$\frac{5}{3}(k-1)+3\leq\frac{5}{3}(k+1)$ edges (see Figure 5(a)). We reach
state $k+2$. In the following assume that $e$ is blue.

Builder presents an edge $e^{\prime}=xy$ where $v_{k}<x<y$. First, we analyze
the case that $e^{\prime}$ is blue. Builder keeps presenting edges
$e_{i}=u_{i}u_{i+1}$ where $v_{k}=u_{1}\leq u_{i_{i}}<u_{i+1}<x$ until the
first time one of those new edges is painted red or a blue $P_{n}$ is created.
If a blue $P_{n}$ is created, Builder wins having played in total at most
$\frac{5}{3}k+(n-k)+2\leq\frac{5}{3}n+10$ edges. Otherwise, there exists
$\ell<n-k$ such that the edges $e_{1},e_{2},\ldots,e_{\ell-1}$ are all blue
and $e_{\ell}$ is red. The blue path $P$ has been extended to a blue path
$P^{\prime}$ of length $k+\ell-1$. Let $x^{\prime}$ be the second to last
vertex in this newly created blue path. Now, Builder presents edges
$x^{\prime}x^{\prime\prime}$ and $x^{\prime\prime}x$ where
$x^{\prime}<u_{\ell}<x^{\prime\prime}<u_{\ell+1}$. If one of them is red, a
red $X$ has been created in at most
$\frac{5}{3}(k-1)+\ell+2\leq\frac{5}{3}n+10$ moves totally. If both of them
are blue, the blue path $P$ has been extended by length $\ell+2$ in at most
$\ell+4$ moves, and since $\ell\geq 1$ we reach some state $k^{\prime}$ for
$k<k^{\prime}\leq n+1$ (see Figure 5(b)).

Next, we analyze the case that $e^{\prime}$ is red. Builder plays an edge
$e_{3}=\alpha_{1}\alpha_{2}$ where $z<\alpha_{1}<\alpha_{2}$. If $e_{3}$ is
blue, Builder plays edges $v_{k}\beta$ and $\beta\alpha_{1}$ where
$x<\beta<y$. If either of those edges is red, a red copy of $X$ is created and
Builder wins, or they are both blue, in which case we reach state $k+3$ since
$P$ got extended by length $3$ and $5$ edges had been played (see Figure
5(c)).

If $e_{3}$ is red, Builder plays an edge $e_{4}=\alpha_{3}\alpha_{4}$ where
$\alpha_{2}<\alpha_{3}<\alpha_{4}$. If this edge is blue, Builder plays the
edges $v_{k}\beta$, $\beta\gamma_{1}$, $\gamma_{1}\gamma_{2}$ and
$\gamma_{2}\alpha_{3}$ where
$x<\beta<y<\gamma_{1}<\alpha_{1}<\gamma_{2}<\alpha_{2}$. Either one of those
four edges is red, in which case a red $X$ is created and Builder wins, or all
four edges are blue, in which case we reach state $k+5$ having played $8$ new
edges (see Figure 5(d)). If $e_{4}$ is red, Builder plays 6 edges:
$v_{k}w_{1},w_{1}w_{2},w_{2}w_{3},w_{4}w_{5},w_{5}w_{6}$, where
$v_{k}<x<w_{1}<y<w_{2}<\alpha_{1}<w_{3}<\alpha_{2}<w_{4}<\alpha_{3}<w_{5}<\alpha_{4}<w_{6}$.
Either one of those six edges is red, in which case a red $X$ is created and
Builder wins, or all six edges are blue, in which case we reach state $k+6$
having played $10$ new edges (see Figure 5(e)). ∎

###  4.3 The third bad graph: $K_{1,2}$

The graph $K_{1,2}$ is unique among the bad graphs of Theorem 1.4 in that we
can determine the exact value of $r_{o}(K_{1,2},P_{n})$. In fact, we can find
$r_{o}(K_{1,k},P_{n})$ exactly for all $k$.

######  Lemma 4.4.

For all $n,k\geq 1$, $r_{o}(K_{1,k},P_{n})=k(n-1)$.

###### Proof.

For the lower bound, Painter’s strategy is to color every edge red, except if
a red copy of $K_{1,k}$ is created. Builder wins the game when a blue copy of
$P_{n}$ is created. Let $vw$ be an edge of this path, with $v<w$; in order for
Painter to color $vw$ blue, there must have been a red copy of $K_{1,k-1}$
whose leftmost vertex is $v$. In total, there are $n-1$ red copies of
$K_{1,k-1}$, all with distinct edges; together with the $n-1$ blue edges of
$P_{n}$, there are at least $k(n-1)$ edges total.

For the upper bound, Builder will successively build a blue path $P$;
initially, $P$ consists of a single arbitrary vertex. When $P=v_{1}v_{2}\dots
v_{s}$ for some $s\geq 1$, Builder chooses vertices $w_{1},\dots,w_{k}$ to the
right of $v_{s}$ and plays the $k$ edges
$\\{v_{s}w_{1},v_{s}w_{2},\dots,v_{s}w_{k}\\}$. If all $k$ edges are red, a
red copy of $K_{1,k}$ is created and Builder wins. If $v_{s}w_{i}$ is blue for
some $i$, then $P$ can be extended to $v_{1}v_{2}\dots v_{s}w_{i}$. Every $k$
moves, Builder is able to extend $P$ by one more vertex; thus Builder wins in
$k(n-1)$ moves. ∎

##  5 Results for matchings

###  5.1 Serial matchings

In this section, we analyze the online Ramsey number $r_{o}(M_{k},P_{n})$,
where $M_{k}$ is the serial $k$-edge matching. This case is notable for two
reasons. First, $M_{k}$ is the instance we see of graphs $G$ such that
$r_{o}(G,P_{n})=n+O(1)$ as $n\to\infty$. Second, we will be able to find
$r_{o}(M_{k},P_{n})$ exactly, when $n$ is sufficiently large compared to $k$.

We will prove Theorem 1.3 in two steps. We begin with the upper bound on
$r_{o}(M_{k},P_{n})$, which is a strategy for Builder.

######  Lemma 5.1.

If $n\geq 4$ and $k\geq 2$, then $r_{o}(M_{k},P_{n})\leq n+2k-4$.

###### Proof.

In this proof, we assume that Builder takes care to space out vertices so that
it is always possible to play a vertex between any two existing vertices.

To keep track of Builder’s progress, we say that the graph built so far is in
state $(x,y)$ if it contains a blue $P_{x}$ followed by a red $M_{y}$, and we
assign state $(x,y)$ the _weight_ $x+2y$. The empty graph is in state $(1,0)$
with weight $1$, because a blue $P_{1}$ is just a vertex. A graph with no red
$M_{k}$ or blue $P_{n}$ must be in a state with weight at most
$n-1+2(k-1)=n+2k-3$.

In state $(x,y)$, let $v_{1},v_{2},\dots,v_{x}$ be the vertices of the blue
$P_{x}$ in order, and let $w$ be a vertex to the right of $v_{x}$ and to the
left of the red $M_{y}$. Suppose Builder plays the edge $v_{x}w$. Then:

  * •

If $v_{x}w$ is blue, the graph now contains a blue $P_{x+1}$ (the path
$v_{1}v_{2}\dots v_{x}w$) followed by a red $M_{y}$, so it is in state
$(x+1,y)$;

  * •

If $v_{x}w$ is red, the graph now contains a blue $P_{x-1}$ (the path
$v_{1}v_{2}\dots v_{x-1}$) followed by a red $M_{y+1}$ (edge $v_{x}w$ together
with the previous $M_{y}$), so it is in state $(x-1,y+1)$.

In both cases, the new state of the graph has weight $x+2y+1$: it increases by
$1$. This argument alone proves $r_{o}(M_{k},P_{n})\leq n+2k-3$: after
$n+2k-3$ repetitions of the move above from state $(1,0)$, Builder reaches a
state $(x,y)$ with weight $n+2k-2$, so either $x\geq n$ or $y\geq k$.

To improve this bound by $1$, we refine the strategy. We say that the graph is
in state $(1,x,y)$ if there is a path $P_{1+x}$ whose first edge is red and
all other edges are blue, followed by a red $M_{y}$; we assign this state
weight $x+2y+2$. It remains the case that when the graph is in a state
$(1,x,y)$ with weight at least $n+2k-2$, it contains a red $M_{k}$ or a blue
$P_{n}$.

From state $(1,x,y)$ with $x>1$, Builder can follow the strategy above to
obtain state $(1,x+1,y)$ or $(1,x-1,y+1)$ in one move, increasing the weight
by $1$. State $(1,1,y)$ carries the same information as state $(1,y+1)$ and
has the same weight, so if the graph reaches such a state, we switch to
treating it as state $(1,y+1)$.

Builder begins with an “opening,” laying down a path starting at a vertex and
going left, until the first time Painter colors an edge of this path red.
Either Builder wins in $n-1<n+2k-4$ steps, or else achieves state $(1,x,0)$ in
$x$ steps, which has weight $x+2$. From here, Builder can follow the strategy
above to increase weight by at least $1$ with every step. In $n+2k-4$ steps, a
state with weight $n+2k-2$ is reached, guaranteeing that Builder wins. ∎

For sufficiently large $n$, Painter has a simple counter-strategy: Painter
colors every edge blue unless this would create a blue $P_{n}$. In the lemma
that follows, we prove that this strategy avoids losing in fewer than $n+2k-4$
moves when $n\geq 3k-3$ and $k\geq 2$, completing the proof of Theorem 1.3.

######  Lemma 5.2.

If $k\geq 2$ and $n\geq 3k-3$, then $r_{o}(M_{k},P_{n})\geq n+2k-4$.

###### Proof.

When Painter colors every edge blue unless this would create a blue $P_{n}$,
the end state of the game is an ordered graph $G$ with $k$ red edges forming a
red $M_{k}$. (We may assume that Builder does not play any other edges that
Painter would color red.) We will show that $G$ must contain at least $n+2k-4$
edges.

As a consequence of Painter’s strategy, $G$ does not contain a blue $P_{n}$.
Moreover, every red edge $e\in E(G)$ must be part of a $P_{n}$ in $G$ in which
$e$ is the only red edge. (Otherwise, Painter would have colored $e$ blue.) It
follows that if $vw$ is a red edge, then there is no blue $v-w$ path in $G$:
otherwise, replacing $vw$ by the blue $v-w$ path would create a path of length
at least $n$ in $G$ with no red edges.

Define a path $P^{*}$ as follows.

  1. 1.

If there is a $P_{n+1}$ in $G$ in which the first and last edges are red, and
all others are blue, let $P^{*}$ be this $P_{n+1}$.

  2. 2.

Otherwise, if there is a $P_{n}$ in $G$ in which the first or last edge is
red, and all others are blue, let $P^{*}$ be this $P_{n}$. (Note that in this
case, the other end of $P^{*}$ is not incident to a red edge, or else we would
be in the first case.)

  3. 3.

Otherwise, choose any edge $e$, and let $P^{*}$ be a $P_{n}$ in $G$ in which
$e$ is the only red edge.

In all cases, $P^{*}$ contains $n-2$ blue edges and either $1$ or $2$ red
edges.

We call every vertex of $P^{*}$ that is not incident on a red edge of $P^{*}$
an _anchor_. Furthermore, we assign a direction (“left” or “right”) to each
anchor by the following algorithm:

  1. 1.

If an anchor is the rightmost vertex of a blue $P_{n-k}$ in $G$, label it a
_left anchor_.

  2. 2.

If an anchor is the leftmost vertex of a blue $P_{n-k}$ in $G$, label it a
_right anchor_. No anchor will fall in both categories: this would imply the
existence of a blue $P_{2n-2k-1}$, which contains a blue $P_{n}$.

  3. 3.

At this point, if there is a left anchor to the left of a right anchor, the
corresponding paths are disjoint and have $2(n-k-1)$ blue edges; together with
the $k$ red edges, we get $2n-k-1$, which is at least $n+2k-4$ when $n\geq
3k-3$.

Assign directions to the other anchors arbitrarily so that this rule continues
to hold: no left anchor is to the left of a right anchor.

It suffices to show that that in $G-P^{*}$, there are at least as many blue
edges as red edges. When $P^{*}$ has $n-2$ blue edges and $1$ red edge, this
would give us $k-1$ red edges and at least $k-1$ blue edges in $G-P^{*}$, for
a total of at least $n+2k-3$. When $P^{*}$ has $n-2$ blue edges and $2$ red
edges, this would give us $k-2$ red edges and at least $k-2$ blue edges in
$G-P^{*}$, for a total of at least $n+2k-4$. To prove this, we will consider
the connected components of $G-P^{*}$, and show that each one has at least as
many blue edges as red edges.

Let $C$ be a connected component of $G-P^{*}$ with $j$ red edges. If $C$ has
$2j+1$ or more vertices, then it must have at least $2j$ edges, and we are
done. Therefore, assume that $C$ has only $2j$ vertices: the endpoints of the
$j$ red edges of $C$.

If a vertex $v$ of $C$ is incident to any edges not in $C$, those edges are in
$P^{*}$, and therefore $v$ must be a vertex of $P^{*}$. Since all vertices of
$C$ are incident to a red edge in $C$, $v$ cannot be incident to any red edge
in $P^{*}$; therefore $v$ is only incident to blue edges in $P^{*}$, so it
must be an anchor.

We classify each red edge of $C$ as

  * •

strong, if its right endpoint is a right anchor, or if its left endpoint is a
left anchor. Let $j_{1}$ be the number of strong edges in $C$.

  * •

weak, if neither of its endpoints is an anchor. Let $j_{2}$ be the number of
weak edges in $C$.

  * •

weird, if its right endpoint is a left anchor, or if its left endpoint is a
right anchor. Let $j_{3}$ be the number of weird edges in $C$.

Examples of this classification are shown in Figure 6.

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$x_{8}$$\cdots$$y_{1}$$y_{2}$$y_{3}$$y_{4}$RRRBBRBBBBBBBRight
anchors Figure 6: Part of path $P^{*}$ with vertices $x_{1},x_{2},x_{3},\dots$
and part of a component $C$ of $G-P^{*}$; edge $y_{1}x_{4}$ is strong, edge
$y_{2}y_{3}$ is weak, and edge $x_{6}y_{4}$ is weird

It is impossible for both endpoints of a red edge to be anchors. If they are
on the same blue segment of $P^{*}$, then there is a blue path between the
endpoints of that red edge, which we ruled out earlier. If they are on
different blue segments of $P^{*}$, then there is a red edge between the
endpoints of another red edge, which violates our assumption that the red
edges form an $M_{k}$. Therefore every red edge is exactly one of strong,
weak, or weird, and $j_{1}+j_{2}+j_{3}=j$.

Let $vw$ be a strong edge where $v$ is a right anchor. Suppose $v$ is the
rightmost vertex of a blue $P_{n-1}$; then $P^{*}$ must also contain a blue
$P_{n-1}$, and $v$ cannot be the rightmost endpoint of the blue $P_{n-1}$
contained in $P^{*}$, or else $vw$ would be part of $P^{*}$. Therefore $v$ is
a vertex on $P^{*}$ with a blue edge going left from $v$, but this creates a
blue $P_{n}$, a contradiction. We conclude that $v$ is not the rightmost
vertex of a blue $P_{n-1}$. Since $vw$ is part of a $P_{n}$ in which it is the
only red edge, there must be a blue edge going right from $w$. That blue edge
is part of $C$, since $w$ is not an anchor. By similar reasoning, if $vw$ is a
strong edge where $w$ is a left anchor, then there must be a blue edge in $C$
going left from $v$.

Every weak edge must be part of a $P_{n}$ in which it is the only red edge; if
this $P_{n}$ is entirely contained in $C$, then $C$ has $n-2\geq k\geq j$ blue
edges, and we are done. Otherwise, the blue $P_{n}$ must leave $C$; therefore,
there is a blue path in $C$ from the weak edge to an anchor.

Let $vw$ be a weird edge; without loss of generality, $w$ is a left anchor.
There must be a $P_{n}$ containing $vw$ where it is the other blue edge; this
decomposes into a blue $P_{a}$ whose rightmost vertex is $v$, and a blue
$P_{b}$ whose leftmost endpoint is $w$, with $a+b=n$. Because $w$ is not a
right anchor, $b<n-k$, and therefore $a\geq k$. However, a blue path in $C$
can only contain one endpoint from each of the $j\leq k-1$ red edges, so we
can have no more than a $P_{k-1}$ entirely contained in $C$. Therefore the
blue $P_{a}$ must leave $C$: there is a blue path in $C$ from $v$ to an
anchor. Similarly, if $vw$ is a weird edge where $v$ is a right anchor, there
must be a blue path in $C$ from $w$ to an anchor.

Let $C^{\prime}$ be the subgraph of $C$ consisting of all $j_{2}$ weak edges,
all $j_{1}+j_{3}$ anchors, and all the blue paths found in the previous two
paragraphs. Let $i\geq 0$ be the number of non-anchor vertices of strong edges
included in $C^{\prime}$. In total, $C^{\prime}$ contains
$i+j_{1}+2j_{2}+2j_{3}$ vertices; it has at most $j_{1}+j_{3}$ connected
components, since every vertex is in a connected component with one of the
anchors. Therefore $C^{\prime}$ has at least
$(i+j_{1}+2j_{2}+2j_{3})-(j_{1}+j_{3})=i+2j_{2}+j_{3}$ edges. Only $j_{2}$
edges of $C^{\prime}$ are red, so $C^{\prime}$ has $i+j_{2}+j_{3}$ blue edges.

There are $j_{1}-i$ non-anchor vertices of strong edges which are not included
in $C^{\prime}$. By a previous claim, each of these must be incident to a blue
edge in $C$ (but not in $C^{\prime}$). Moreover, since (in $G$, and therefore
also in $C$) no left anchor is to the left of a right anchor, these edges
consist of some number of blue edges going left from a red edge, followed by
some number of blue edges going right from a red edge. Therefore these
$j_{1}-i$ non-anchor vertices must have $j_{1}-i$ additional blue edges.

The total number of blue edges is
$(i+j_{2}+j_{3})+(j_{1}-i)=j_{1}+j_{2}+j_{3}=j$. Therefore $C$ contains at
least $j$ blue edges, which was what we wanted. ∎

The lower bound $n\geq 3k-3$ might not be optimal, and it is even possible
that $r_{o}(M_{k},P_{n})=n+2k-4$ for all $n,k$ such that $n,k\geq 2$ (avoiding
some strange behavior when $k=1$ or $n=1$). However, Painter’s strategy of
coloring every edge blue when this does not lose the game assumes that $n$ is
large compared to $k$; when $n<k$, Builder can exploit it.

$9$$10$$14$$15$$20$$25$$30$$31$$35$$36$$40$$45$RRRRRRBBBBB Figure 7: Builder’s
exploit of Painter’s strategy when $n=4$ and $k=6$. Edges $(10,20)$,
$(20,30)$, $(15,25)$, $(25,35)$ are played first, then edges $(9,10)$,
$(14,15)$, $(20,25)$, $(30,31)$, $(35,36)$, then edge $(20,40)$ and edge
$(40,45)$.

When $n<k$ and Painter is known to follow this strategy, Builder begins by
playing two copies of $P_{n-1}$: one on vertices $10,20,30,\dots,10n-10$ and
one on vertices $15,25,35,\dots,10n-5$. Because no blue $P_{n}$ is created,
Painter colors all $2n-4$ edges blue. However, now Builder can play edges

$\\{9,10\\},\\{14,15\\},\\{20,25\\},\dots,\\{10n-20,10n-15\\},\\{10n-10,10n-9\\},\\{10n-5,10n-4\\}$

and Painter must color each of these red, creating an $M_{n+1}$ in just $3n-3$
moves total: this is $n+2(n+1)-5$. Builder can then play edges
$\\{10n-20,10(n+i)\\}$ and $\\{10(n+i),10(n+i)+5\\}$ for $i=1,\dots,k-n-1$.
Painter colors the first edge blue and the second edge red for each $i$,
increasing the red matching from $M_{n+1}$ to $M_{k}$ in $2(k-n-1)$ more
moves: $n+2k-5$ moves total. An example where $n=4$ and $k=6$ is illustrated
in Figure 7.

This argument partially justifies the need for a lower bound on $n$ in Theorem
1.3, though it is possible that Painter has a more refined strategy that does
not require it.

###  5.2 The partial St. Ives matching

Recall that the partial St. Ives matching $S_{k}^{\prime}$ is obtained from a
nested $k$-edge matching by adding $k$ more consecutive nested $k$-edge
matchings inside it. In this final section of the paper, we prove Theorem 1.5
that for all $k$ there is a constant $c_{k}$ such that
$r_{o}(S_{k}^{\prime},P_{n})\leq n+c_{k}$. Throughout this proof, we write
$r(n_{1},n_{2})$ for the Ramsey number of two cliques,
$r(K_{n_{1}},K_{n_{2}})$; note that this is the same as
$r_{o}(K_{n_{1}},K_{n_{2}})$, since all vertex orderings of a clique are
isomorphic as ordered graphs.

For $0\leq b\leq(k+1)k$, we define a family of $b$-edge subgraphs of
$S_{k}^{\prime}$ called $\mathcal{S}_{k}^{\prime}[b]$. When $b\leq 2k$, the
family $\mathcal{S}_{k}^{\prime}[b]$ includes only one graph: a nested
matching of size $b$, whose inmost edge is denoted by $e_{b}$. When $b>2k$,
the family $\mathcal{S}_{k}^{\prime}[b]$ includes all ordered graphs
consisting of one nested matching of size $k$ and $\lceil\frac{b}{k}\rceil-1$
further nested matchings inside it. These $\lceil\frac{b}{k}\rceil-1$
matchings are consecutive and disjoint; $\lfloor\frac{b}{k}\rfloor-1$ of them
have size $k$ and, if $k\nmid b$, one of them has size $b\bmod k$. If $k\nmid
b$, we denote the inmost edge of the matching of size $b\bmod k$ by $e_{b}$.

Note that when $b>2k$, the family $\mathcal{S}_{k}^{\prime}[b]$ includes
multiple ordered graphs, since we do not specify the location of the nested
matching of smaller size.

For $b\in[(k+1)^{2}]\setminus\\{2k,3k,\ldots,k^{2}\\}$ and
$a\geq(k+1)^{3}-bk$, we say that we are in state $(a,b)$ if there exists a
blue $P_{a}$ and a red $S\in\mathcal{S}_{k}^{\prime}[b]$ where the last
$(k+1)^{3}-bk$ vertices of the blue path are between the two endpoints of the
edge $e_{b}$.

For $b\in\\{2k,3k,\ldots,k^{2}\\}$ and $a\geq(k+1)^{3}-bk$, we say that we are
in state $(a,b)$ if there exists a blue $P_{a}$ and a red
$S\in\mathcal{S}_{k}^{\prime}[b]$ where the last $(k+1)^{3}-bk$ vertices of
the blue path are either before or after all of the inside copies of the red
nested matchings in $S$, or between two consecutive copies of nested matchings
in $S$.

We will show that either in one move we increase the first coordinate of our
states by 1 or in a constant number of moves the second coordinate by 1 while
the first coordinate only decreases by at most a constant. Builder wins when a
state $(n^{\prime},b)$ for some $n^{\prime}\geq n$ and $b\geq 0$ or a state
$(a,(k+1)k)$ for some $a\geq 0$ is reached.

Let $v_{a}$ be the last vertex in the blue $P_{a}$.

######  Claim 5.1.

There exists $c_{k}>0$ such that Builder can reach state $((k+1)^{3},0)$ in at
most $c_{k}$ moves.

###### Proof.

Builder simply plays all edges of a clique of size $r((k+1)^{3},2(k+1)^{2})$
which is a constant depending only on $k$. Then either there exists a red
clique of size $2(k+1)^{2}$, and therefore in particular a red
$S\in\mathcal{S}_{k}^{\prime}$, or a blue clique of size $(k+1)^{3}$, and
therefore in particular a blue $P_{(k+1)^{3}}$. ∎

######  Claim 5.2.

There exists $c_{k}>0$ such that the following holds. If we are in state
$(a,b)$ with $a\geq(k+1)^{3}-bk$ and $b\not\in\\{2k-1,3k-1,\ldots,k^{2}-1\\}$
we reach state $(a+1,b)$ in 1 move or $(a^{\prime},b+1)$ in at most $c_{k}$
moves for some $a^{\prime}\geq a$.

###### Proof.

We start by defining an interval $[u_{b},w_{b}]$ in which all new edges for
the following rounds will be played.

If $b\geq 1$, there exists a blue $P_{a}$ and a red
$S\in\mathcal{S}_{k}^{\prime}[b]$ where the last $(k+1)^{3}-bk$ vertices of
the blue path are between the two endpoints of the edge $e_{b}$. We denote by
$u_{a}$ the first vertex to the left of the last-$(k+1)^{3}$ vertices of
$P_{a}$ which is incident to the red $S$. Further, we define $u_{b}$ to be the
first vertex to the right of the last vertex of $P_{a}$ which is incident to
the red $S$.

If $b=0$, there exists a blue $P_{a}$. Denote by $u_{b}$ the vertex one to the
left of the $(k+1)^{3}$ last vertex in $P_{a}$, and denote by $w_{b}$ an
arbitrary vertex to the right of the last vertex in $P_{a}$.

Note that $u_{b}<v_{a}<w_{b}$. In this case Builder plays an edge from $v_{a}$
to a vertex $w$ such that $u_{b}<v_{a}<w<w_{b}$.

If $v_{a}w$ is painted blue, we reached state $(a+1,b)$ in 1 move. If $v_{a}w$
is painted red, Builder plays all edges of a clique of size
$r((k+1)^{3},2(k+1)^{2})$ where all the vertices of this clique are between
$v_{a}$ and $w$. Then either there exists a red clique of size $2(k+1)^{2}$ or
a blue clique of size $(k+1)^{3}$ and therefore in a particular a blue
$P_{(k+1)^{3}}$. In the first case, Builder created a red $S_{k}^{\prime}$ and
therefore wins in a total of at most $a+c_{k}$ moves for some constant
$c_{k}>0$.

Now assume Builder created a blue path of length $(k+1)^{3}$. Let $z^{\prime}$
be the first vertex in this blue path of length $(k+1)^{3}$ and $z$ be the
$((k+1)^{3}-bk)$-last vertex in the blue $P_{a}$. Now, Builder plays the edge
$zz^{\prime}$.

  * •

If $zz^{\prime}$ is painted blue, Builder has created a blue path of length
$a^{\prime}=a-((k+1)^{3}-bk)+(k+1)^{3}\geq a$ and a red $S_{k}^{\prime}[b+1]$
(with $v_{a}w$ being the new red edge $e_{b+1}$) where the last $(k+1)^{3}$
vertices of the blue path are between the two endpoints of the edge $e_{b+1}$.
Therefore we reached state $(a^{\prime},b+1)$ for $a^{\prime}\geq a$ in a
constant number of moves.

  * •

If $zz^{\prime}$ is painted red, there is a blue path of length $a$ and a red
$S_{k}^{\prime}[b+1]$ (with edge $e_{b+1}$ being the edge $z^{\prime}z$) where
the last $(k+1)^{3}-bk-1\geq(k+1)^{3}-(b+1)k$ vertices of the blue $P_{a}$ are
between the two endpoints of the edge $e_{b+1}=zz^{\prime}$. Thus, we reached
state $(a,b+1)$ in a constant number of moves.∎

######  Claim 5.3.

There exists $c_{k}>0$ such that the following holds. If we are in state
$(a,b)$ with $a\geq(k+1)^{3}-bk$ and $b\in\\{2k-1,3k-1,\ldots k^{2}-1\\}$, we
reach $(a+1,b)$ in 1 move or $(a^{\prime},b+1)$ for $a^{\prime}\geq a-k$ in at
most $c_{k}$ moves for some $a^{\prime}\geq a$.

###### Proof.

Since we are in state $(a,b)$ there exists a blue $P_{a}$ and a red
$S\in\mathcal{S}_{k}^{\prime}[b]$ where the last $(k+1)^{3}-bk$ vertices of
the blue path are between the two endpoints of the edge $e_{b}$. Let $u_{a}$
be the rightmost vertex incident to the red nested matching of size $k-1$ and
$u_{b}$ the leftmost vertex, after $u_{a}$, which is incident to a vertex of
$S$.

Builder plays all edges of a clique of size $r((k+1)^{3}+k,2(k+1)^{2})$
between $u_{a}$ and $u_{b}$. Then either Builder created a red
$K_{2(k+1)^{2}}$ or a blue path of length $(k+1)^{3}+k$. In the first case,
Builder created a red $S_{k}^{\prime}$ and therefore wins in a total of at
most $a+c_{k}$ moves for some constant $c_{k}>0$.

Now assume Builder created a blue path of length $(k+1)^{3}+k$.

Denote $c_{1}^{\prime},c_{2}^{\prime},\ldots,c_{k}^{\prime}$ the $k$ first
vertices of this blue path and $c_{1},c_{2},\ldots,c_{k}$ the last $k$
vertices of the blue $P_{a}$. Builder now plays the edges
$c_{1}c_{1}^{\prime},c_{2}c_{2}^{\prime},\ldots,c_{k}c_{k}^{\prime}$.

  * •

If one of those edges is painted blue, we obtain a blue path of length
$a^{\prime}$ where $a^{\prime}\geq a$ such that the last $(k+1)^{3}$ vertices
of this blue path are between $u_{a}$ and $u_{b}$. We have reached state
$(a^{\prime},b+1)$ in at most $a+c_{k}$ moves for some constant $c_{k}>0$.

  * •

If all of those edges are painted red, we obtain a copy of some
$S_{k}^{\prime}[b+1]$ and a blue $P_{a}^{\prime}$ for $a^{\prime}=a-k$ such
that the last $(k+1)^{3}-bk-k=(k+1)^{3}-(b+1)k$ vertices of the
$P_{a}^{\prime}$ are before the newly created nested matching of size $k$ and
after $u_{a}$. We have reached state $(a^{\prime},b+1)$ in at most $a+c_{k}$
moves for some constant $c_{k}>0$.∎

The proof of Theorem 1.5 follows by combining Claims 5.1, 5.2 and 5.3.

## References

  * [1] G. Adamski and M. Bednarska-Bzdega.  Online size Ramsey numbers: Odd cycles vs connected graphs.  arXiv preprint arXiv:2111.14147, 2021.
  * [2] J. Balogh, F. C. Clemen, E. Heath, and M. Lavrov.  A strengthening of the Erdős–Szekeres theorem.  European J. Combin., 101:Paper No. 103456, 12, 2022.
  * [3] J. Beck.  Achievement games and the probabilistic method.  In Combinatorics, Paul Erdős is eighty, Vol. 1, Bolyai Soc. Math. Stud., pages 51–78. János Bolyai Math. Soc., Budapest, 1993\.
  * [4] D. Conlon.  On-line Ramsey numbers.  SIAM J. Discret. Math., 23:1954–1963, 2009.
  * [5] D. Conlon, J. Fox, C. Lee, and B. Sudakov.  Ordered Ramsey numbers.  J. Combin. Theory Ser. B, 122:353–383, 2017.
  * [6] D. Conlon, J. Fox, and B. Sudakov.  Recent developments in graph Ramsey theory.  Surveys in Combinatorics, 424(2015):49–118, 2015.
  * [7] J. Cyman, T. Dzido, J. Lapinskas, and A. Lo.  On-line Ramsey numbers of paths and cycles.  Electron. J. Comb., 22:P1.15, 2015.
  * [8] P. Erdős and Gy. Szekeres.  A combinatorial problem in geometry.  Compos. Math., 2:463–470, 1935.
  * [9] J. Geneson, A. Holmes, X. Liu, D. Neidinger, Y. Pehova, and I. Wass.  Ramsey numbers of ordered graphs under graph operations.  arXiv preprint arXiv:1902.00259, 2019.
  * [10] J. A. Grytczuk, H. A. Kierstead, and P. Prałat.  On-line Ramsey numbers for paths and stars.  Discrete Math. Theor. Comput. Sci., 10(3):63–74, 2008.
  * [11] A. Kurek and A. Ruciński.  Two variants of the size Ramsey number.  Discuss. Math. Graph Theory, 25(1-2):141–149, 2005.
  * [12] D. Neidinger and D. B. West.  Ramsey numbers of interval 2-chromatic ordered graphs.  Graphs Combin., 35(5):1065–1076, 2019.
  * [13] J. Pach and G. Tardos.  Forbidden paths and cycles in ordered graphs and matrices.  Israel J. Math., 155:359–380, 2006.
  * [14] X. Pérez-Giménez, P. Prałat, and D. B. West.  On-line size Ramsey number for monotone $k$-uniform ordered paths with uniform looseness.  European J. Combin., 92:Paper No. 103242, 14, 2021.
  * [15] J. M. Steele.  Variations on the monotone subsequence theme of Erdős and Szekeres.  In Discrete probability and algorithms (Minneapolis, MN, 1993), volume 72 of IMA Vol. Math. Appl., pages 111–131. Springer, New York, 1995.