# Ramsey numbers of sparse digraphs

Jacob Fox Department of Mathematics, Stanford University, Stanford, CA 94305,
USA. Email<EMAIL_ADDRESS>Research supported by a Packard Fellowship
and by NSF award DMS-185563. Xiaoyu He Department of Mathematics, Stanford
University, Stanford, CA 94305, USA. Email<EMAIL_ADDRESS>Research
supported by NSF GRFP Grant DGE-1656518. Yuval Wigderson Department of
Mathematics, Stanford University, Stanford, CA 94305, USA. Email:
<EMAIL_ADDRESS>Research supported by NSF GRFP Grant DGE-1656518.

###### Abstract

Burr and Erdős in 1975 conjectured, and Chvátal, Rödl, Szemerédi and Trotter
later proved, that the Ramsey number of any bounded degree graph is linear in
the number of vertices. In this paper, we disprove the natural directed
analogue of the Burr–Erdős conjecture, answering a question of Bucić, Letzter,
and Sudakov. If $H$ is an acyclic digraph, the _oriented Ramsey number_ of
$H$, denoted $\overrightarrow{r_{1}}(H)$, is the least $N$ such that every
tournament on $N$ vertices contains a copy of $H$. We show that for any
$\Delta\geq 2$ and any sufficiently large $n$, there exists an acyclic digraph
$H$ with $n$ vertices and maximum degree $\Delta$ such that

$\overrightarrow{r_{1}}(H)\geq n^{\Omega(\Delta^{2/3}/\log^{5/3}\Delta)}.$

This proves that $\overrightarrow{r_{1}}(H)$ is not always linear in the
number of vertices for bounded-degree $H$. On the other hand, we show that
$\overrightarrow{r_{1}}(H)$ is nearly linear in the number of vertices for
typical bounded-degree acyclic digraphs $H$, and obtain linear or nearly
linear bounds for several natural families of bounded-degree acyclic digraphs.

For multiple colors, we prove a quasi-polynomial upper bound
$\overrightarrow{r_{k}}(H)=2^{(\log n)^{O_{k}(1)}}$ for all bounded-degree
acyclic digraphs $H$ on $n$ vertices, where $\overrightarrow{r_{k}}(H)$ is the
least $N$ such that every $k$-edge-colored tournament on $N$ vertices contains
a monochromatic copy of $H$. For $k\geq 2$ and $n\geq 4$, we exhibit an
acyclic digraph $H$ with $n$ vertices and maximum degree $3$ such that
$\overrightarrow{r_{k}}(H)\geq n^{\Omega(\log n/\log\log n)}$, showing that
these Ramsey numbers can grow faster than any polynomial in the number of
vertices.

##  1 Introduction

The $k$-color Ramsey number of a (simple undirected) graph $H$, denoted
$r_{k}(H)$, is the minimum $N$ such that every $k$-edge-coloring of the
complete graph $K_{N}$ contains a monochromatic copy of $H$. Broadly speaking,
the main question in graph Ramsey theory is to understand how $r_{k}(H)$
depends on $H$ and $k$. The most well-studied case is that of two colors,
$k=2$. For $H$ on $n$ vertices, it is known [10, 36] that $r_{2}(H)$ grows
exponentially in $n$ if and only if $H$ has $\Omega(n^{2})$ edges.

However, it has long been observed that the Ramsey number of a sparse graph
$H$ is much smaller than exponential in $|V(H)|$. In their foundational paper
on the topic, Burr and Erdős [6] conjectured that this phenomenon is quite
general and that any sparse graph has linear Ramsey number. Here, the
appropriate notion of sparsity is _degeneracy:_ $H$ is said to be
$d$-degenerate if every subgraph of $H$ has a vertex of degree at most $d$,
and the degeneracy of $H$ is the minimum $d$ such that $H$ is $d$-degenerate.
Burr and Erdős conjectured that $r_{k}(H)=O_{k,d}(n)$ for any $n$-vertex graph
$H$ with degeneracy $d$. Here and throughout we use the standard asymptotic
notation where the implicit constant is allowed to depend only on the
subscripts of $O(\cdot)$. Major progress towards this conjecture was made by
Chvátal, Rödl, Szemerédi, and Trotter [8], who proved the Burr–Erdős
conjecture under the stronger assumption that $H$ has bounded degree (rather
than bounded degeneracy), that is, that $r_{k}(H)=O_{k,\Delta}(n)$ for any
$n$-vertex graph $H$ with maximum degree $\Delta$. Finally, building on many
prior developments (e.g. [19, 28]), the full Burr–Erdős conjecture was proved
by Lee [30] in 2017.

There are many analogous questions and results for directed graphs (henceforth
_digraphs_). We assume all digraphs are simple and oriented, so they do not
contain self-loops, parallel edges or anti-parallel edges. For a digraph $H$,
define the $k$-color _oriented Ramsey number_ $\overrightarrow{r_{k}}(H)$ to
be the minimum $N$ such that any $k$-edge-colored tournament on $N$ vertices
contains a monochromatic copy of $H$. Note that if $H$ contains a directed
cycle, then $H$ does not appear in any transitive tournament, so
$\overrightarrow{r_{k}}(H)$ only exists for acyclic $H$. Henceforth, we work
exclusively with acyclic digraphs $H$.

Unlike undirected Ramsey numbers, oriented Ramsey numbers are interesting even
in the case of one color, $k=1$, where $\overrightarrow{r_{1}}(H)$ is simply
the minimum $N$ such that any tournament on $N$ vertices contains a copy of
$H$. Let $\textnormal{TT}_{n}$ denote the transitive tournament on $n$
vertices. The study of oriented Ramsey numbers was initiated by Stearns [35]
in 1959 and Erdős and Moser [18] in 1964, who showed the upper and lower
bounds, respectively, in

$2^{n/2-1}\leq\overrightarrow{r_{1}}(\textnormal{TT}_{n})\leq 2^{n-1}.$ (1.1)

The exponential constants in these bounds have not been improved, similar to
the classical case of the diagonal undirected Ramsey number $r_{2}(K_{n})$
[10, 33, 34]. This may not be surprising, given that
$\overrightarrow{r_{1}}(\textnormal{TT}_{n})\leq r_{2}(K_{n})$. Thus,
improving the lower bound in (1.1) is at least as difficult as improving the
lower bound on $r_{2}(K_{n})$.

Somewhat more is known about the oriented Ramsey number
$\overrightarrow{r_{k}}(H)$ when $H$ is sparse. When $H=P_{n}$ is the directed
path on $n$ vertices, Chvátal [7] and Gyárfás and Lehel [22] determined that
$\overrightarrow{r_{k}}(P_{n})=(n-1)^{k}+1$ using the Gallai–Hasse–Roy–Vitaver
theorem [20, 24, 32, 38]. In the case of one color, it was more generally
conjectured by Sumner in 1971 that for any oriented tree $T$ on $n\geq 2$
vertices, $\overrightarrow{r_{1}}(T)\leq 2n-2$. Sumner’s conjecture has
received a considerable amount of attention over the years (see e.g. [15, 16,
23, 25, 26, 29, 37]); it was proven for $n$ sufficiently large by Kühn,
Mycroft, and Osthus [29], and Dross and Havet [15] showed that
$\overrightarrow{r_{1}}(T)\leq\frac{21}{8}n-\frac{47}{16}$ for all $n\geq 2$.
In more colors, it was shown by Bucić, Letzter, and Sudakov [4] that
$\overrightarrow{r_{k}}(T)=O_{k}(|V(T)|^{k})$ for any oriented tree $T$ and
all $k\geq 1$. In the same paper, they asked a natural directed analogue of
the classical Burr–Erdős problem.

######  Problem 1.1 ([4]).

Is it true that $\overrightarrow{r_{1}}(H)=O_{\Delta}(n)$ for every acyclic
digraph $H$ with $n$ vertices and maximum degree $\Delta$?

Here we write $N^{+}(v)$ for the out-neighborhood and $N^{-}(v)$ for the in-
neighborhood of a vertex $v\in V(H)$, and say that a digraph $H$ has maximum
degree $\Delta$ if $\max_{v\in V(H)}(|N^{+}(v)|+|N^{-}(v)|)=\Delta$.

Yuster [40] recently initiated the study of the special case of Problem 1.1
when $H=P_{n}^{\ell}$ is the $\ell$-th power of a directed path $P_{n}$, which
is the digraph on vertex set $[n]$ whose edges are the ordered pairs $(i,j)$
satisfying $1\leq j-i\leq\ell$. This case was recently settled by Draganić et
al. [14], who showed that $\overrightarrow{r_{1}}(P_{n}^{\ell})=O_{\ell}(n)$.
Letting the _bandwidth_ of an acyclic digraph $H$ on $n$ vertices be the
minimum $\ell$ such that $P_{n}^{\ell}$ contains a copy of $H$, this
aforementioned result implies that $\overrightarrow{r_{1}}(H)=O_{\ell}(n)$ if
$H$ has $n$ vertices and bandwidth $\ell$.

In this paper, we answer Problem 1.1 in the negative, and show that in fact
$\overrightarrow{r_{1}}(H)$ can grow faster than any fixed power of $n$, as
long as the maximum degree is a sufficiently large constant.

######  Theorem 1.2.

For any $\Delta\geq 2$ and $n$ sufficiently large in terms of $\Delta$, there
exists an acyclic digraph $H$ on $n$ vertices and maximum degree at most
$\Delta$ for which

$\overrightarrow{r_{1}}(H)\geq n^{\Omega(\Delta^{2/3}/\log^{5/3}\Delta)}.$

The power $\Delta^{2/3}$ seems to be best possible with our method, but the
power of $\log\Delta$ can be improved. Although the answer to Problem 1.1 is
negative, we prove an almost linear upper bound on $\overrightarrow{r_{1}}(H)$
for almost all $H$, in the following sense. Define $\overrightarrow{G}(n,d)$
to be the orientation of the random regular graph $G(n,d)$ on vertex set $[n]$
with all edges pointing to the right.

######  Theorem 1.3.

If $d\geq 2$ is fixed and $H=\overrightarrow{G}(n,d)$, then w.h.p.111As usual,
we say that an event $\mathcal{E}$ happens _with high probability (w.h.p.)_ if
$\Pr(\mathcal{E})\to 1$ as $n\to\infty$. (as $n\rightarrow\infty$)

$\overrightarrow{r_{1}}(H)\leq n(\log n)^{4\log d}.$

It is not difficult to extend Theorem 1.3 to show
$\overrightarrow{r_{1}}(H)=n(\log n)^{O_{\Delta}(1)}$ w.h.p. if $H$ is the
forward acyclic orientation of a uniformly random graph with any fixed degree
sequence $\Delta=d_{1}\geq d_{2}\geq\cdots\geq d_{n}$, and therefore also for
the forward acyclic orientation of a uniformly random bounded-degree graph. We
also prove a similar bound $\overrightarrow{r_{1}}(H)\leq n(\log
n)^{O_{d}(1)}$ when $H=\overrightarrow{G}(n,p)$ is the forward acyclic
orientation of an Erdős–Rényi random graph of constant average degree $d=pn$.

Although we are able to show that $\overrightarrow{r_{1}}(H)$ is w.h.p. almost
linear for a random bounded-degree acyclic digraph, we have not determined the
worst-case behavior of this Ramsey number. For general acyclic digraphs $H$ on
$n$ vertices with maximum degree $\Delta$, the best upper bound we are able to
prove is $\overrightarrow{r_{1}}(H)\leq n^{O_{\Delta}(\log n)}$ (see Theorem
1.7 below). Nonetheless, we are able to prove stronger (and in some cases
linear) upper bounds on $\overrightarrow{r_{1}}(H)$ in case $H$ lies in
certain natural families. We now give two examples of such families.

Let the _height_ of $H$ be the number of vertices on the longest directed path
in $H$. Equivalently, the height can be seen as a directed analogue of the
chromatic number: $H$ has height at most $h$ if and only if $V(H)$ can be
partitioned into independent sets $S_{1},\dotsc,S_{h}$ such that every edge
between $S_{i}$ and $S_{j}$ is oriented from $S_{i}$ to $S_{j}$, for every
$i<j$. For acyclic digraphs of bounded height and bounded degree, we are able
to prove the following linear bound on $\overrightarrow{r_{1}}(H)$.

######  Theorem 1.4.

If $H$ is an acyclic digraph on $n$ vertices with maximum degree $\Delta$ and
height $h$, then

$\overrightarrow{r_{1}}(H)\leq(\Delta h)^{10\Delta\log h}n.$

In particular, $\overrightarrow{r_{1}}(H)=O_{h,\Delta}(n)$.

Note that this theorem also implies the aforementioned $n^{O_{\Delta}(\log
n)}$ upper bound on $\overrightarrow{r_{1}}(H)$ for any bounded-degree acyclic
digraph $H$, since the height of an acyclic digraph is at most its vertex
count.

Next, we say that an acyclic digraph $H$ of height $h$ is _graded_ if its
vertex set can be partitioned into $h$ independent sets $S_{1},\dotsc,S_{h}$
such that every edge in $H$ is directed from some $S_{i}$ to $S_{i+1}$.
Equivalently, $H$ is graded if for every pair of vertices $(u,v)$, all
directed paths from $u$ to $v$ have the same length (the equivalence of the
definitions follows e.g. from [31, Proposition 4.4]). A natural example of a
graded digraph is a grid (in any dimension) with all edges oriented towards
the first orthant. In general, a graded digraph can be obtained from any
graded lattice (in the sense of partially ordered sets) $L$ by orienting every
edge $x<y$ of the Hasse diagram of $L$ from $x$ to $y$. For graded digraphs of
bounded degree, we are able to prove a polynomial bound on
$\overrightarrow{r_{1}}(H)$.

######  Theorem 1.5.

If $H$ is a graded digraph on $n$ vertices with maximum degree $\Delta$ and
height $h$, then

$\overrightarrow{r_{1}}(H)\leq h^{10\Delta\log\Delta}n.$

In particular, since $h\leq n$, we have that $\overrightarrow{r_{1}}(H)\leq
n^{O(\Delta\log\Delta)}$.

Our methods are motivated by those used by Conlox, Fox, Lee, and Sudakov [11]
to prove bounds on ordered Ramsey numbers, and the two problems are especially
closely related when the number of colors is at least $2$. Using this
connection, we are able to give a super-polynomial lower bound for
$\overrightarrow{r_{k}}(H)$ when $k\geq 2$.

######  Theorem 1.6.

For any $n\geq 4$, there exists an acyclic digraph $H$ on $n$ vertices with
maximum degree $3$ for which

$\overrightarrow{r_{k}}(H)\geq n^{\log n/20\log\log n}$

for all $k\geq 2$.

Thus, for acyclic digraphs of bounded degree, $\overrightarrow{r_{k}}(H)$ can
grow super-polynomially if $k\geq 2$. In the other direction, for any number
of colors we have the following quasi-polynomial upper bound.

######  Theorem 1.7.

If $k\geq 1$ and $H$ is any acyclic digraph with $n$ vertices and maximum
degree $\Delta$, then

$\overrightarrow{r_{k}}(H)\leq 2^{O_{k,\Delta}\left((\log
n)^{2^{2k-1}}\right)}.$

For one color, there is still a gap between the polynomial lower bound and the
super-polynomial upper bound.

We remark that there is another well-studied analogue of ordinary Ramsey
numbers in the directed setting, namely the _directed Ramsey number_
$\overleftrightarrow{r_{k}}(H)$, introduced by Bermond [2]. This is defined as
the minimum $N$ such that a monochromatic copy of $H$ exists in every
$k$-coloring of the edges of $\overleftrightarrow{K_{N}}$, the digraph with
edges in both directions between all pairs of vertices. There are similarities
and differences between the two theories (see e.g. [4]), and several of our
results on oriented Ramsey numbers can be extended to the setting of directed
Ramsey numbers. We expand on these connections in our concluding remarks,
Section 6.

To conclude this introduction, we remark on an interesting phenomenon brought
to light by our results. An important “meta-question” driving many advances in
Ramsey theory asks which graph parameters roughly determine a Ramsey number.
In the Ramsey theory of undirected graphs, this question has been more or less
resolved, at least in a qualitative sense. Namely, for an undirected graph
$H$, the degeneracy and the number of vertices are the main parameters that
determine the growth of $r_{2}(H)$ (we focus on the two-color case to be
concrete). This is easiest to see in the lower bounds: if $H$ has $n$
vertices, then certainly $r_{2}(H)\geq n$. Additionally, if $H$ has degeneracy
$d$, then it is a simple exercise to show that a random $2$-edge-coloring on
$2^{d/2}$ vertices does not contain a monochromatic copy of $H$ w.h.p.,
implying that $r_{2}(H)\geq 2^{d/2}$. Putting these two facts together, we
find that

$\log r_{2}(H)=\Omega(d+\log n).$

Conlon, Fox, and Sudakov [12, Conjecture 2.16] conjectured that this bound is
tight up to the implicit constant, namely that

$\log r_{2}(H)=\Theta(d+\log n)$

for any graph $H$ with $n$ vertices and degeneracy $d$. Moreover, this
conjecture is known to be true up to a multiplicative factor of $\log^{2}d$
[19, Theorem 3.1]. Because of these results, one can say that the degeneracy
and the vertex count of $H$ roughly determine its Ramsey number.

For acyclic digraphs, we do not know what parameters determine the growth
order of $\overrightarrow{r_{1}}(H)$ (indeed, we don’t even know if
$\overrightarrow{r_{1}}(H)$ is polynomial or super-polynomial in $n$ when $H$
has bounded degree). Nonetheless, our results indicate that one parameter,
which we call “multiscale complexity,” is relevant. Namely, suppose we order
the vertices of $H$ as $v_{1},\dotsc,v_{n}$ so that every edge is oriented to
the right, that is $v_{i}\to v_{j}$ is an edge only if $i<j$ (such an ordering
is often called a _topological sorting_ of $H$). Under this ordering we may
assign every edge $v_{i}\to v_{j}$ a _length_ $j-i$. Here, if $u,v\in V(H)$,
we write $u\rightarrow v$ to signify that there is a directed edge from $u$ to
$v$, and similarly $u\leftarrow v$ for an edge in the other direction.

In graphs of bounded bandwidth, every edge is short and has length $O(1)$. At
the other extreme, if $H$ has bounded height, then most edges of $H$ are long
and have length $\Omega(n)$. The same is true in the random model
$\overrightarrow{G}(n,d)$, where most edges have length $\Omega(n)$. Some
other acyclic digraphs have intermediate edge-length statistics, such as the
_directed grid_ whose vertex set is $[\sqrt{n}]^{2}$ and all edges are
oriented towards the lexicographically larger ordered pair. For every acyclic
ordering of such a grid, there are many edges in most dyadic length scales
between $1$ and $\Omega(\sqrt{n})$.

Loosely, let us say that $H$ has _high multiscale complexity_ if, for most
dyadic intervals $I_{t}=[2^{t},2^{t+1})$ with $0\leq t\leq\log n$, there are
many edges in $H$ whose length is in $I_{t}$. Conversely, if most edge lengths
of $H$ are concentrated in a small number of dyadic intervals, then we loosely
say that $H$ has _low multiscale complexity_. At a high level, all of our
upper bound results prove upper bounds on $\overrightarrow{r_{1}}(H)$ in terms
of $n,\Delta$, and the multiscale complexity of $H$; if the multiscale
complexity is low, then these bounds are stronger, and one can prove linear,
nearly linear, or polynomial bounds on $\overrightarrow{r_{1}}(H)$ (depending
on the precise context). Conversely, our lower bound construction for Theorem
1.2 is a family of digraphs which we call _interval meshes_. We delay the
precise definition to Section 2, but interval meshes are in some sense
designed to maximize multiscale complexity among all graphs of maximum degree
at most $\Delta$.

We stress that we have not fully solved the problem of which natural
parameters determine the growth order of $\overrightarrow{r_{1}}(H)$, and we
think this problem deserves further research. Nonetheless, our results do make
it clear that some notion of multiscale complexity is one of these parameters,
and we believe this notion is fundamental. As such, we state and prove many of
our technical upper bounds in greater generality than is needed to deduce our
main theorems, in order to demonstrate how notions of multiscale complexity
arise naturally from our techniques.

The rest of the paper is laid out as follows. Section 2 carries out the
construction of interval meshes to prove the lower bound Theorem 1.2. Section
3 uses the greedy embedding technique to prove the main technical lemmas
needed for the upper bounds Theorems 1.3, 1.4, and 1.5. Section 4 completes
the proofs of these results, as well as a more general upper bound in terms of
“multiscale complexity.” Using the connection to ordered Ramsey numbers,
Section 5 proves Theorems 1.6 and 1.7. Finally, in our concluding remarks,
Section 6, we collect a few of the tantalizing open problems that remain in
this area.

#### Notation and terminology.

By an _embedding_ $H\hookrightarrow T$, we mean an injective function $V(H)\to
V(T)$ such that edges of $H$ are mapped to edges of $T$, with edge
orientations preserved. We say that a digraph $T$ is $H$-free if there is no
embedding $H\hookrightarrow T$. All logarithms are to base $2$. For the sake
of clarity of presentation, we sometimes omit floor and ceiling signs when
they are not crucial.

##  2 Lower bounds

In this section, we prove the lower bound Theorem 1.2, which states that for
any $\Delta\geq 1$ there exists a family of acyclic digraphs
$\\{H_{n}\\}_{n\geq 1}$ with maximum degree $\Delta$ for which $|V(H_{n})|=n$
and $\overrightarrow{r_{1}}(H_{n})\geq
n^{\Omega(\Delta^{2/3}/\log^{5/3}\Delta)}$. The lower bound consists of three
ingredients: constructing a bounded degree acyclic digraph $H$ that is hard to
embed, constructing a Ramsey tournament $T$ that is hard to embed $H$ into,
and proving that there is no embedding $H\hookrightarrow T$.

The next three subsections separately provide these three ingredients. Section
2.1 defines a class of digraphs $H$ with edges “at all scales,” which we call
_interval meshes,_ and proves the existence of bounded-degree $H$ with this
property. Section 2.2 defines the Ramsey tournament $T$ as a lexicographic
power of a tournament $R$ with no large transitive subtournament, and shows
that embeddings $H\hookrightarrow T$ correspond to certain highly constrained
walks on $R$ which we call _$(R,f,s)$ -walks._ Section 2.3 completes the proof
by showing that long $(R,f,s)$-walks do not exist, and therefore large
interval meshes $H$ cannot be embedded into small powers $T=R^{m}$.

###  2.1 Interval meshes

Our proof of Theorem 1.2 is motivated by the lower bound construction for
ordered Ramsey numbers proved by Conlon, Fox, Lee, and Sudakov [11]. They
prove a lower bound on the ordered Ramsey number of a random matching on
$[n]$; see Theorem 5.1 and the surrounding discussion for details. The main
property they need of the random matching is that most pairs of long intervals
have an edge between them. We need the following stronger property of the same
form for our acyclic digraph $H$.

######  Definition 2.1.

If $f:\mathbb{N}\rightarrow\mathbb{R}_{>0}$ is a nondecreasing function, we
define an _$f$ -interval mesh _to be an acyclic digraph $H$ whose vertex set
is an interval $I\subseteq\mathbb{N}$ such that any edge $(i,j)\in E(H)$ has
$i<j$ and for all pairs of intervals $(a_{1},b_{1}],(a_{2},b_{2}]\subseteq I$
with $b_{1}\leq a_{2}$ and

$a_{2}-b_{1}\leq f(\min(b_{1}-a_{1},b_{2}-a_{2})),$ (2.1)

there exists an edge in $H$ between $(a_{1},b_{1}]$ and $(a_{2},b_{2}]$. When
the function $f$ is clear from context, we simply call $H$ an _interval mesh._

The notion of an interval mesh is one way of formalizing the notion from the
introduction of “high multiscale complexity”, since interval meshes have many
edges in every length scale. We construct interval meshes of bounded degree
using a greedy algorithm.

######  Lemma 2.2.

For any nondecreasing function $f:\mathbb{N}\rightarrow\mathbb{R}_{>0}$ with
$S=\sum_{m\geq 0}f(2^{m+2})\cdot 2^{-2m}<\infty$, there exists an $f$-interval
mesh $H$ on vertex set $\mathbb{N}$ with maximum degree at most $2S+17$.

###### Proof.

Starting from an empty digraph on $\mathbb{N}$, we construct $H$ by using a
greedy algorithm to add edges. All edges introduced point to the right, so the
resulting digraph must be acyclic. Define $I_{m,j}$ to be the dyadic interval
$(j\cdot 2^{m},(j+1)\cdot 2^{m}]$ with length $2^{m}$.

Let $m\geq 0$ range through the nonnegative integers. On subroutine $m$, we
iterate through all pairs $(i,j)\in\mathbb{N}_{\geq 0}^{2}$ satisfying

$1\leq j-i\leq f(2^{m+2})\cdot 2^{-m}+4$ (2.2)

and add an edge between the (currently) lowest degree vertex of $I_{m,i}$ and
the (currently) lowest degree vertex of $I_{m,j}$, if an edge does not exist
between $I_{m,i}$ and $I_{m,j}$ already. Writing $d(U)$ for the sum of the
degrees of the vertices in a set $U$, we see that for any given $i$,
subroutine $m$ increases $d(I_{m,i})$ by a total of at most

$2[f(2^{m+2})\cdot 2^{-m}+4]=2^{-m+1}\cdot f(2^{m+2})+8.$

Let $H$ be the digraph produced from this infinite process. Explicitly, $H$ is
the edge union of all the graphs $H^{(m)}$, where $H^{(m)}$ is the graph
produced after subroutine $m$. It has the property that every pair of dyadic
intervals $I_{m,i}$, $I_{m,j}$ satisfying (2.2) has an edge between them.

We first check that $H$ has maximum degree at most $2S+17$. Since $I_{m,i}$ is
a union of $2^{m-k}$ dyadic intervals of length $2^{k}$, we have that after
subroutine $m$,

$d(I_{m,i})\leq\sum_{k=0}^{m}2^{m-k}(2^{-k+1}\cdot f(2^{k+2})+8)\leq
2^{m+1}\cdot S+2^{m+1}\cdot 8=2^{m}(2S+16).$

In particular, the average degree in $I_{m,i}$ is less than $2S+17$ at the end
of subroutine $m$. However, subroutine $m$ only adds edges incident to
vertices of $I_{m,i}$ which have at most average degree, so no new vertex of
degree at least $2S+18$ can appear on subroutine $m$. Thus, no vertex of
degree at least $2S+18$ ever appears, as desired.

Next, we check that $H$ is an $f$-interval mesh. Suppose two intervals
$(a_{1},b_{1}]$, $(a_{2},b_{2}]$ with $b_{1}\leq a_{2}$ satisfy (2.1) and let
$m$ be the largest positive integer such that $(a_{1},b_{1}]$ and
$(a_{2},b_{2}]$ both contain dyadic intervals of length $2^{m}$. Note that in
any interval $(a,b]$ of integers, a longest dyadic subinterval $I_{\ell,i}$
has length $2^{\ell}\in[\frac{b-a}{4},b-a]$, so in particular
$2^{m+2}\geq\min(b_{1}-a_{1},b_{2}-a_{2}).$ Next, pick $i$ maximal and $j$
minimal such that $I_{m,i}\subseteq(a_{1},b_{1}]$ and
$I_{m,j}\subseteq(a_{2},b_{2}]$.

Using (2.1), we find

$j-i\leq 4+\frac{a_{2}-b_{1}}{2^{m}}\leq
4+\frac{f(\min(b_{1}-a_{1},b_{2}-a_{2}))}{2^{m}}\leq
4+\frac{f(2^{m+2})}{2^{m}},$

and so there is an edge in $H$ between $I_{m,i}$ and $I_{m,j}$, and therefore
between $(a_{1},b_{1}]$ and $(a_{2},b_{2}]$ as well. ∎

The acyclic digraphs $H_{n}$ we use are induced subgraphs on intervals of the
infinite interval mesh constructed in Lemma 2.2, for an appropriate choice of
$f$.

###  2.2 Walks in tournaments

Next, we construct the large tournament $T$ which is difficult to embed $H$
into. Again, the construction is motivated by the lower bound argument of
Conlon, Fox, Lee, and Sudakov [11] for ordered Ramsey numbers, although its
analysis requires new techniques.

Recall that the _lexicographic product_ $G\cdot H$ of two digraphs $G$ and $H$
is the digraph on vertex set $V(G)\times V(H)$ with an edge
$(g_{1},h_{1})\rightarrow(g_{2},h_{2})$ iff $g_{1}\rightarrow g_{2}$ in $G$ or
$g_{1}=g_{2}$ and $h_{1}\rightarrow h_{2}$ in $H$. Henceforth, write $G^{m}$
for the $m$-fold lexicographic product of $G$ with itself. Note that
lexicographic powers of tournaments are tournaments. By (1.1), there exists
for any $r\geq 3$ a tournament $R$ on $r$ vertices with no transitive
subtournament of size $2\log r+2$. We take $T=R^{m}$ and show that an interval
mesh $H$ is difficult to embed into $T$.

To this end, let $H$ be an interval mesh. We relate embeddings
$H\hookrightarrow R^{m}$ to certain constrained walks on the tournament $R$.

######  Definition 2.3.

For a tournament $R$, a nondecreasing function
$f:\mathbb{N}\rightarrow\mathbb{R}_{>0}$, and $s\geq 1$, define an
$(R,f,s)$_-walk_ to be a sequence of ordered pairs
$\\{(v_{i},a_{i})\\}_{i=1}^{\ell}$ $(\ell$ possibly infinite) where for each
$i$, $v_{i}\in V(R)$, $1\leq a_{i}\leq s$, $v_{i}\neq v_{i+1}$, and for any
pair $i<j$ for which $v_{i}\leftarrow v_{j}$ in $R$, we have

$a_{(i,j)}>f(\min(a_{i},a_{j})),$

where $a_{I}\coloneqq\sum_{k\in I}a_{k}$ if $I$ is an interval of integers and
the empty sum equals $0$. We define the _length_ of an $(R,f,s)$-walk to be
$a_{[1,\ell]}$.

Let $L_{R,f}(s)$ be the length of the longest $(R,f,s)$-walk if such a maximum
exists, and $+\infty$ otherwise. The next lemma reduces Theorem 1.2 to showing
asymptotic upper bounds on $L_{R,f}(s)$.

######  Lemma 2.4.

Suppose there exists $r\geq 1$, a nondecreasing
$f:\mathbb{N}\rightarrow\mathbb{R}_{>0}$, and a tournament $R$ on $r$ vertices
for which $\limsup_{s\rightarrow\infty}L_{R,f}(s)s^{-1}=\alpha$. If $H$ is an
$f$-interval mesh on $n$ vertices, then

$\overrightarrow{r_{1}}(H)\geq n^{\frac{\log r}{\log\alpha}-o(1)}.$

###### Proof.

For each $n\geq 1$, let $m=m(n)$ be the minimum positive integer for which
there exists an $f$-interval mesh $H$ with vertex set $[n]$ and an embedding
$\phi:H\hookrightarrow R^{m}$.

Let $\pi:R^{m}\rightarrow R$ be the projection onto the first coordinate.
Consider the sequence $\\{\pi\circ\phi(j)\\}_{j=1}^{n}$. Consecutive terms of
this sequence may repeat, so we block the sequence into consecutive runs of
identical vertices. Suppose there are $\ell$ total runs
$I_{1}\sqcup\cdots\sqcup I_{\ell}=[n]$ and run $I_{i}$ consists of $a_{i}$
repetitions of vertex $v_{i}\in V(R)$. We claim that
$\\{(v_{i},a_{i})\\}_{i=1}^{\ell}$ is an $(R,f,s)$-walk, where
$s\coloneqq\max(a_{i})$. It is easy to see that $1\leq a_{i}\leq s$ for all
$i$, and that $v_{i}\neq v_{i+1}$ since we already blocked consecutive
identical vertices together. It remains to check the key condition, that if
$i<j$ and $v_{i}\leftarrow v_{j}$ in $R$, we must have

$a_{(i,j)}>f(\min(a_{i},a_{j})).$

Suppose this is not true, so there exists some $i<j$ with $v_{i}\leftarrow
v_{j}$ and $a_{(i,j)}\leq f(\min(a_{i},a_{j}))$. By the definition of
$v_{i},v_{j}$, we have that $\pi(\phi(I_{i}))=\\{v_{i}\\}$,
$\pi(\phi(I_{j}))=\\{v_{j}\\}$. By the definition of the lexicographic power,
if $v_{i}\leftarrow v_{j}$ then $w_{i}\leftarrow w_{j}$ for all
$w_{i}\in\pi^{-1}(v_{i}),w_{j}\in\pi^{-1}(v_{j})$. Thus, all edges between
$\phi(I_{i})$ and $\phi(I_{j})$ are oriented from $\phi(I_{j})$ to
$\phi(I_{i})$. For $\phi$ to be a homomorphism, this means that $H$ has no
edge oriented from $I_{i}$ to $I_{j}$. On the other hand, $|I_{i}|=a_{i}$,
$|I_{j}|=a_{j}$, and the distance between the two intervals is $a_{(i,j)}\leq
f(\min(a_{i},a_{j}))$, so since $H$ is an $f$-interval mesh there is such an
edge. This is a contradiction, and we see that
$\\{(v_{i},a_{i})\\}_{i=1}^{\ell}$ is an $(R,f,s)$-walk of length $n$.

Fix any $\varepsilon>0$. We are given that
$L_{R,f}(s)\leq(\alpha+\varepsilon)s$ for sufficiently large $s$, so we get
$s\geq(\alpha+\varepsilon)^{-1}n$ using the fact that $n\leq L_{R,f}(s)$ since
we have found an $(R,f,s)$-walk of length $n$. Since $s=\max(a_{i})$, this
means that there is some subinterval $I_{i}\subseteq[n]$ of length at least
$(\alpha+\varepsilon)^{-1}n$ for which $\pi\circ\phi$ is constant on $I_{i}$,
i.e. the image $\phi(I_{i})\subseteq\\{v_{i}\\}\times R^{m-1}$ lies in a copy
of $R^{m-1}$. Putting this together, we have shown that for large enough $n$,
the existence of an embedding $\phi:H\hookrightarrow R^{m}$ implies the
existence of an embedding $\phi^{\prime}:H^{\prime}\hookrightarrow R^{m-1}$
for some $f$-interval mesh $H^{\prime}$ on $(\alpha+\varepsilon)^{-1}n$
vertices. In other words,

$m(n)\geq m((\alpha+\varepsilon)^{-1}n)+1$

for all $n$ sufficiently large. Applying this recursively, we obtain that
$m(n)\geq\frac{\log n}{\log(\alpha+\varepsilon)}-O_{\varepsilon}(1)$. By the
definition of $m(n)$, any $f$-interval mesh $H$ on $n$ vertices has no
embedding into $R^{m(n)-1}$, and so

$\overrightarrow{r_{1}}(H)>|V(R^{m(n)-1})|\geq r^{\frac{\log
n}{\log(\alpha+\varepsilon)}-O_{\varepsilon}(1)}=\Omega_{\varepsilon}\left(n^{\frac{\log
r}{\log(\alpha+\varepsilon)}}\right),$

which proves the lemma. ∎

To finish the proof of Theorem 1.2, it remains to bound the asymptotic growth
rate of $L_{R,f}(s)$, which we do in the next section.

###  2.3 Completing the proof

The next lemma is a simple observation that is helpful for analyzing the
structure of $(R,f,s)$-walks.

######  Lemma 2.5.

If $R$ is a tournament without a transitive $t$-subtournament, then any
sequence $v_{1},\ldots,v_{t}$ of $t$ vertices either contains a back-edge
$v_{i}\leftarrow v_{j}$ with $i<j$ or two consecutive elements
$v_{i}=v_{i+1}$.

###### Proof.

If the vertices are all distinct, then since $R$ has no transitive
$t$-subtournament there must exist a back-edge. Suppose $v_{i}=v_{j}$ and
$i<j$ but $j\neq i+1$. Then either $v_{i}\leftarrow v_{i+1}$ or
$v_{i+1}\leftarrow v_{j}$ is a back-edge. ∎

We now prove a recursive upper bound on $L_{R,f}(s)$. Given an implicit
parameter $t\geq 3$, tournament $R$, and nondecreasing function
$f:\mathbb{N}\rightarrow\mathbb{R}_{>0}$, we say that a positive integer $s$
is _short_ if $L_{R,f}(s)\leq 2st$ and $L_{R,f}(s^{\prime\prime})\leq
f(s^{\prime\prime})$ for all $s^{\prime\prime}\leq s$.

######  Lemma 2.6.

Suppose $s\geq 1$, $t\geq 3$, $R$ is a tournament without a transitive
$t$-subtournament, and $f:\mathbb{N}\rightarrow\mathbb{R}_{>0}$ is a
nondecreasing function satisfying $f(s)>6st^{2}$. If $s$ is short, then every
$s^{\prime}\in[2st,4st]$ is short.

###### Proof.

Suppose $s<s^{\prime}\leq 4st$, $\\{(v_{i},a_{i})\\}_{i=1}^{\ell}$ is an
$(R,f,s^{\prime})$-walk, and let $i_{1}<\dotsb<i_{u}$ be the sequence of all
indices where $a_{i_{j}}\geq s$.

Our first goal is to show that $u<t$. If not, by Lemma 2.5 there is either a
back-edge $v_{i_{x}}\leftarrow v_{i_{y}}$ with $x<y\leq t$ or some $x\leq t-1$
for which $v_{i_{x}}=v_{i_{x+1}}$. We show that neither of these situations is
possible.

In the first case, there is an edge $v_{i_{x}}\leftarrow v_{i_{y}}$ with
$x<y\leq t$. By the definition of an $(R,f,s^{\prime})$-walk,

$a_{(i_{x},i_{y})}>f(\min(a_{i_{x}},a_{i_{y}}))\geq f(s).$ (2.3)

On the other hand,

$a_{(i_{x},i_{y})}=\sum_{j\in(x,y)}a_{i_{j}}+\sum_{j\in[x,y)}a_{(i_{j},i_{j+1})}\leq
s^{\prime}t+t\cdot L_{R,f}(s)\leq 6st^{2},$

since for each $j=x,\ldots,y-1$, the subsequence
$\\{(v_{i},a_{i})\\}_{i=i_{j}+1}^{i_{j+1}-1}$ is an $(R,f,s)$-walk with length
at most $L_{R,f}(s)\leq 2st$. But $f(s)>6st^{2}$, so this contradicts (2.3)
and the back-edge $v_{i_{x}}\leftarrow v_{i_{y}}$ cannot exist.

Next, suppose for some $x\leq t-1$ that $v_{i_{x}}=v_{i_{x+1}}$. The
subsequence $\\{(v_{i},a_{i})\\}_{i=i_{x}+1}^{i_{x+1}-1}$ is an
$(R,f,s^{\prime\prime})$-walk where $s^{\prime\prime}$ is the maximum value of
$a_{i}$ in this subsequence. Pick some $z$ for which $a_{z}=s^{\prime\prime}$.
Either $v_{i_{x}}\leftarrow v_{z}$ or $v_{z}\leftarrow v_{i_{x+1}}$ is a back-
edge, and without loss of generality assume it is the former. Applying the
definition of the $(R,f,s^{\prime\prime})$-walk on the two indices $i_{x}$ and
$z$,

$a_{(i_{x},z)}>f(\min(a_{i_{x}},a_{z}))=f(s^{\prime\prime}).$

On the other hand, this sum is bounded above by $a_{(i_{x},i_{x+1})}$. We know
$a_{(i_{x},i_{x+1})}\leq L_{R,f}(s^{\prime\prime})\leq f(s^{\prime\prime})$
because $\\{(v_{i},a_{i})\\}_{i=i_{x}+1}^{i_{x+1}-1}$ is an
$(R,f,s^{\prime\prime})$-walk and $s\geq s^{\prime\prime}$ is short, so we
have another contradiction. Thus $u<t$.

We obtain

$a_{[1,\ell]}\leq\sum_{j=1}^{u}a_{i_{j}}+\sum_{j=0}^{u}a_{(i_{j},i_{j+1})}\leq
s^{\prime}t+t\cdot L_{R,f}(s)\leq s^{\prime}t+2st^{2},$ (2.4)

for all $s<s^{\prime}\leq 4st$ and any $(R,f,s^{\prime})$-walk
$\\{(v_{i},a_{i})\\}_{i=1}^{\ell}$. Here we let $i_{0}=0$ and $i_{u+1}=\ell+1$
for convenience.

Inequality (2.4) implies that $L_{R,f}(s^{\prime})\leq 2s^{\prime}t$ for all
$s^{\prime}\in[2st,4st]$. It also implies that $L_{R,f}(s^{\prime\prime})\leq
6st^{2}<f(s)\leq f(s^{\prime\prime})$ for all $s^{\prime\prime}\in(s,4st]$. We
have verified both conditions for $s^{\prime}$ to be short for every
$s^{\prime}\in[2st,4st]$, as desired. ∎

It remains to pick a function $f$ for which Lemma 2.6 bootstraps successfully.
Define

$f(s)\coloneqq\begin{cases}\frac{10s^{2}t^{3/2}\log t}{\log^{2}s}&s\geq 4\\\
40t^{3/2}\log t&s<4,\end{cases}$ (2.5)

where the values of $f(1),f(2),f(3)$ are chosen just to make $f$
nondecreasing. Recall that all logarithms are to base $2$.

######  Lemma 2.7.

If $t\geq 10^{6}$, $f:\mathbb{N}\rightarrow\mathbb{R}_{>0}$ is defined by
(2.5), and $R$ is a tournament without a transitive $t$-subtournament, then
$L_{R,f}(s)\leq 2st$ for all $s$ sufficiently large.

###### Proof.

We apply Lemma 2.6 inductively to show that $s$ is short for all $s$
sufficiently large. This implies the desired result.

For the base case, we claim that $s$ is short for all $s\leq s_{0}\coloneqq
40t^{1/2}\log t$. Indeed, suppose $s\leq s_{0}$ and
$\\{(v_{i},a_{i})\\}_{i=1}^{\ell}$ is an $(R,f,s)$-walk. By Lemma 2.5, if
$\ell\geq t$ then there is either a back-edge $v_{i}\leftarrow v_{j}$ with
$i<j\leq t$ or two consecutive elements $v_{i}=v_{i+1}$. The latter
contradicts the definition of an $(R,f,s)$-walk, so assume the former holds.
But $a_{(i,j)}<st\leq f(1)\leq f(\min(a_{i},a_{j}))$, so this contradicts the
definition of an $(R,f,s)$-walk again. We have shown that $\ell<t$, so
$L_{R,f}(s)<st\leq f(s)$ for all $s\leq s_{0}$. This proves $s$ is short for
every $s\leq s_{0}$.

Next, we check that $f(s)>6st^{2}$ for all $s\geq s_{0}$. Indeed, $f(s)/s$ is
increasing for $s\geq s_{0}$, and $\log s_{0}\leq\log t$ since $t\geq 10^{6}$.
We get

$f(s_{0})=\frac{10s_{0}^{2}t^{3/2}\log t}{\log^{2}s_{0}}>1000t^{5/2}\log
t>6s_{0}t^{2},$

proving that the conditions of Lemma 2.6 are satisfied. By induction, Lemma
2.6 then implies that $s$ is short for $s\in[(2t)^{k}s_{0},(4t)^{k}s_{0}]$ for
all $k\geq 0$. All sufficiently large integers lie in some such interval, so
$L_{R,f}(s)\leq 2st$ for all sufficiently large $s$, as desired. ∎

Putting everything together, we have a proof of the general lower bound.

###### Proof of Theorem 1.2..

We may assume that $\Delta$ is sufficiently large as we always have
$\overrightarrow{r_{1}}(H_{n})\geq n$, which proves the theorem for small
$\Delta$ by picking the implicit constant factor in the exponent
appropriately. Let $t=\Delta^{2/3}/(200\log^{2/3}\Delta)$; we may assume
$t\geq 10^{6}$. Define $f:\mathbb{N}\rightarrow\mathbb{R}_{>0}$ by (2.5). We
have

$S=\sum_{m\geq 0}f(2^{m+2})\cdot 2^{-2m}\leq f(1)\cdot\sum_{m\geq 1}m^{-2}\leq
80t^{3/2}\log t.$

Lemma 2.2 implies that there exists an $f$-interval mesh $H$ on $\mathbb{N}$
with maximum degree at most $2S+17\leq 200t^{3/2}\log t\leq\Delta$. For any
$n\geq 1$, let $H_{n}$ be the induced subgraph of $H$ on the interval $[n]$,
so that $H_{n}$ has $n$ vertices and is also an $f$-interval mesh of maximum
degree at most $\Delta$.

There exists a tournament $R$ on $r=2^{\Omega(t)}$ vertices with no transitive
$t$-subtournament. By Lemmas 2.4 and 2.7 applied with these choices of $R,f$
and $H_{n}$, we find that

$\overrightarrow{r_{1}}(H_{n})>n^{\frac{\log r}{\log(2t)}-o(1)}\geq
n^{\Omega(t/\log t)},$

which proves the theorem, by our choice of $t$. ∎

We remark that the polylogarithmic factor in
$\Delta=\Omega(t^{2/3}/\log^{2/3}\Delta)$ can be easily improved. Indeed, the
growth rate of $f(s)=\Theta(s^{2}/\log^{2}s)$ is chosen so that

$\sum_{m\geq 0}f(2^{m+2})\cdot 2^{-2m}<\infty,$

and we may take $f(s)=\Theta(s^{2}/\log^{1+\varepsilon}s)$ for any fixed
$\varepsilon>0$ instead, leading to a slightly smaller $\Delta$.

##  3 Greedy embedding

In this section we prove the main lemmas needed for all of the upper bounds in
this paper. We use the greedy embedding technique, motivated by similar
arguments for ordered graphs from [11].

Framework. Let $H$ be an acyclic digraph on $n$ vertices $v_{1},\ldots,v_{n}$.
We would like to find an embedding $\phi:H\hookrightarrow T$ into an ambient
tournament $T$. In addition we specify $n$ sets $U_{1},\ldots,U_{n}\subseteq
V(T)$ and aim to satisfy $\phi(v_{i})\in U_{i}$ for all $i$. Embedding then
proceeds in $n$ rounds, where round $t$ determines the image $\phi(v_{t})$.
After round $t$, we keep track of the shrinking sets
$U_{1}^{(t)},\ldots,U_{n}^{(t)}$ of “valid candidates” for each vertex, where
initially $U_{i}^{(0)}=U_{i}$ for all $i$. On round $t$, $\phi(v_{t})$ is a
carefully chosen vertex in $U_{t}^{(t-1)}$, and
$U_{t}^{(t)}\coloneqq\\{\phi(v_{t})\\}$. The other candidate sets are updated
as follows:

$U_{j}^{(t)}\coloneqq\begin{cases}[U_{j}^{(t-1)}\cap
N^{+}(v_{t})]\setminus\\{\phi(v_{t})\\}&\text{if }v_{t}\rightarrow v_{j},\\\
{}[U_{j}^{(t-1)}\cap N^{-}(v_{t})]\setminus\\{\phi(v_{t})\\}&\text{if
}v_{j}\rightarrow v_{t},\\\
U_{j}^{(t-1)}\setminus\\{\phi(v_{t})\\}&\text{else}.\end{cases}$

The process fails if there is an empty $U_{t}^{(t-1)}$, as there would be no
valid choice for $\phi(v_{t})$. Otherwise, it succeeds if $\phi(v_{t})$ is
chosen successfully for each $t\leq n$. Note that after round $t$,
$\\{\phi(v_{1}),\ldots,\phi(v_{t})\\}$ is an embedded copy of
$H[\\{v_{1},\ldots,v_{t}\\}]$ in $T$, and these vertices have been removed
from the other candidate sets, so the update rule guarantees that
$U_{j}^{(t)}=\\{\phi(v_{j})\\}$ remains a singleton when $t\geq j$. If the
greedy embedding process succeeds, it exhibits the existence of a copy of $H$
in $T$. See Figure 3.1 for a schematic illustration of the greedy embedding
process.

Target graph $H$$v_{1}$$v_{2}$$v_{3}$$v_{4}$Step
0$U_{1}^{(0)}$$U_{2}^{(0)}$$U_{3}^{(0)}$$U_{4}^{(0)}$Step
1$\phi(v_{1})$$U_{2}^{(1)}$$U_{3}^{(1)}$$U_{4}^{(1)}$Step
2$\phi(v_{1})$$\phi(v_{2})$$U_{3}^{(2)}$$U_{4}^{(2)}$Step
3$\phi(v_{1})$$\phi(v_{2})$$\phi(v_{3})$$U_{4}^{(3)}$Step
4$\phi(v_{1})$$\phi(v_{2})$$\phi(v_{3})$$\phi(v_{4})$ Figure 3.1: Illustration
of the greedy embedding process for an acyclic orientation of the four-cycle.
A directed arrow from a vertex to a set indicates that the vertex is complete
to the set. All edges point forward in this example, but we do not always make
this assumption.

For the upper bounds described in the introduction (Theorems 1.3, 1.4, and
1.5), we apply greedy embedding in two separate stages, which we call the
outer stage and the inner stage. Roughly speaking, in the outer stage, we run
the greedy embedding procedure many times to show that if $T$ is $H$-free,
then $T$ contains a large “approximate blowup of $H$.” In the inner stage, we
use greedy embedding one final time within this “approximate blowup” to
guarantee the existence of a copy of $H$ in $T$. In either case, we can
conclude that $T$ contains a copy of $H$—either it is found directly by the
greedy embedding strategy, or else the failure of the greedy embedding yields
the “approximate blowup” of $H$, in which a copy of $H$ can be found directly.

This section is split into three subsections. The first covers the basic
results that follow from the greedy embedding framework described above,
namely how a failure to greedily embed $H$ in a tournament $T$ implies that
$T$ contains a certain nice structure, namely a pair of large vertex sets such
that most edges between them have the same orientation. The tools built in
this first subsection are then used as basic building blocks and iterated in
the subsequent subsections. In the second subsection, we use them to build the
outer stage of the embedding. In the third subsection, we explain how to use
this outer stage construction of an “approximate blowup of $H$” to finally
embed $H$ itself.

In some of these greedy embedding arguments, we are concerned with
partitioning an acyclic digraph $H$ into a number of parts and embedding the
parts one at a time, so the following definition will be useful.

######  Definition 3.1.

If $H$ is an acyclic digraph, we say that a collection $\\{P_{i}\\}_{i=1}^{r}$
of vertex subsets of $H$ is a _directed partition_ of $H$ if $P_{1}\sqcup
P_{2}\sqcup\cdots\sqcup P_{r}=V(H)$, and any edge of $H$ between two distinct
parts $P_{i},P_{j}$ with $i<j$ is oriented from $P_{i}$ to $P_{j}$.

In particular, the height of $H$ is exactly the least $h$ for which there
exists a directed partition of $H$ into $h$ independent sets.

###  3.1 The basic greedy embedding building blocks

Recall that an undirected graph $G$ is said to be $d$_-degenerate_ if there
exists an ordering $v_{1},\ldots,v_{n}$ of the vertices of $G$ such that each
$|N(v_{i})\cap\\{v_{1},\ldots,v_{i-1}\\}|\leq d$, and such an ordering is
called a $d$_-degenerate ordering_ of $G$. A $d$-degenerate ordering is a
natural order for greedily embedding an undirected graph $G$, since each
candidate set $U_{j}^{(t)}$ in the greedy embedding strategy only shrinks in
size by more than one at most $d$ times. We say that a digraph $H$ is
$d$-degenerate if its underlying undirected graph is $d$-degenerate. Note that
if $H$ has maximum degree $\Delta$ then it is $\Delta$-degenerate, but
$d$-degenerate digraphs can have arbitrarily large maximum degree.

Define a $\delta$-_dense pair_ $(W_{1},W_{2})$ in a tournament $T$ to be a
pair of vertex subsets such that at least $\delta|W_{1}||W_{2}|$ of the edges
between $W_{1}$ and $W_{2}$ point from $W_{1}$ to $W_{2}$. The _size_ of the
pair is defined to be $\min(|W_{1}|,|W_{2}|)$. We do not require $W_{1}$ and
$W_{2}$ to be disjoint, although the assumption of $\delta$-density implies
that $W_{1}\cap W_{2}$ cannot be too large if $\delta$ is close to $1$.

The first lemma in this subsection uses greedy embedding to show that if $T$
doesn’t contain a copy of a given $d$-degenerate $H$, then $T$ contains some
large dense pair. The undirected analogue of this lemma is well-known, and
goes back at least to work of Erdős and Hajnal [17, Lemma 1.5].

######  Lemma 3.2.

Let $H$ be a $d$-degenerate digraph with $n$ vertices and maximum degree
$\Delta$, and let $0<c\leq\frac{1}{2}$. If $T$ is an $H$-free tournament on
$N\geq 2\Delta c^{-d}n$ vertices, then $T$ contains a $(1-c)$-dense pair
$(W_{1},W_{2})$ with size at least $c^{d}N/(2\Delta)$.

###### Proof.

We use the greedy embedding framework described above. Let us label the
vertices of $H$ according to the $d$-degenerate ordering as
$v_{1},v_{2},\dotsc,v_{n}.$ We initialize $U_{i}^{(0)}=V(T)$ for all $1\leq
i\leq n$. We now attempt to embed the vertices of $H$ one at a time in $T$, in
the $d$-degenerate ordering. For $j>t$, let $N_{t}(v_{j})$ denote the set of
vertices $v_{i}$ with $i\leq t$ such that $v_{i}$ and $v_{j}$ are connected by
an edge (in some direction). We inductively pick the values of $\phi(v_{t})\in
V(T)$ and maintain vertex sets $U_{i}^{(t)}$ with the following properties.

  1. 1.

For every $i\leq t$, we have $U_{i}^{(t)}=\\{\phi(v_{i})\\}$.

  2. 2.

For every $j>t$, we have $|U_{j}^{(t)}|\geq c^{|N_{t}(v_{j})|}N-t$.

  3. 3.

For $i\leq t$, if $v_{i}\to v_{j}$ then $\phi(v_{i})\to x$ for every $x\in
U_{j}^{(t)}$, and if $v_{i}\leftarrow v_{j}$ then $\phi(v_{i})\leftarrow x$
for every $x\in U_{j}^{(t)}$.

From these properties, we see that if the process continues through step
$t=n$, then we will have embedded a copy of $H$ in $T$, contradicting our
assumption that $T$ is $H$-free. Moreover, all three properties are vacuously
true for $t=0$. Now, suppose we have maintained this process up through step
$t-1$. Suppose there exists $w_{t}\in U_{t}^{(t-1)}$ such that for every $j>t$
with $v_{t}\to v_{j}$ (resp. $v_{t}\leftarrow v_{j}$), we have
$|N^{+}(w_{t})\cap U_{j}^{(t-1)}|\geq c|U_{j}^{(t-1)}|$ (resp.
$|N^{-}(w_{t})\cap U_{j}^{(t-1)}|\geq c|U_{j}^{(t-1)}|$). Then we may define
$\phi(v_{t})=w_{t}$, $U_{t}^{(t)}=\\{\phi(v_{t})\\}$, and update the remaining
sets as

$U_{j}^{(t)}\coloneqq\begin{cases}[U_{j}^{(t-1)}\cap
N^{+}(v_{t})]\setminus\\{\phi(v_{t})\\}&\text{if }v_{t}\rightarrow v_{j},\\\
{}[U_{j}^{(t-1)}\cap N^{-}(v_{t})]\setminus\\{\phi(v_{t})\\}&\text{if
}v_{j}\rightarrow v_{t},\\\
U_{j}^{(t-1)}\setminus\\{\phi(v_{t})\\}&\text{else},\end{cases}$

for all $j>t$. Properties 1 and 3 above continue to hold automatically after
round $t$, and all that remains to check is Property 2. For those $j>t$ for
which $v_{j}$ is not adjacent to $v_{t}$, $N_{t}(v_{j})=N_{t-1}(v_{j})$ and at
most one vertex is removed from $U_{j}^{(t-1)}$ to obtain $U_{j}^{(t)}$.
Therefore,

$|U_{j}^{(t)}|\geq|U_{j}^{(t-1)}|-1\geq
c^{|N_{t-1}(v_{j})|}N-(t-1)-1=c^{|N_{t}(v_{j})|}-t.$

On the other hand, if $v_{j}$ is adjacent to $v_{t}$, then
$|N_{t}(v_{j})|=|N_{t-1}(v_{j})|+1$, and therefore

$|U_{j}^{(t)}|\geq c|U_{j}^{(t-1)}|-1\geq
c\cdot(c^{|N_{t-1}(v_{j})|}N-(t-1))-1\geq c^{|N_{t}(v_{j})|}N-t.$

Thus, all three properties are maintained if such a $w_{t}$ exists.

Since we assumed that $T$ was $H$-free, this process cannot continue until
step $t=n$, and therefore must fail at some step $1\leq t\leq n-1$. Let
$W_{0}=U_{t}^{(t-1)}$. Since the process fails at this step, for every $w\in
W_{0}$, we can assign some $j>t$ such that either $v_{t}\to v_{j}$ and
$|N^{+}(w)\cap U_{j}^{(t-1)}|<c|U_{j}^{(t-1)}|$, or $v_{t}\leftarrow v_{j}$
and $|N^{-}(w)\cap U_{j}^{(t-1)}|<c|U_{j}^{(t-1)}|$. Since $v_{t}$ has at most
$\Delta$ neighbors in total, at least $|W_{0}|/\Delta$ choices of $w$ are
assigned the same $j>t$ by the pigeonhole principle. Fix such a “popular” $j$.

Suppose first that $v_{t}\to v_{j}$. Let $W_{2}=U_{j}^{(t-1)}$, and let
$W_{1}$ be the set of all $w\in W_{0}$ which have fewer than $c|W_{2}|$ out-
neighbors in $W_{2}$. Then $(W_{1},W_{2})$ is a $(1-c)$-dense pair. Similarly,
if $v_{j}\in N^{-}(v_{t})$, then we would similarly find that $(W_{2},W_{1})$
is a $(1-c)$-dense pair.

It remains to verify the lower bound on the sizes of $W_{1}$ and $W_{2}$.
Recall that the greedy embedding process succeeded up through step $t-1$,
meaning that

$|U_{t}^{(t-1)}|\geq c^{|N_{t-1}(v_{t})|}N-(t-1)\geq
c^{d}N-n\geq\frac{c^{d}N}{2},$

and similarly for $U_{j}^{(t-1)}$, where we use the $d$-degeneracy assumption
to conclude that $|N_{t-1}(v_{t})|\leq d$, and our assumption that $t<n\leq
c^{d}N/2$. Since $|W_{2}|=|U_{j}^{(t-1)}|$ and
$|W_{1}|\geq|U_{t}^{(t-1)}|/\Delta$, this completes the proof. ∎

The second lemma proves a much stronger bound when $H$ is $1$-degenerate and
weakly connected, i.e. some orientation of a tree (recall that a digraph is
called _weakly connected_ if its underlying undirected graph is connected).
Note that a $1$-dense pair in a tournament is just a pair of sets
$W_{1},W_{2}$ with all edges directed from $W_{1}$ to $W_{2}$.

######  Lemma 3.3.

Let $H$ be a weakly connected $1$-degenerate digraph with maximum degree
$\Delta$ on $m$ vertices $v_{1},\ldots,v_{m}$, and let $T$ be an arbitrary
tournament. If there exist sets $U_{1},\ldots,U_{m}\subseteq V(T)$, each of
size $M\geq 2m\Delta$ such that if there is no embedding
$\phi:H\hookrightarrow T$ satisfying $\phi(v_{i})\in U_{i}$, then $T$ contains
a $1$-dense pair with size at least $M/(m(\Delta+1))$.

###### Proof.

We begin by picking subsets $V_{1}\subseteq U_{1},\dotsc,V_{m}\subseteq
U_{m}$, each of size $M/m$, such that $V_{1},\dotsc,V_{m}$ are pairwise
disjoint. We can do this greedily, by first picking an arbitrary subset
$V_{1}\subseteq U_{1}$ of size $M/m$, then picking an arbitrary subset
$V_{2}\subseteq U_{2}\setminus V_{1}$ of size $M/m$, then picking
$V_{3}\subseteq U_{3}\setminus(V_{1}\cup V_{2})$, and so on. At the $i$th
step, we have deleted at most $(i-1)M/m\leq(m-1)M/m$ elements from $U_{i}$, so
at least $M/m$ elements remain, from which we pick $V_{i}$ arbitrarily.

The remainder of the proof is very similar to that of the previous lemma,
though it will be more convenient to work with a slightly different setup than
before. Let the vertices of $H$ be ordered so that each $v_{i}$ has at most
one neighbor $v_{j}$ with $j>i$ (this is the reverse of the usual degenerate
ordering). For each $t$, let $S_{t}$ denote the set of vertices $v_{i}$ with
$i\leq t$ that are connected to $v_{i}$ by a path of vertices whose indices
are monotonically increasing, including $v_{t}$ itself. In other words, we set
$S_{1}=\\{v_{1}\\}$, let $N_{t}(v_{t})$ denote the set of vertices $v_{i}$
adjacent to $v_{t}$ (in either orientation) with $i<t$, and set

$S_{t}=\\{v_{t}\\}\cup\bigcup_{i\in N_{t}(v_{t})}S_{i}.$

We define $W_{t}\subseteq V_{t}$ to be the set of all $w\in V_{t}$ for which
there exists an embedding $\phi:H[S_{t}]\hookrightarrow T$ mapping each
$v_{i}$ into $V_{i}$ for $v_{i}\in S_{t}$, and mapping $v_{t}$ to $w$. We know
$W_{n}=\varnothing$, since otherwise there is an embedding of $H$ into the
sets $V_{1},\dotsc,V_{m}$, contradicting our assumption. Let $t\leq n$ be the
minimum index such that $|W_{t}|<M/(m(\Delta+1))$; note that $t>1$ since
$W_{1}=V_{1}$ has size $M/m$. Let
$N_{t}(v_{t})=\\{v_{i_{1}},\dotsc,v_{i_{s}}\\}$. Our maximum degree assumption
implies $s\leq\Delta$, while if $s=0$, then $W_{t}=V_{t}$, contradicting our
assumption that $|W_{t}|<M/(m(\Delta+1))$. Thus, $1\leq s\leq\Delta$.

By definition, $W_{t}$ is precisely the set of $w\in V_{t}$ adjacent in the
appropriate orientation to at least one vertex in each of
$W_{i_{1}},\dotsc,W_{i_{s}}$. Let $X_{1},\dotsc,X_{s}\subseteq V_{t}$ denote
the choices of $w$ which do not have any edge in the appropriate orientation
to $W_{i_{1}},\dotsc,W_{i_{s}}$, respectively. We get $V_{t}=W_{t}\cup
X_{1}\cup\dotsb\cup X_{s}$. Since $s\leq\Delta$ and $|W_{t}|\leq
M/(m(\Delta+1))$, we see that there exists some $j$ for which $|X_{j}|\geq
M/(m(\Delta+1))$. Moreover, since $t$ was taken to be minimal, we have that
$|W_{i_{j}}|\geq M/(m(\Delta+1))$ as well. This yields a pair of sets
$(X_{j},W_{i_{j}})$ where all edges between them are oriented the same way,
and both sets have size at least $M/(m(\Delta+1))$. This is the desired
$1$-dense pair. ∎

We remark that we expect the $m$ dependence in Lemma 3.3 to be unnecessary,
and proving this would improve our results for random digraphs; for details,
see Conjecture 6.5 and the surrounding discussion.

We do not use Lemma 3.3 directly, but only the following simple corollary. It
allows us to find a large $1$-dense pair in $T$ whenever $T$ does not contain
a copy of some fixed oriented forest with small maximum degree and small
weakly connected components.

######  Lemma 3.4.

Let $H$ be a $1$-degenerate digraph with maximum degree $\Delta$ and vertices
$v_{1},\dotsc,v_{n}$, and suppose that every weakly connected component of $H$
has at most $m$ vertices. Let $T$ be an arbitrary tournament. For any
collection of sets $V_{1},\ldots,V_{n}\subseteq V(T)$, each of size $M\geq
3n\Delta$, either there is an embedding $\phi:H\hookrightarrow T$ satisfying
$\phi(v_{i})\in V_{i}$, or $T$ contains a $1$-dense pair with size at least
$M/(4m\Delta)$.

###### Proof.

Let the weakly connected components of $H$ be $C_{1},\dotsc,C_{r}$. We prove
the result by induction on $r$. The base case, $r=1$, follows immediately from
Lemma 3.3, since $n\geq m$ and $\Delta+1\leq 2\Delta$. For the inductive step,
let $H^{\prime}$ be the induced subgraph of $H$ consisting of the weakly
connected components $C_{1},\dotsc,C_{r-1}$. By the inductive hypothesis,
either $T$ contains a $1$-dense pair of size at least $M/(4m\Delta)$, in which
case we are done, or else there is an embedding $\phi$ of $H^{\prime}$ into
$T$ satisfying that $\phi(v_{i})\in V_{i}$ for all $v_{i}\in V(H^{\prime})$.
Let $T^{\prime}$ be the tournament obtained by deleting the image of $\phi$
from $T$, and similarly let $V_{1}^{\prime},\dotsc,V_{n}^{\prime}$ be obtained
by deleting the image of $\phi$ from $V_{1},\dotsc,V_{n}$. Since we have
deleted at most $n\leq n\Delta$ vertices, each $V_{i}^{\prime}$ has size at
least $M^{\prime}\geq 2n\Delta\geq 2m\Delta$. Therefore, by Lemma 3.3, either
$T^{\prime}$ contains a $1$-dense pair of size at least
$M^{\prime}/(2m\Delta)\geq M/(4m\Delta)$, in which case so does $T$, or else
there is an embedding of $H[C_{r}]$ into $T^{\prime}$ mapping each $v_{i}\in
C_{r}$ into $V_{i}^{\prime}$. Since we deleted the image of $\phi$ from $T$ to
define $T^{\prime}$, such an embedding yields an embedding of $H$ into $T$,
completing the induction. ∎

Our final basic greedy embedding lemma is the following, which shows that if
we assume appropriate density conditions on the sets in which we are trying to
greedily embed $H$, then we are guaranteed not to fail in the embedding. In
Subsection 3.3, we use this lemma as a basic building block. Again, the
undirected analogue of this lemma is well-known, e.g. [21, Lemma 2].

######  Lemma 3.5.

Let $H$ be an acyclic digraph with maximum degree $\Delta$ on $n$ vertices
$v_{1},\ldots,v_{n}$, and let $T$ be a tournament containing subsets
$V_{1},\ldots,V_{n}\subseteq V(T)$, each of size at least $4n$. If for every
edge $v_{i}\rightarrow v_{j}$ in $H$, $(V_{i},V_{j})$ is a
$(1-\frac{1}{8\Delta^{2}})$-dense pair, then $T$ contains a copy of $H$.

Note that the sets $V_{i}$ are allowed to overlap222However, if $v_{i}\to
v_{j}$, then the assumption that $(V_{i},V_{j})$ is
$(1-\frac{1}{8\Delta^{2}})$-dense implies that $V_{i}\cap V_{j}$ cannot be too
large. or even be identical. This is crucial; for instance, if $H$ has height
$h$ then our choice of $V_{i}$’s will take only $h$ distinct values.

###### Proof.

Every acyclic digraph has a vertex ordering where all edges point forward, so
we may reorder the vertices to assume all edges $v_{i}\rightarrow v_{j}$
satisfy $i<j$. We now run the greedy embedding process for $H$ into $T$ with
the given $U_{i}$, using essentially the same framework as we used in Lemma
3.2. The key difference is that before, the greedy embedding process could
fail and terminate prematurely, whereas the additional assumptions here
guarantee that greedy embedding runs to completion.

We begin by refining the sets $V_{1},\dotsc,V_{n}$. Namely, for every edge
$v_{i}\to v_{j}$ in $H$, let $V_{i,j}\subseteq V_{i}$ be the set of vertices
$w\in V_{i}$ with $|N^{-}(w)\cap V_{j}|\geq|V_{j}|/(4\Delta)$. Since the pair
$(V_{i,},V_{j})$ is $(1-\frac{1}{8\Delta^{2}})$-dense, there are at most
$|V_{i}||V_{j}|/(8\Delta^{2})$ edges directed from $V_{j}$ to $V_{i}$ in
total, so

$|V_{i,j}|\cdot\frac{|V_{j}|}{4\Delta}\leq\frac{|V_{i}||V_{j}|}{8\Delta^{2}},$

and thus $|V_{i,j}|\leq|V_{i}|/(2\Delta)$. Each $v_{i}$ has at most $\Delta$
out-neighbors $v_{j}$, which implies that $|\bigcup_{j}V_{i,j}|\leq|V_{i}|/2$.
Therefore, if $U_{i}\coloneqq V_{i}\setminus(\bigcup_{j}V_{i,j})$, then
$|U_{i}|\geq|V_{i}|/2$, and every vertex in $U_{i}$ has at most
$|V_{j}|/(4\Delta)\leq|U_{j}|/(2\Delta)$ in-neighbors in $U_{j}$ for every $j$
such that $v_{i}\to v_{j}$.

Now, we exhibit an embedding $\phi:H\hookrightarrow T$ by picking
$\phi(v_{t})\in U_{t}$ inductively for each $t\in[n]$, as follows. Having
picked $\phi(v_{1}),\ldots,\phi(v_{t-1})$, we claim that there is at least one
valid candidate for $\phi(v_{t})\in U_{t}$ which is consistent with the
previous choices. Indeed, there are at most $\Delta$ choices of $i<t$ such
that $v_{i}\to v_{t}$. For every such $i$, we have that $\phi(v_{i})\in
U_{i}$, which means that $\phi(v_{i})$ has at most $|U_{t}|/(2\Delta)$ in-
neighbors in $U_{t}$. Hence, at least $|U_{t}|/2$ vertices in $U_{t}$ are out-
neighbors of $\phi(v_{i})$ for all $i$ such that $v_{i}\to v_{j}$. Moreover,
at most $t-1$ vertices of $U_{j}$ have been picked as outputs of $\phi$, and
thus the number of possible candidates for $\phi(v_{t})$ is at least

$\frac{|U_{t}|}{2}-(t-1)\geq\frac{|V_{t}|}{4}-n+1\geq 1,$

by our assumption that $|V_{j}|\geq 4n$. This shows that at every step $t\leq
n$ we can pick vertex $\phi(v_{t})$ such that
$\\{\phi(v_{1}),\ldots,\phi(v_{t})\\}$ is a copy of
$H[\\{v_{1},\ldots,v_{t}\\}]$ in $T$, and so $T$ contains a copy of the
entirety of $H$, as desired. ∎

We remark that one can prove a strengthening of Lemma 2.4, where the
assumption is weakened to each pair $(V_{i},V_{j})$ being merely
$(1-\Omega(\frac{1}{\Delta}))$-dense. This can be done by replacing the greedy
embedding argument by a random embedding technique, using the Lovász local
lemma. For details, we refer the reader to [13, Lemma 4.5], where the
analogous undirected result is proved using this technique.

###  3.2 The outer stage

In this subsection, we show how two of our basic building blocks, Lemmas 3.2
and 3.4, can be iterated to construct, in any $H$-free tournament $T$, an
“approximate blowup” of $H$. This will be a large collection of vertex sets
which correspond to the vertices of $H$, such that the edges between sets are
mostly oriented in the correct direction. Before stating the result precisely,
we need some definitions.

Let $\\{0,1\\}^{*}$ denote the set of all finite binary strings. Recall that a
_prefix code_ is a set $C\subset\\{0,1\\}^{*}$ with the property that no
element of $C$ is a prefix of another element of $C$. The _depth_ of $C$ is
defined as the maximum length of an element of $C$. Let $\prec$ denote the
lexicographic ordering on $\\{0,1\\}^{*}$, namely the ordering in which
$x\prec y$ if $x$ is a proper prefix of $y$ or if $x_{i}<y_{i}$ where $i$ is
the first index for which $x_{i}\neq y_{i}$.

######  Definition 3.6.

Given an acyclic digraph $H$, a _prefix labeling_ of $H$ is a surjective map
$\rho:V(H)\to C$ for some prefix code $C\subset\\{0,1\\}^{*}$, with the
property that if $v_{i}\to v_{j}$ is an edge of $H$, then either
$\rho(v_{i})=\rho(v_{j})$ or $\rho(v_{i})\prec\rho(v_{j})$. The map $\rho$
naturally defines a graph structure on $C$, where we say that two codewords
$x,y$ are _adjacent under $\rho$_ if there exists some edge between the sets
$\rho^{-1}(x)$ and $\rho^{-1}(y)$. By the _maximum degree of $\rho$_, we mean
the maximum degree of this graph on $C$. If $\rho^{-1}(x)$ is an independent
set for every $x\in C$, then we call $\rho$ a _prefix coloring._ Less
stringently, we call $\rho$ a _forest prefix labeling_ if $\rho^{-1}(x)$ is a
directed forest (or equivalently, a $1$-degenerate digraph) for every $x\in
C$. By the _maximum component size_ of $\rho$, we mean the maximum number of
vertices of any weakly connected component in $\rho^{-1}(x)$, over all $x\in
C$. Thus, $\rho$ is a prefix coloring if and only if its maximum component
size is $1$.

Thus, we see that prefix colorings of $H$ correspond to colorings of the
underlying undirected graph of $H$, with the property that the palette of
colors $C$ is a prefix code, and that the lexicographic order on $C$ is
consistent with the edge directions in $H$. Similarly, a forest prefix
labeling is in particular a partition of the underlying undirected graph into
sets which induce forests, which corresponds to the undirected problem of
_vertex arboricity._ However, for both concepts, we will crucially use the
additional structure given both by the edge directions of $H$ and by the
structure of the prefix code $C$.

For a binary string $x$, let us denote by $x0$ and $x1$ the strings obtained
by appending a $0$ or $1$, respectively, to the end of $x$. For a prefix code
$C$, we denote by $C_{0}(x)$ the set of all elements $y\in C$ which have $x0$
as a prefix, and by $C_{1}(x)$ the set of elements that have $x1$ as a prefix.
Suppose that $\rho:V(H)\to C$ is a prefix labeling of an acyclic digraph $H$.
For binary string $x$, let us denote by $a_{0}(x)$ the number of codewords
$y\in C_{0}(x)$ which are adjacent under $\rho$ to some codeword $z\in
C_{1}(x)$. Similarly, $a_{1}(x)$ is the number of codewords $z\in C_{1}(x)$
that are adjacent under $\rho$ to some codeword $y\in C_{0}(x)$. Finally, we
let

$a(x)=\begin{cases}1&\text{if }a_{0}(x)=0\text{ or }a_{1}(x)=0,\\\
\min(a_{0}(x),a_{1}(x))&\text{otherwise.}\end{cases}$

In particular, $a(x)=1$ if $x$ is not a proper prefix of any element of $C$.
With this notation, we can now define the key parameters of $\rho$ that we
later use to bound Ramsey numbers.

######  Definition 3.7.

Let $H$ be an acyclic digraph and $\rho:V(H)\to C$ some prefix labeling of
$H$. We define the _dyadic complexity_ of $\rho$ to be the quantity

$\operatorname{comp}(\rho):=\max_{y\in C}\prod_{x\text{ a prefix of }y}a(x).$

Additionally, the _depth_ of $\rho$, denoted $\operatorname{depth}(\rho)$, is
defined as the depth of $C$, i.e. the maximum length of an element of $C$.

To understand these definitions, it is helpful to think of $\\{0,1\\}^{*}$ as
the vertices of the infinite binary tree. In this setup, the elements of a
prefix code $C$ correspond to the leaves of some subtree. A prefix labeling
$\rho:V(H)\to C$ is then a partition of the vertices of $H$ into sets labeled
by the leaves of this subtree. Two codewords (leaves) are adjacent under
$\rho$ if there is an edge between the corresponding vertex subsets of $H$.
For a binary string $x$, which should be thought of as a non-leaf vertex of
the subtree, $a(x)$ roughly records the “cost” of separating the descendants
of $x$: it measures how many pairs of codewords adjacent under $\rho$ there
are between its descendants on the left and on the right. Because of the
structure of the proof, this cost function is somewhat unnatural: it is the
minimum of two quantities, each of which is the number of descendants on one
side which are adjacent under $\rho$ to any number of descendants on the other
side. Moreover, this cost function should be thought of as multiplicative, so
that the ultimate cost of the whole labeling—namely the dyadic complexity
$\operatorname{comp}(\rho)$—is the product of the costs of all ancestors of
$y$, maximized over all $y\in C$.

We remark that the dyadic complexity of a prefix coloring of $H$ is one
possible formalization of the notion of multiscale complexity discussed in the
introduction. Indeed, if every prefix coloring of $H$ has high dyadic
complexity, then $H$ has many edges at “many different dyadic scales”. All of
our upper bounds on oriented Ramsey numbers depend on the dyadic complexity of
some prefix labeling of $H$, making formal the intuition that the strength of
our upper bound results depends on whether $H$ has high or low multiscale
complexity.

In order to embed some acyclic digraph $H$ in a tournament $T$, we first build
a certain structure of vertex subsets of $T$ with high forward edge density
between many of the pairs. Then, in the inner stage of the embedding process,
we use such a structure to find a copy of $H$. The structure we build depends
on a parameter $\delta\in[0,1]$, as well as on a prefix labeling $\rho$ of
$H$. We now define this structure, and next prove a lemma showing how to find
such a structure.

######  Definition 3.8.

Let $\delta\in[0,1]$ be some parameter, let $H$ be an acyclic digraph, and let
$\rho:V(H)\to C$ be some prefix labeling of $H$, for some prefix code $C$. Let
$T$ be any tournament. A _$(\rho,\delta)$ -skeleton _is a collection
$\\{V_{x}\\}_{x\in C}$ of (not necessarily disjoint) vertex subsets of $T$,
indexed by the codewords in $C$, with the property that if $x\prec y$ are
elements of $C$ that are adjacent under $\rho$, then $(V_{x},V_{y})$ is a
$\delta$-dense pair. We define the _size_ of a $(\rho,\delta)$-skeleton to be
$\min_{x\in C}|V_{x}|$.

Our next lemma shows how to iterate Lemma 3.2 to construct a
$(\rho,\delta)$-skeleton in any sufficiently large $H$-free tournament $T$.
Roughly speaking, since the structure of a $(\rho,\delta)$-skeleton is based
on the binary tree structure of $C$, we may construct such a skeleton by
performing a depth-first search, and applying Lemma 3.2 every time we need to
split an existing node into two daughter nodes in this binary tree.

######  Lemma 3.9.

Let $c\in(0,1)$ be some parameter, let $H$ be a $d$-degenerate acyclic digraph
with maximum degree $\Delta$, and let $\rho:V(H)\to C$ be some prefix labeling
of $H$, for some prefix code $C$. Suppose that $T$ is an $H$-free tournament
on $N$ vertices, with

$N\geq\left(\frac{4^{d+1}\Delta}{c^{d}}\right)^{\operatorname{depth}(\rho)}\operatorname{comp}(\rho)^{d}n.$

Then $T$ contains a $(\rho,1-c)$-skeleton of size at least
$\left(\frac{c^{d}}{4^{d+1}\Delta}\right)^{\operatorname{depth}(\rho)}\operatorname{comp}(\rho)^{-d}N$.

###### Proof.

For every binary string $x\in\\{0,1\\}^{*}$ which is a prefix of some codeword
in $C$, let $H_{x}$ denote the subgraph of $H$ induced by the vertices $v$ for
which $x$ is a prefix of $\rho(v)$. We will construct, for every such
$x\in\\{0,1\\}^{*}$, a vertex subset $V_{x}\subseteq V(T)$, with

$|V_{x}|\geq\left(\prod_{z\text{ a proper prefix of
}x}\frac{c^{d}}{4^{d+1}\Delta a(z)^{d}}\right)N.$

We initialize $V_{\varnothing}=V(T)$, where $\varnothing\in\\{0,1\\}^{*}$
denotes the empty string, and observe that this property holds vacuously for
$V_{\varnothing}$ since $\varnothing$ has no proper prefixes. In order to
construct these vertex sets for other $x$, we proceed via a depth-first search
along the binary tree, as follows. Recall that for any binary string $x$, the
numbers $a_{0}(x)$ and $a_{1}(x)$ are the number of codewords in $C$ beginning
with $x0$ and $x1$, respectively, such that some vertex labeled by that
codeword has an edge to $H_{x1}$ and $H_{x0}$, respectively. If
$\min(a_{0}(x),a_{1}(x))=0$, then we define $V_{x0}=V_{x1}=V_{x}$, and observe
that our desired inequality holds, since $a(x)=1$ in this case. In particular,
if $x\in C$ is a codeword, then we stop the inductive process, since we only
wished to define such vertex subsets for strings $x$ that are the prefix of
some codeword. Now, suppose that $\min(a_{0}(x),a_{1}(x))\geq 1$, and assume
without loss of generality333If $a_{1}(x)<a_{0}(x)$, then we swap the roles of
$0$ and $1$ and the roles of in- and out-neighbors in this construction. that
$a_{0}(x)\leq a_{1}(x)$. We will first show how to define $V_{x0}\subseteq
V_{x}$ satisfying the desired inequality on its cardinality. We will then
proceed to recursively define vertex subsets $V_{y}\subseteq V_{x0}$ for every
binary string $y$ prefixed by $x0$. Note that we have not yet defined the set
$V_{x1}$: we are proceeding in a depth-first fashion, so we will not define
$V_{x1}$ until we have defined $V_{y}$ for every $y$ prefixed by $x0$. This
will eventually happen, since we already described above how to define $V_{y}$
if $y$ is a codeword of $C$; therefore, we eventually reach the bottom of our
depth-first search (namely a codeword $y\in C$), at which point we stop going
down the tree, and begin to retrace our steps and traverse back up the tree.

Recall that we assumed that $a_{0}(x)\leq a_{1}(x)$, and let
$c_{x}=c/(4a_{0}(x)).$ Since

$\displaystyle|V_{x}|$ $\displaystyle\geq\left(\prod_{z\text{ a proper prefix
of }x}\frac{c^{d}}{4^{d+1}\Delta a(z)^{d}}\right)N$
$\displaystyle=\frac{4\Delta(4a(x))^{d}}{c^{d}}\left(\prod_{z\text{ a proper
prefix of }x0}\frac{c^{d}}{4^{d+1}\Delta a(z)^{d}}\right)N$
$\displaystyle\geq\frac{\left(c^{d}/(4^{d+1}\Delta)\right)^{\operatorname{depth}(\rho)}\operatorname{comp}(\rho)^{-d}}{c^{d}/(4\Delta(4a(x))^{d})}N$
$\displaystyle\geq 4\Delta c_{x}^{-d}n,$ (3.1)

and since $T$ contains no copy of $H$, we may apply Lemma 3.2 with parameter
$c_{x}$. Then this lemma says that $V_{x}$ contains a $(1-c_{x})$-dense pair
$(W_{0},W_{1})$, where $\min(|W_{0}|,|W_{1}|)\geq c_{x}^{d}|V_{x}|/(2\Delta)$.
Let $V_{x0}\subseteq W_{0}$ denote the set of vertices in $W_{0}$ whose in-
degree to $W_{1}$ is at most $2c_{x}|W_{1}|$; since there are at most
$(1-c_{x})|W_{0}||W_{1}|$ edges directed from $W_{1}$ to $W_{0}$, we see that
$|V_{x0}|\geq|W_{0}|/2$. Therefore,

$|V_{x0}|\geq\frac{c_{x}^{d}}{4\Delta}|V_{x}|=\frac{c^{d}}{4^{d+1}\Delta
a(x)^{d}}|V_{x}|\geq\left(\prod_{z\text{ a proper prefix of
}x0}\frac{c^{d}}{4^{d+1}\Delta a(z)^{d}}\right)N,$ (3.2)

since the proper prefixes of $x0$ are just $x$, in addition to all the proper
prefixes of $x$ itself.

As discussed above, we can now recursively define $V_{y}$ for all $y$ prefixed
by $x0$. It thus only remains to define $V_{x1}\subseteq V_{x}$, under the
assumption that we have defined $V_{y}\subseteq V_{x0}\subseteq W_{0}$ for all
$y$ prefixed by $x0$.

To do so, let $y_{1},\dotsc,y_{a_{0}(x)}$ denote the set of codewords prefixed
by $x0$ with the property that some vertex in $\rho^{-1}(y_{i})$ is adjacent
to some vertex in $H_{x1}$, noting that there are exactly $a_{0}(x)$ such
codewords by the definition of $a_{0}(x)$. Let $W_{1}^{(i)}$ denote the subset
of $W_{1}$ consisting of vertices in $W_{1}$ whose out-degree to $V_{y_{i}}$
is at least $c|V_{y_{i}}|$. Since every vertex in $V_{y_{i}}\subseteq V_{x0}$
has at most $2c_{x}|W_{1}|$ in-neighbors in $W_{1}$, we see that the total
number of edges directed from $W_{1}$ to $V_{y_{i}}$ is at most
$2c_{x}|W_{1}||V_{y_{i}}|$, and therefore
$|W_{1}^{(i)}|\leq(2c_{x}/c)|W_{1}|$. Because of this, we have that

$\left|\bigcup_{i=1}^{a_{0}(x)}W_{1}^{(i)}\right|\leq\sum_{i=1}^{a_{0}(x)}|W_{1}^{(i)}|\leq
a_{0}(x)\frac{2c_{x}}{c}|W_{1}|=\frac{|W_{1}|}{2}.$

Therefore, we can define
$V_{x1}=W_{1}\setminus\left(\bigcup_{i=1}^{a_{0}(x)}W_{1}^{(i)}\right)$, and
we have that $|V_{x1}|\geq|W_{1}|/2$. By the same computation as in equation
(3.2), we see that this definition of $V_{x1}$ satisfies our desired lower
bound on the size of $V_{x1}$.

We claim that in this construction, if $y\prec z$ are codewords that are
adjacent under $\rho$, then the pair $(V_{y},V_{z})$ is $(1-c)$-dense. To see
this, let $x$ be the longest common prefix of $y$ and $z$. In the construction
at level $x$, we first proceeded to either $V_{x0}$ or $V_{x1}$ in the depth-
first search, depending on the relative sizes of $a_{0}(x)$ and $a_{1}(x)$. In
the former case, we ensured that every vertex in $V_{x1}$ had out-degree at
most $c|V_{y}|$ to $V_{y}$, while in the latter case, we ensured that every
vertex in $V_{x0}$ had in-degree at most $c|V_{z}|$ to $V_{z}$. In either
case, we see that $(V_{y},V_{z})$ is $(1-c)$-dense, since $V_{y}\subseteq
V_{x0}$ and $V_{z}\subseteq V_{x1}$. Additionally, by the same computation as
in equation (3.1), we see that
$|V_{y}|\geq\left(\frac{c^{d}}{4^{d+1}\Delta}\right)^{\operatorname{depth}(\rho)}\operatorname{comp}(\rho)^{-d}N$
for every $y\in C$. This verifies all the properties of a
$(\rho,1-c)$-skeleton, and concludes the proof. ∎

Our next two lemmas are very similar to Lemmas 3.2 and 3.9. Namely, the first
shows us how to find a $1$-dense pair in an $H$-free tournament $T$, and the
second then iterates the first to form a skeleton of $1$-dense pairs. The main
difference between these and the previous results are that for these lemmas,
we need strengthened assumptions on $H$ (namely that it has a directed
partition into forests). Moreover, the first step in the proof is an
application of Lemma 3.9, and we find the $1$-dense pair by failing to
greedily embed $H$ in the skeleton given by Lemma 3.9.

######  Lemma 3.10.

Let $d\geq 2$, and suppose that $H$ is a $d$-degenerate acyclic digraph on $n$
vertices with maximum degree $\Delta$, and suppose that $\rho:V(H)\to C$ is
some forest prefix labeling with maximum degree $A$ and maximum component size
$m$. Let $T$ be an $H$-free tournament on
$N\geq(2^{10}A\Delta^{2})^{d\operatorname{depth}(\rho)}\operatorname{comp}(\rho)^{d}n$
vertices. Then $T$ contains a $1$-dense pair $(U_{1},U_{2})$ of size at least
$m^{-1}(2^{10}A\Delta^{2})^{-d\operatorname{depth}(\rho)}\operatorname{comp}(\rho)^{-d}N$.

###### Proof.

We first apply Lemma 3.9 to the prefix labeling $\rho$ and with parameter
$c=1/(16A\Delta)$. This lemma outputs a
$(\rho,1-\frac{1}{16A\Delta})$-skeleton $\\{V_{x}\\}_{x\in C}$ in $T$ of size
at least

$\left(\frac{c^{d}}{4^{d+1}\Delta}\right)^{\operatorname{depth}(\rho)}\operatorname{comp}(\rho)^{-d}N\geq
12\Delta n.$

For every pair of codewords $x\prec y$ that are adjacent under $\rho$, let
$V_{x,y}$ denote the set of vertices in $V_{x}$ whose in-degree to $V_{y}$ is
at least $\frac{1}{8\Delta}|V_{y}|$. Since at most
$\frac{1}{16A\Delta}|V_{x}||V_{y}|$ of the edges between $V_{x}$ and $V_{y}$
are directed from $V_{y}$ to $V_{x}$, we see that
$|V_{x,y}|\leq\frac{1}{2A}|V_{x}|$. Therefore, if we define
$V_{x}^{\prime}=V_{x}\setminus\left(\bigcup_{y\succ x}V_{x,y}\right)$, then we
see that $|V_{x}^{\prime}|\geq\frac{1}{2}|V_{x}|$, since there are at most $A$
choices for $y\succ x$ with $x,y$ adjacent under $\rho$. Additionally, every
vertex in $V_{x}^{\prime}$ has in-degree at most
$\frac{1}{8\Delta}|V_{y}|\leq\frac{1}{4\Delta}|V_{y}^{\prime}|$ from any
$V_{y}^{\prime}$ with $y\succ x$ such that $x,y$ are adjacent under $\rho$. We
now attempt to greedily embed $H$ in these sets $\\{V_{x}^{\prime}\\}_{x\in
C}$.

Let the codewords of $C$ be $x_{1},\dotsc,x_{r}$, sorted so that $i<j$ if and
only if $x_{i}\prec x_{j}$. Let $P_{i}=\rho^{-1}(x_{i})$, so that $P_{i}$ is
an oriented forest, each of whose weakly connected components has at most $m$
vertices. Additionally, $P_{1}\sqcup\dotsb\sqcup P_{r}$ forms a directed
partition of $V(H)$, which we recall means that every edge of $H$ is oriented
from $P_{i}$ to $P_{j}$ where $i\leq j$. For every vertex $v\in P_{i}$, we
initialize a set of candidates $U_{i,v}^{(0)}=V_{x_{i}}^{\prime}$.
Inductively, having defined $U_{i,v}^{(t)}$ for each $i>t$ and each $v\in
P_{i}$, we attempt to pick an embedding $\phi_{t}:H[P_{t}]\hookrightarrow
V_{x_{t}}^{\prime}$, such that for every $v\in P_{t}$, $\phi_{t}(v)\in
U_{t,v}^{(t-1)}$. If such a $\phi_{t}$ exists, then for each $i>t$ and each
$v\in P_{i}$, we let

$U_{i,v}^{(t)}\coloneqq\\{u\in
U_{i,v}^{(t-1)}\backslash\phi_{t}(P_{t}):{\forall w\in N^{-}(v)\cap
P_{t},}\phi_{t}(w)\rightarrow u\\}.$

Note that by the structure of the sets
$V_{x_{1}}^{\prime},\dotsc,V_{x_{r}}^{\prime}$, we only change $U_{i,v}^{(t)}$
as follows. First, in at most $\Delta$ steps, we embed an in-neighbor of $v$,
and we decrease $|U_{i,v}^{(t)}|$ by at most
$\frac{1}{4\Delta}|V_{x_{i}}^{\prime}|$. Additionally, we remove at most $n$
additional vertices from $U_{i,v}^{(t)}$, corresponding to vertices that were
picked as images of $\phi_{t}$. In total, we remove at most
$\Delta\cdot\frac{1}{4\Delta}|V_{x_{i}}^{\prime}|+n\leq\frac{1}{2}|V_{x_{i}}^{\prime}|$
vertices. We thus see that
$|U_{i,v}^{(t)}|\geq\frac{1}{2}|V_{x_{i}}^{\prime}|$ for all $t$.

If we are able to run this process for all $1\leq t\leq r$, then we have
embedded a copy of $H$ in $T$, so we may assume that the process fails at some
step $t$. This means that there is no embedding
$\phi_{t}:H[P_{t}]\hookrightarrow T$ such that every vertex $v\in P_{t}$ is
mapped to $U_{t,v}^{(t-1)}$. Therefore, by applying Lemma 3.4 to $H[P_{t}]$,
we conclude that $T$ contains a $1$-dense pair $(U_{1},U_{2})$ of size at
least

$\frac{|U_{t,v}^{(t-1)}|}{4m\Delta}\geq\frac{|V_{x_{t}}|}{16m\Delta}\geq\frac{1}{m}(2^{10}A\Delta^{2})^{-d\operatorname{depth}(\rho)}\operatorname{comp}(\rho)^{-d}N.\qed$

Our next result shows how we can iterate the previous lemma to construct many
$1$-dense pairs. The iteration is nearly identical to the one in Lemma 3.9,
where we iterated the construction of one dense pair to the construction of a
$(\rho,1-c)$-skeleton. This lemma takes as input two (not necessarily
distinct) prefix labelings on $H$, one of which is a forest labeling. The
reason to have two separate labelings is that it may be useful to use the
failure of embedding of $H$ according to one labeling to construct a good
embedding structure for the other labeling.

######  Lemma 3.11.

Let $d\geq 2$, and suppose that $H$ is a $d$-degenerate acyclic digraph on $n$
vertices with maximum degree $\Delta$. Let $\rho_{1}:V(H)\to C_{1}$ and
$\rho_{2}:V(H)\to C_{2}$ be two prefix labelings, such that $\rho_{1}$ is a
forest prefix labeling of maximum degree $A_{1}$ and maximum component size
$m_{1}$. Let

$\gamma=\left(m_{1}(2^{10}A_{1}\Delta^{2})^{d\operatorname{depth}(\rho_{1})}\operatorname{comp}(\rho_{1})^{d}\right)^{-1}.$

If $T$ is an $H$-free tournament on
$N\geq\gamma^{-\operatorname{depth}(\rho_{2})}n$ vertices, then $T$ contains a
$(\rho_{2},1)$-skeleton of size at least
$\gamma^{\operatorname{depth}(\rho_{2})}N$.

###### Proof.

As in the proof of Lemma 3.9, we construct our skeleton by assigning a set
$V_{x}\subseteq V(T)$ for every $x\in\\{0,1\\}^{*}$ that is a prefix of some
codeword in $C_{2}$, with the property that $V_{x0},V_{x1}$ are both subsets
of $V_{x}$. We guarantee inductively that

$|V_{x}|\geq\gamma^{|x|}N,$ (3.3)

where $|x|$ is the length of $x$. To begin the induction, we set
$V_{\varnothing}=V(T)$, which satisfies our size hypothesis since
$|\varnothing|=0$. Inductively, suppose we’ve defined $V_{x}$. If $x\in
C_{2}$, we stop. If not, we apply Lemma 3.10 to the induced subtournament on
$V_{x}$, which we may do since

$\displaystyle|V_{x}|$
$\displaystyle\geq\gamma^{|x|}N\geq\gamma^{\operatorname{depth}(\rho_{2})-1}N\geq(2^{10}A_{1}\Delta^{2})^{d\operatorname{depth}(\rho_{1})}\operatorname{comp}(\rho_{1})^{d}n.$

This allows us to find a $1$-dense pair $(U_{1},U_{2})$ of size at least
$\gamma|V_{x}|$. We then set $V_{x0}=U_{1}$ and $V_{x1}=U_{2}$, which we see
satisfy (3.3) inductively. We continue in this way until we define $V_{x}$ for
every $x\in C_{2}$. To conclude, suppose that $y,z\in C_{2}$ are adjacent
under $\rho_{2}$, and let $x$ be their longest common prefix. Then
$V_{y}\subseteq V_{x0}$ and $V_{z}\subseteq V_{x1}$, and we know that every
edge between $V_{x0}$ and $V_{x1}$ is oriented from $V_{x0}$ to $V_{x1}$,
which implies that $(V_{y},V_{z})$ is $1$-dense, as claimed. ∎

###  3.3 The inner stage

In this subsection, we will see how to use the various structures built in the
previous subsection to successfully embed a copy of $H$ in any sufficiently
large tournament $T$. The basic idea is that the $(\rho,\delta)$-skeletons
constructed in Lemmas 3.9 and 3.11 are precisely the structures we need in
order to apply Lemma 3.5 and find a copy of $H$.

Recall that a prefix coloring is a prefix labeling where the preimage of every
codeword is an independent set. Our first result here shows a general upper
bound on $\overrightarrow{r_{1}}(H)$ in terms of the depth and complexity of a
prefix coloring of $H$.

######  Theorem 3.12.

Let $H$ be an acyclic digraph on $n$ vertices with maximum degree $\Delta\geq
1$. Then for any prefix coloring $\rho:V(H)\to C$, we have
$\overrightarrow{r_{1}}(H)\leq N$, where

$N=\left(2^{5\Delta+4}\Delta^{2\Delta+1}\right)^{\operatorname{depth}(\rho)}\operatorname{comp}(\rho)^{\Delta}n.$

###### Proof.

Let $T$ be a tournament on $N$ vertices, and suppose for contradiction that
$T$ is $H$-free. By Lemma 3.9 applied with $d=\Delta$ and
$c=\frac{1}{8\Delta^{2}}$, we can find in $T$ a
$(\rho,1-\frac{1}{8\Delta^{2}})$-skeleton $\\{V_{x}\\}_{x\in C}$ of size at
least

$\left(\frac{(8\Delta^{2})^{-\Delta}}{4^{\Delta+1}\Delta}\right)^{\operatorname{depth}(\rho)}\operatorname{comp}(\rho)^{-\Delta}N=\left(2^{5\Delta+2}\Delta^{2\Delta+1}\right)^{-\operatorname{depth}(\rho)}\operatorname{comp}(\rho)^{-\Delta}N\geq
4n.$

Now, for any vertex $v_{i}\in V(H)$, let $V_{i}=V_{\rho(v_{i})}$. Then since
$\rho^{-1}(x)$ is an independent set for any $x\in C$, we see that if
$v_{i}\to v_{j}$ is an edge of $H$, then $(V_{i},V_{j})$ is a
$(1-\frac{1}{8\Delta^{2}})$-dense pair. Therefore, by Lemma 3.5, we conclude
that $T$ contains a copy of $H$. ∎

The second result of this subsection uses the $(\rho,1)$-skeletons we
constructed in case we are given a forest prefix labeling. Using this
skeleton, we are able to prove the following result, which takes as input a
forest prefix labeling and any arbitrary prefix labeling (which may be the
same as the forest prefix labeling). The output is a bound on the Ramsey
number, in terms of the depth and complexity of the first labeling, and in
terms of the maximum Ramsey number of the parts in the partition induced by
the second prefix labeling.

######  Theorem 3.13.

Let $d\geq 2$, and let $H$ be a $d$-degenerate acyclic digraph on $n$ vertices
with maximum degree $\Delta$. Suppose that $\rho_{1}:V(H)\to C_{1}$ is a
forest prefix labeling of $H$ and that $\rho_{2}:V(H)\to C_{2}$ is any prefix
labeling. Let $A_{1}$ and $m_{1}$ be the maximum degree and maximum component
size of $\rho_{1}$, respectively. Then $\overrightarrow{r_{1}}(H)\leq N$,
where

$N=\left(m_{1}(2^{10}A_{1}\Delta^{2})^{d\operatorname{depth}(\rho_{1})}\operatorname{comp}(\rho_{1})^{d}\right)^{\operatorname{depth}(\rho_{2})}\max\left(n,\max_{x\in
C_{2}}\overrightarrow{r_{1}}(H[\rho_{2}^{-1}(x)])\right).$

###### Proof.

Let $T$ be a tournament on $N$ vertices, and suppose that $T$ is $H$-free. We
apply Lemma 3.11 to $T$, which allows us to find a $(\rho_{2},1)$-skeleton
$\\{V_{x}\\}_{x\in C_{2}}$ where

$|V_{x}|\geq\max_{y\in
C_{2}}\overrightarrow{r_{1}}(H[\rho_{2}^{-1}(y)])\geq\overrightarrow{r_{1}}(H[\rho_{2}^{-1}(x)])$

for all $x\in C_{2}$. In other words, this is a collection of disjoint sets
$\\{V_{x}\\}_{x\in C_{2}}$ such that if $x$ precedes $y$ in the lexicographic
ordering, then every edge is oriented from $V_{x}$ to $V_{y}$. By the
definition of the Ramsey number, we see that the induced subtournament
$T[V_{x}]$ must contain a copy of $H[\rho_{2}^{-1}(x)]$ for all $x\in C_{2}$.
We pick such a copy arbitrarily for each $x\in C_{2}$, and observe that their
union forms a copy of $H$ in $T$. ∎

##  4 Upper bounds on oriented Ramsey numbers

###  4.1 Upper bounds in terms of height

Theorem 3.12, which bounds $\overrightarrow{r_{1}}(H)$ in terms of the dyadic
complexity and depth of a prefix coloring, allows us to prove bounds on
$\overrightarrow{r_{1}}(H)$ in terms of other, more natural, parameters. For
instance, the next lemma relates the height of an acyclic digraph to its
dyadic complexity and depth.

######  Lemma 4.1.

If $H$ is an acyclic digraph of height $h$, then there exists a prefix
coloring $\rho:V(H)\to C$ with $\operatorname{depth}(\rho)\leq\lceil\log
h\rceil$ and $\operatorname{comp}(\rho)\leq h^{\lceil\log h\rceil}$.

###### Proof.

Recall that if $H$ has height $h$, then $H$ has a directed partition
$P_{0},\ldots,P_{h-1}$ into $h$ independent sets. This partition naturally
yields a prefix coloring using the prefix code $C$ consisting of all binary
strings of length $\lceil\log h\rceil$. Namely, we can label each vertex in
$P_{i}$ by the base-$2$ representation of $i$, and this yields a prefix
coloring with depth $\lceil\log h\rceil$. To estimate the dyadic complexity of
this prefix coloring, note that for any binary string $x$ of length
$\ell\leq\lceil\log h\rceil$, we have that $a(x)\leq 2^{\lceil\log
h\rceil-\ell}$, since there are at most $2^{\lceil\log h\rceil-\ell}$
codewords in $C$ prefixed by $x$. Therefore,

$\operatorname{comp}(\rho)\leq\prod_{\ell=0}^{\lceil\log h\rceil}2^{\lceil\log
h\rceil-\ell}=2^{\lceil\log h\rceil^{2}-\sum_{\ell=0}^{\lceil\log
h\rceil}\ell}\leq h^{\lceil\log h\rceil}.\qed$

Then Theorem 1.4 follows as a simple corollary.

###### Proof of Theorem 1.4.

The result is immediate if $\Delta=1$, so assume $\Delta\geq 2$. Let $\rho$ be
the prefix coloring from Lemma 4.1, which has
$\operatorname{depth}(\rho)\leq\lceil\log h\rceil$ and
$\operatorname{comp}(\rho)\leq h^{\lceil\log h\rceil}$. By Theorem 3.12,

$\overrightarrow{r_{1}}(H)\leq\left(2^{5\Delta+4}\Delta^{2\Delta+1}\right)^{\operatorname{depth}(\rho)}\operatorname{comp}(\rho)^{\Delta}n\leq
2^{7\Delta\log h}\Delta^{3\Delta\log h}h^{2\Delta\log h}n\leq(\Delta
h)^{10\Delta\log h}n.\qed$

Similarly, given a graded digraph, one can find a prefix coloring with small
depth and dyadic complexity.

######  Lemma 4.2.

If $H$ is a graded acyclic digraph of height $h$, then there exists a prefix
coloring $\rho:V(H)\to C$ with $\operatorname{depth}(\rho)\leq\lceil\log
h\rceil$ and $\operatorname{comp}(\rho)=1$.

###### Proof.

The proof is identical to that of Lemma 4.1, except that $a(x)\leq 1$ for
every binary string $x$, since the only codeword prefixed by $x0$ that can
have edges to a codeword prefixed by $x1$ is the codeword
$(x,0,1,1,\dotsc,1)$. ∎

As before, Theorem 1.5 follows as a corollary.

###### Proof of Theorem 1.5.

We may again assume that $\Delta\geq 2$. Let $\rho$ be the prefix coloring
from Lemma 4.2, with $\operatorname{depth}(\rho)\leq\lceil\log h\rceil$ and
$\operatorname{comp}(\rho)=1$. Then from Theorem 3.12,

$\overrightarrow{r_{1}}(H)\leq\left(2^{5\Delta+4}\Delta^{2\Delta+1}\right)^{\operatorname{depth}(\rho)}\operatorname{comp}(\rho)^{\Delta}n\leq
2^{7\Delta\log h}\Delta^{3\Delta\log h}n\leq h^{10\Delta\log\Delta}n.\qed$

Recall from the introduction that the bandwidth of an $n$-vertex acyclic
digraph $H$ is the least $\ell$ so that $P_{n}^{\ell}$ contains $H$. Using the
same argument, one can obtain a bound of $\overrightarrow{r_{1}}(H)\leq
n^{O_{\ell}(1)}$ for any $n$-vertex acyclic digraph of bandwidth at most
$\ell$, using the fact that the same binary-representation prefix coloring
have dyadic complexity at most $n^{O(\log\ell)}$. However, since the Ramsey
number of bounded-bandwidth acyclic digraphs is known to be linear [14], we
omit the proof of this weaker result.

###  4.2 Upper bounds for random digraphs

In this section, we prove Theorem 1.3, showing that if $d\geq 1$ is bounded,
then w.h.p. $\overrightarrow{r_{1}}(H)$ is nearly linear when
$H=\overrightarrow{G}(n,d)$. Additionally, we prove a nearly-linear upper
bound when $p=d/n$ and $H=\overrightarrow{G}(n,p)$.

We will need the following result of Dross and Havet [15] mentioned in the
introduction. They only state this result for orientations of trees, but one
can easily extend it to orientations of forests by adding edges to join
distinct connected components.

######  Theorem 4.3.

Let $H$ be a $1$-degenerate digraph (i.e. an orientation of an undirected
forest) on $n\geq 2$ vertices. If $T$ is any tournament on at least
$\frac{21}{8}n-\frac{47}{16}$ vertices, then $T$ contains a copy of $H$.

We recall that the _vertex arboricity_ of an undirected graph is the minimum
number of subsets needed to cover the vertices of the graph, such that each
subset induces a forest (see e.g. [5] for more on this undirected graph
parameter). We first define a natural directed analogue of this quantity,
though for technical reasons we also keep track of the maximum component size
in such a partition.

######  Definition 4.4.

The _directed vertex arboricity_ $\overrightarrow{va}(H)$ of an acyclic
digraph $H$ is the minimum size $r$ of a directed partition of $H$ into sets
$\\{P_{i}\\}_{i=1}^{r}$ where $H[P_{i}]$ is $1$-degenerate for all $i$.

Additionally, if $H$ has a directed partition into sets
$\\{P_{i}\\}_{i=1}^{r}$ such that $H[P_{i}]$ is $1$-degenerate for all $i$,
and every weakly connected component in $H[P_{i}]$ has at most $m$ vertices,
then we say that $H$ has an _$(r,m)$ -forest partition_.

Both of our upper bound results for random digraphs follow from the following
theorem, which yields an upper bound on $\overrightarrow{r_{1}}(H)$ in terms
of the degeneracy, maximum degree, and forest partition size of $H$.

######  Theorem 4.5.

Let $H$ be an acyclic digraph on $n$ vertices with maximum degree $\Delta$,
degeneracy $d\geq 2$, and with an $(r,m)$-forest partition. Then
$\overrightarrow{r_{1}}(H)\leq(r\Delta)^{6d(\log r)^{2}}m^{2\log r}n$.

###### Proof.

Let $s=\lceil\log r\rceil$, and let $C$ denote the prefix code consisting of
all strings of length $s$. Fix a partition $P_{0}\sqcup\dotsb\sqcup P_{r-1}$
of $V(H)$ into directed forests such that every edge between $P_{i}$ and
$P_{j}$ is oriented from $P_{i}$ to $P_{j}$ for all $i<j$, and such that
$H[P_{i}]$ has weakly connected components of size at most $m$. Let
$\rho:V(H)\to C$ be the forest prefix labeling mapping $P_{i}$ to the binary
representation of $i$. Then the maximum degree of $\rho$ is at most
$|C|=2^{s}\leq 2r$, the maximum component size of $\rho$ is at most $m$, and
$\operatorname{depth}(\rho)=s$. Moreover, we can bound the dyadic complexity
of $\rho$ as $\operatorname{comp}(\rho)\leq r^{s}$, since every binary string
is the prefix of at most $r$ codewords in $C$. We now now apply Theorem 3.13
with $\rho_{1}=\rho_{2}=\rho$. We recall that since $\rho^{-1}(x)$ is a forest
for every $x$, we have that $\overrightarrow{r_{1}}(H[\rho^{-1}(x)])\leq 3n$
by Theorem 4.3. Therefore,

$\displaystyle\overrightarrow{r_{1}}(H)$
$\displaystyle\leq\left(m_{1}(2^{10}A_{1}\Delta^{2})^{d\operatorname{depth}(\rho_{1})}\operatorname{comp}(\rho_{1})^{d}\right)^{\operatorname{depth}(\rho_{2})}\max\left(n,\max_{x\in
C_{2}}\overrightarrow{r_{1}}(H[\rho_{2}^{-1}(x)])\right)$
$\displaystyle\leq\left(m(2^{11}r\Delta^{2})^{ds}r^{ds}\right)^{s}\cdot(3n)$
$\displaystyle\leq(r\Delta)^{6d(\log r)^{2}}m^{2\log r}n.\qed$

It remains to check that both $\overrightarrow{G}(n,d)$ and
$\overrightarrow{G}(n,p)$ satisfy the conditions of Theorem 4.5 for
appropriate $\Delta,d,m,$ and $r$. Maximum degree and degeneracy are both easy
to control for these graphs, so the nontrivial part is bounding their directed
vertex arboricity, or more precisely the parameters of a forest partition.

Consider the random digraph $\overrightarrow{G}(n,p)$, where $np=d\geq 1$. The
idea for bounding $\overrightarrow{va}(H)$ is to equitably divide $[n]$ into
$5d$ intervals $I_{i}$, and note that $H[I_{i}]\sim\overrightarrow{G}(n/5d,p)$
is in the subcritical regime of the Erdős–Rényi random graph process, so
w.h.p. is a union of trees and unicyclic components, each comprising $O(\log
n)$ vertices. Each interval $I_{i}$ can be further divided in two to break the
unicyclic components, which shows that w.h.p. we have a $(10d,O(\log
n))$-forest partition. The analysis is broadly similar for
$H=\overrightarrow{G}(n,d)$ but somewhat more technical.

Recall that if $d\geq 1$ and $nd$ is even, a uniformly random undirected
$d$-regular graph $G(n,d)$ can be generated using the “pairings model” (also
known as the “configurations model”) of Bollobás [3], see the survey of
Wormald [39]. The pairings model of $G(n,d)$ generates a random $d$-regular
multi-graph (with self-loops allowed) by taking a uniformly random perfect
matching (a “pairing”) on $nd$ points divided into $n$ $d$-sets, and then
contracting each $d$-set into a single vertex. There are a total of

$P(nd)=\frac{(nd)!}{(nd/2)!\cdot 2^{nd/2}}$

such pairings, and any simple $d$-regular graph is equally likely to be
generated. If $d\geq 1$ is fixed and $n\rightarrow\infty$, it is known that
the probability a pairing generates a simple graph is asymptotic to
$e^{(1-d^{2})/4}$. To generate an honest $G(n,d)$, repeatedly sample from the
above model (expected constant number of samples) until a simple graph is
found.

######  Lemma 4.6.

If $d\geq 2$ is fixed, $nd$ is even, and $G$ is the induced subgraph of
$G(n,d)$ on a fixed set of $\frac{n}{5d}$ vertices, then w.h.p. every
connected component of $G$ has order at most $2\log n$ and contains at most
one cycle.

###### Proof.

We first show that w.h.p. each component contains at most one cycle.

It is not difficult to show that any _minimal_ graph $H$ on $k$ vertices with
at least two cycles is formed from a path of length $k$ by adding edges from
each of its ends, see e.g. [27, Theorem 5.5]. Thus, there are at most
$k^{2}\cdot k!$ labelled graphs on $k$ vertices with this property. For a
fixed such $H$, we bound the probability it appears among $k$ fixed vertices
$v_{1},\ldots,v_{k}$ in the pairings model for $G(n,d)$. The total number of
pairings giving such an $H$ (without giving rise to multi-edges) can be
bounded above by

$d^{2(k+1)}\cdot P(nd-2(k+1)),$

since there are at most $(d^{2})^{k+1}$ ways to choose the edges between
$d$-sets that correspond to the $k+1$ edges of $H$, and then at most
$P(nd-2(k+1))$ ways to pair the remaining points. Let $\mathcal{E}$ be the
event that the pairings model generating a simple graph, which occurs with
probability $(1+o(1))e^{(1-d^{2})/4}$. We get that

$\displaystyle\Pr[\\{v_{1},\ldots,v_{k}\\}\text{ is a copy of
}H\mid\mathcal{E}]$
$\displaystyle\leq(1+o(1))e^{-(1-d^{2})/4}\cdot\frac{d^{2(k+1)}P(nd-2(k+1))}{P(nd)}$
$\displaystyle\leq(1+o(1))e^{-(1-d^{2})/4}\cdot\frac{d^{k+1}}{n^{k+1}}.$

Thus,

$\Pr[\text{some such }H\text{ appears in
}G]\leq(1+o(1))e^{-(1-d^{2})/4}\sum_{k\geq 4}\binom{n/(5d)}{k}k^{2}\cdot
k!\cdot\frac{d^{k+1}}{n^{k+1}}=o(1),$

which completes the proof that every component of $G$ contains at most one
cycle w.h.p.

Next, we show that w.h.p. every connected component has order at most $2\log
n$ with a similar computation. For a given set size $k$, the number of
labelled trees $H$ on $k$ vertices is $k^{k-2}$ by Cayley’s theorem. We bound
the probability that a fixed such $H$ appears among $k$ fixed vertices
$v_{1},\ldots,v_{k}$. Similarly to before, we obtain that the total number of
pairings giving such an $H$ without multi-edges is bounded above by

$d^{2(k-1)}\cdot P(nd-2(k-1)),$

since there are at most $(d^{2})^{k-1}$ ways to choose the edges between
$d$-sets that correspond to the $k-1$ edges of the tree $H$, and at most
$P(nd-2(k-1))$ ways to pair the remaining points. Conditioning on the pairings
model generating a simple graph, which occurs with probability
$(1+o(1))e^{(1-d^{2})/4}$, we get

$\displaystyle\Pr[\\{v_{1},\ldots,v_{k}\\}\text{ is a copy of
}H\mid\mathcal{E}]$
$\displaystyle\leq(1+o(1))e^{-(1-d^{2})/4}\cdot\frac{d^{2(k-1)}P(nd-2(k-1))}{P(nd)}$
$\displaystyle\leq(1+o(1))e^{-(1-d^{2})/4}\cdot\frac{d^{k-1}}{n^{k-1}}.$

Taking a union bound over all choices of $v_{1},\ldots,v_{k}$,

$\displaystyle\Pr[\text{a tree on }k\text{ vertices appears in }G]$
$\displaystyle\leq(1+o(1))e^{-(1-d^{2})/4}\binom{n/(5d)}{k}k^{k-2}\cdot\frac{d^{k-1}}{n^{k-1}}$
$\displaystyle\leq(1+o(1))e^{-(1-d^{2})/4}\frac{n^{k}\cdot k^{k-2}\cdot
d^{k-1}}{(5d)^{k}\cdot(k/e)^{k}\cdot n^{k-1}}$ $\displaystyle\leq
n\cdot(e/5+o(1))^{k},$

which is $o(1)$ for $k=2\log n$. This implies that w.h.p. every component of
$G$ has order at most $2\log n$, and completes the proof. ∎

We can now prove Theorem 1.3.

######  Corollary 4.7.

For any $d\geq 2$, we have that w.h.p.,
$\overrightarrow{r_{1}}(\overrightarrow{G}(n,d))\leq n(\log n)^{4\log d}$ as
$n\to\infty$.

###### Proof.

By Lemma 4.6, we know that w.h.p., any fixed $n/(5d)$ vertices of
$\overrightarrow{G}(n,d)$ span a disjoint union of trees and unicyclic
components, each of which has order at most $2\log n$. Therefore, by applying
the union bound to $5d$ events, we conclude that w.h.p.,
$\overrightarrow{G}(n,d)$ has a directed partition into $5d$ parts all with
this property. Dividing each part in two to split every cycle, we conclude
that w.h.p. $\overrightarrow{G}(n,d)$ has a $(10d,2\log n)$-forest partition.
Additionally, since the underlying undirected graph of
$\overrightarrow{G}(n,d)$ is $d$-regular, we see that
$\overrightarrow{G}(n,d)$ is $d$-degenerate and has maximum degree $d$. So by
Theorem 4.5, we conclude that w.h.p. as $n\to\infty$,

$\overrightarrow{r_{1}}(\overrightarrow{G}(n,d))\leq(10d^{2})^{6d(\log(10d))^{2}}(2\log
n)^{2\log(10d)}n,$

which is upper-bounded by $n(\log n)^{4\log d}$ for any fixed $d$ and
sufficiently large $n$. ∎

Let $\overrightarrow{G}(n,p)$ denote the orientation of the Erdős–Rényi random
graph $G(n,p)$ on vertex set $[n]$ where all edges are oriented to the right.
Similarly to the above, we can prove a nearly-linear upper bound on
$\overrightarrow{r_{1}}(\overrightarrow{G}(n,p))$.

######  Corollary 4.8.

For any $d\geq 2$, we have that w.h.p.,
$\overrightarrow{r_{1}}(\overrightarrow{G}(n,p))\leq n\cdot(\log n)^{O(d(\log
d)^{2})}$, where $p=d/n$.

###### Proof.

It is easy to show that if $p=d/n$, then $G(n,p)$ is $O(d)$-degenerate (see
[19, Theorem 4.8] for a proof of a stronger result). Additionally, it is well-
known that the maximum degree of $G(n,p)$ is $O(\log n/\log\log n)$ for any
fixed $d\geq 2$. Finally, by the easier version of Lemma 4.6 (e.g. [27,
Theorem 5.5]), we see that $\overrightarrow{G}(n,p)$ has a $(10d,2\log
n)$-forest partition. Hence, Theorem 4.5 implies that
$\overrightarrow{r_{1}}(\overrightarrow{G}(n,p))\leq n\cdot(\log n)^{O(d(\log
d)^{2})}$. ∎

##  5 Multiple colors and ordered Ramsey numbers

In this section we study oriented Ramsey numbers of more than one color,
proving Theorems 1.6 and 1.7.

We define an _ordered graph_ $G$ to be an undirected graph whose vertex set
comes with a total order. If the vertex set is a subset of $\mathbb{N}$, then
the total order is assumed to be that of $\mathbb{N}$. If $G_{1},\ldots,G_{k}$
are ordered graphs, then the _ordered Ramsey number_
$r_{<}(G_{1},\ldots,G_{k})$ is the minimum $N$ such that any edge-coloring of
the complete graph on $[N]$ in colors $1,\ldots,k$ contains a monochromatic
copy of $G_{i}$ in color $i$ for some $i$. Here an _ordered copy_ of $G_{i}$
is a subgraph isomorphic to $G_{i}$ with vertices appearing in the same order.
We write $r_{<}(G;k)\coloneqq r_{<}(G,\ldots,G)$ when all the graphs $G_{i}$
are the same.

###  5.1 The lower bound

To prove Theorem 1.6, we need the following theorem from Conlon, Fox, Lee, and
Sudakov [11, Theorem 2.3].

######  Theorem 5.1.

If $M$ is a random matching on vertex set $[n]$, then w.h.p.,

$r_{<}(M;2)>n^{\log n/20\log\log n}.$

We remark that the existence of ordered matchings $M$ with $r_{<}(M;2)>n^{\log
n/20\log\log n}$ was proven independently by Balko, Cibulka, Král, and Kynčl
[1]. We will only need this weaker result.

If $H$ is an acyclic digraph with a Hamiltonian (directed) path, we say $H$ is
_Hamiltonian_. It has a unique vertex ordering $v_{1},\ldots,v_{n}$ where
consecutive vertices are adjacent and all edges point forwards. We assign to
$H$ a natural ordered graph $H^{+}$ on $[n]$ where $i\sim j$ if and only if
$v_{i}\rightarrow v_{j}$ in $H$.

######  Lemma 5.2.

If $k\geq 1$ and $H$ is an acyclic Hamiltonian digraph, then

$\overrightarrow{r_{k}}(H)\geq r_{<}(H^{+};k).$

###### Proof.

If $N=r_{<}(H^{+};k)-1$, there exists a $k$-edge-coloring $\chi$ of the
complete graph on $[N]$ in which there is no monochromatic copy of $H^{+}$.
Let $T$ be the transitive tournament on $[N]$ with all edges oriented forwards
(i.e. $i\to j$ if and only if $i<j$), and the edge between $i\to j$ also
colored $\chi(i,j)$. Since $H$ has a Hamiltonian path and all edges in $T$
point forwards in $[N]$, any copy of $H$ in $T$ corresponds to an ordered copy
of $H^{+}$ in $\chi$. By construction, there is no monochromatic copy of $H$
in $T$, as desired. ∎

The two results above together can be used to prove Theorem 1.6.

###### Proof of Theorem 1.6.

Since $\overrightarrow{r_{k}}(H)$ is nondecreasing in $k$, it suffices to
prove the result for $k=2$. By Theorem 5.1, there exists a matching $M$ on
$[n]$ which satisfies $r_{<}(M;2)>n^{\log n/20\log\log n}$. Define $H$ to be
the acyclic digraph on $[n]$ where $i\rightarrow j$ if $i<j$ and either
$j=i+1$ or $(i,j)$ is an edge of $M$. By Lemma 5.2,
$\overrightarrow{r_{2}}(H)\geq r_{<}(H^{+};2)$. On the other hand, $M$ is a
ordered subgraph of $H^{+}$, so $r_{<}(H^{+};2)\geq r_{<}(M;2)$. It follows
that

$\overrightarrow{r_{2}}(H)\geq r_{<}(M;2)>n^{\log n/20\log\log n},$

as desired. Note that $H$ is the edge union of a path and a matching, so it
has maximum degree $3$. ∎

###  5.2 The upper bound

To prove Theorem 1.7, we upper bound $k$-color oriented Ramsey numbers by
$2k$-color ordered Ramsey numbers. Let $H^{-}$ be the ordered graph obtained
from $H^{+}$ by reversing the vertex order.

######  Lemma 5.3.

If $k\geq 1$ and $H$ is an acyclic digraph, then

$\overrightarrow{r_{k}}(H)\leq
r_{<}(\underbrace{H^{+},\ldots,H^{+}}_{k},\underbrace{H^{-},\ldots,H^{-}}_{k}).$

###### Proof.

Let $T$ be a tournament on

$N=r_{<}(\underbrace{H^{+},\ldots,H^{+}}_{k},\underbrace{H^{-},\ldots,H^{-}}_{k})$

vertices, with an edge-coloring $\chi$ using colors $1,\dotsc,k$. Arbitrarily
identify $V(T)$ with $[N]$ and define a $(2k)$-edge-coloring $\chi^{\prime}$
of $K_{N}$ by

$\chi^{\prime}(i,j)=\begin{cases}\chi(i,j)&\text{if }i<j\text{ and
}i\rightarrow j\\\ \chi(i,j)+k&\text{else}.\end{cases}$

By the definition of $N$, there is either some color $c\leq k$ where
$\chi^{\prime}$ has an ordered copy of $H^{+}$ in color $c$, or some color
$c>k$ where $\chi^{\prime}$ has an ordered copy of $H^{-}$ in $c$. In the
former case, $T$ contains a monochromatic copy of $H$ in color $c$ with all
vertices pointed forwards in the arbitrary ordering, and in the latter case
$T$ contains a monochromatic copy of $H$ in color $c-k$ with all edges pointed
backwards. In either case, $T$ contains a monochromatic copy of $H$, as
desired. ∎

To prove an upper bound on $\overrightarrow{r_{k}}(H)$, it remains to
generalize the following upper bound of [11] on $2$-color ordered Ramsey
numbers to more colors.

######  Theorem 5.4 ([11, Theorem 3.6]).

If $H$ is an ordered graph on at most $n$ vertices with degeneracy $d\geq 2$,
then

$r_{<}(H,K_{n})\leq 2^{O(d\log^{2}(2n/d))}.$

The multicolor bound can now be obtained by iterating the above theorem.

######  Theorem 5.5.

If $k,d\geq 2$ and $H_{1},\ldots,H_{k-1}$ are $d$-degenerate ordered graphs on
at most $n$ vertices, then

$r_{<}(H_{1},\ldots,H_{k-1},K_{n})\leq 2^{O_{k,d}(\log^{2^{k-1}}n)}.$

###### Proof.

We prove the theorem by induction on $k$. The base case $k=2$ is just Theorem
5.4. For the inductive step, note that if
$M=r_{<}(H_{2},\ldots,H_{k-1},K_{n})\leq 2^{O(\log^{2^{k-2}}n)}$ then one
obtains

$r_{<}(H_{1},H_{2},\ldots,H_{k-1},K_{n})\leq r_{<}(H_{1},K_{M}),$

by combining the last $k-1$ colors into one “super-color.” It follows by
applying the base case that

$r_{<}(H_{1},H_{2},\ldots,H_{k-1},K_{n})\leq r_{<}(H_{1},K_{M})\leq
2^{O(\log^{2}M)}\leq 2^{O(\log^{2^{k-1}}n)},$

as desired. ∎

Theorem 1.7 follows by combining Lemma 5.3 with Theorem 5.5.

##  6 Concluding Remarks

In this section we collect a few appealing open problems on the Ramsey numbers
of digraphs. For $k,\Delta\geq 1$ and $n>\Delta$, let $H_{k,n,\Delta}$ be an
acyclic digraph $H$ with $n$ vertices and maximum degree $\Delta$ maximizing
the value of $\overrightarrow{r_{k}}(H)$. Much of this paper was devoted to
understanding the growth rate of $\overrightarrow{r_{k}}(H_{k,n,\Delta})$ for
fixed $k$ and $\Delta$.

We first consider the one-color case. Theorem 1.2, Lemma 5.3, and Theorem 5.4
together show

$n^{\Omega(\Delta^{2/3}/\log^{5/3}\Delta)}\leq\overrightarrow{r_{1}}(H_{1,n,\Delta})\leq
2^{O(\Delta\log^{2}(2n/\Delta))}$ (6.1)

While we do not know whether the above Ramsey number grows polynomially or
super-polynomially in $n$ for $k=1$, we also showed that for $k\geq 2$ and
$\Delta\geq 3$, $\overrightarrow{r_{k}}(H_{k,n,\Delta})$ is at least
$n^{\Omega(\log n/\log\log n)}$. We conjecture that a super-polynomial growth
rate is also possible for $k=1$.

######  Conjecture 6.1.

There exists an absolute constant $\Delta$ such that

$\overrightarrow{r_{1}}(H_{1,n,\Delta})\geq n^{\omega(1)}.$

In the case of $k\geq 2$ colors, Theorems 1.6 and 1.7 together imply

$n^{\Omega(\log n/\log\log n)}\leq\overrightarrow{r_{k}}(H_{k,n,\Delta})\leq
2^{O(\log^{2^{2k-1}}n)}.$ (6.2)

It would be interesting to determine even the logarithmic order of
$\overrightarrow{r_{k}}(H_{k,n,\Delta})$.

######  Problem 6.2.

For any fixed $k\geq 1$ and $\Delta\geq 2$, determine the order of growth of
$\log\overrightarrow{r_{k}}(H_{k,n,\Delta})$.

To our knowledge, the only solved case of Problem 6.2 is $k=1$, $\Delta=2$.
Here, $H_{1,n,2}$ must be a disjoint union of arbitrarily oriented paths and
non-strongly oriented cycles (an acyclic $H$ cannot contain a strongly
oriented cycle). Thomason [37] proved that if $n$ is large enough,
$\overrightarrow{r_{1}}(C_{n})=n$ for any non-strongly oriented cycle $C_{n}$
on $n$ vertices, which can be used to show
$\overrightarrow{r_{1}}(H_{1,n,2})=n+O(1)$.

It would be interesting to improve either side of (6.2) substantially. We
tentatively conjecture that neither side is close to the truth, in the
following quantitative form.

######  Conjecture 6.3.

There exist $\Delta\geq 3$ and constants $c_{k}=\omega_{k}(1)$ and
$C_{k}=2^{o(k)}$ such that

$\Omega(\log^{c_{k}}n)\leq\log\overrightarrow{r_{k}}(H_{k,n,\Delta})\leq
O(\log^{C_{k}}n).$

In the one-color case, another open problem we find interesting is to
determine more precisely the Ramsey number of a sparse random digraph. Theorem
1.3 shows that for fixed $d$, the Ramsey number of $\overrightarrow{G}(n,d)$
is w.h.p. bounded above by $n(\log n)^{O_{d}(1)}$. We expect that the answer
is in fact linear.

######  Conjecture 6.4.

If $d\geq 2$ is fixed and $H=\overrightarrow{G}(n,d)$, then w.h.p.
$\overrightarrow{r_{1}}(H)=O_{d}(n).$

This would follow from our techniques if one could prove the following
strengthening of Lemma 3.3, in which the size of the $1$-dense pair depends
only on the maximum degree $\Delta$ (and not on the number $m$ of vertices).

######  Conjecture 6.5.

For every $\Delta\geq 1$, there exists $C_{\Delta}>0$ such that the following
holds. Let $H$ be a $1$-degenerate digraph with maximum degree $\Delta$ on $m$
vertices $v_{1},\ldots,v_{m}$, and let $T$ be an arbitrary tournament. If
there exist sets $U_{1},\ldots,U_{m}\subseteq V(T)$, each of size $M\geq
C_{\Delta}m$, such that there is no embedding $\phi:H\hookrightarrow T$
satisfying $\phi(v_{i})\in U_{i}$, then $T$ contains a $1$-dense pair with
size at least $M/C_{\Delta}$.

Indeed, if one could prove Conjecture 6.5, then it would imply that Lemma
3.10, Lemma 3.11, Theorem 3.13, and Theorem 4.5 would all no longer depend on
$m$, the maximum size of a tree component in a directed partition of $H$ into
oriented forests. In particular, this would imply Conjecture 6.4. Moreover, it
is entirely possible that Conjecture 6.5 could be proven using similar greedy
embedding arguments, since the conjecture is not hard to prove if the
injectivity constraint on $\phi$ is removed.

We would also like to highlight one powerful digraph embedding technique that
we have not used in this paper, but are hopeful can be incorporated into our
arguments to prove more general results. The median ordering of a tournament
$T$ is the vertex ordering $v_{1},\ldots,v_{n}$ maximizing the number of
forward edges. To see the power of the median ordering, note that
$v_{i}\rightarrow v_{i+1}$ for every $1\leq i\leq n-1$ in this ordering, so
this immediately exhibits a Hamiltonian path in $T$. Previous work showing
linear upper bounds on $\overrightarrow{r_{1}}(H)$ when $H$ is an oriented
tree (e.g. [16]) or an acyclic digraph of bounded bandwidth [14] all depend on
embedding $H$ into a tournament $T$ in some iterative manner according to its
median ordering. We were not able to reproduce these upper bounds using greedy
embedding arguments, which seem primarily suited for embedding digraphs $H$
without long paths.

Finally, we recall from the introduction the _directed Ramsey number_
$\overleftrightarrow{r_{k}}(H)$, which is defined as the least $N$ such that
every $k$-coloring of the edges of $\overleftrightarrow{K_{N}}$ contains a
monochromatic copy of $H$. It is easy to see that
$\overrightarrow{r_{k}}(H)\geq\overleftrightarrow{r_{k}}(H)$ for any $k$ and
any acyclic $H$. Indeed, if $N=\overrightarrow{r_{k}}(H)$, then given a
$k$-edge-coloring of $\overleftrightarrow{K_{N}}$, we may ignore one edge from
each anti-parallel pair to obtain a $k$-edge-colored $N$-vertex tournament,
which contains a monochromatic $H$. There is also an inequality in the other
direction, whose proof is identical to that given in Lemma 5.3, and which
states that
$\overrightarrow{r_{k}}(H)\leq\overleftrightarrow{r_{2k}}(H,\dots,H,H^{\prime},\dots,H^{\prime})$,
where there are $k$ copies of $H$ and $k$ of $H^{\prime}$, and $H^{\prime}$ is
obtained from $H$ by reversing all the edges. Thanks to these connections, one
can convert many of our results on oriented Ramsey numbers to results on
directed Ramsey numbers. For example, Theorem 1.7 immediately implies a quasi-
polynomial upper bound on $\overleftrightarrow{r_{k}}(H)$ for any bounded-
degree acyclic digraph $H$. In the other direction, since reversing the edges
of any interval mesh yields another interval mesh, Theorem 1.2 shows the
existence of a bounded-degree acyclic digraph $H$ with
$\overleftrightarrow{r_{2}}(H)$ which grows faster than any fixed polynomial
in the number of vertices of $H$. For $k\geq 4$ colors, we can similarly use
Theorem 1.6 to produce a bounded-degree acyclic digraph $H$ such that
$\overleftrightarrow{r_{k}}(H)$ grows super-polynomially. However, there is an
interesting intermediate case at $k=3$ colors, and we end with the following
conjecture, which may be easier than Conjecture 6.1.

######  Conjecture 6.6.

There is an absolute constant $\Delta$ and an infinite sequence $\\{H_{n}\\}$
of $n$-vertex acyclic digraphs with maximum degree at most $\Delta$ and
$\overleftrightarrow{r_{3}}(H_{n})\geq n^{\omega(1)}$.

Acknowledgments. We would like to thank Jasmine Yan for producing Figure 3.1,
and the anonymous referee for many helpful comments.

## References

  * [1] M. Balko, J. Cibulka, K. Král, and J. Kynčl, Ramsey numbers of ordered graphs, _Electron. J. Comb._ 27 (2020), P1.16.
  * [2] J.-C. Bermond, Some Ramsey numbers for directed graphs, _Discrete Math._ 9 (1974), 313–321.
  * [3] B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, _European J. Combin_. 1 (1980), 311–316.
  * [4] M. Bucić, S. Letzter, and B. Sudakov, Directed Ramsey number for trees, _J. Combin. Theory Ser. B_ 137 (2019), 145–177.
  * [5] S. A. Burr, An inequality involving the vertex arboricity and edge arboricity of a graph, _J. Graph Theory_ 10 (1986), 403–404.
  * [6] S. A. Burr and P. Erdős, On the magnitude of generalized Ramsey numbers for graphs, in: _Infinite and Finite Sets I_ , Colloq. Math. Soc Janos Bolyai 10, North-Holland, Amsterdam (1975), 214–240.
  * [7] V. Chvátal, Monochromatic paths in edge-colored graphs, _J. Combin. Theory Ser. B_ 13 (1972), 69–70.
  * [8] V. Chvátal, V. Rödl, E. Szemerédi and W. T. Trotter Jr., The Ramsey number of a graph with bounded maximum degree, _J. Combin. Theory Ser. B_ 34 (1983), 239–243.
  * [9] D. Conlon, A new upper bound for diagonal Ramsey numbers, _Ann. of Math._ 170 (2009), 941–960.
  * [10] D. Conlon, The Ramsey number of dense graphs, _Bull. Lond. Math. Soc._ 45 (2013), 483–496.
  * [11] D. Conlon, J. Fox, C. Lee, and B. Sudakov, Ordered Ramsey numbers,_J. Combin. Theory Ser. B_ 122 (2017), 353–383.
  * [12] D. Conlon, J. Fox, and B. Sudakov, Recent developments in graph Ramsey theory, _London Math. Soc. Lecture Note Ser._ 424 (2015), 49–118.
  * [13] D. Conlon, J. Fox, and B. Sudakov, Short proofs of some extremal results II, _J. Combin. Theory Ser. B_ 121 (2016), 173–196.
  * [14] N. Draganić, F. Dross, J. Fox, A. Girão, F. Havet, D. Korándi, W. Lochet, D. Munhá Correia, A. Scott, and B. Sudakov, Powers of paths in tournaments, Combin. Probab. Comput. 30 (2021), 894–898.
  * [15] F. Dross and F. Havet, On the unavoidability of oriented trees, _Electron. Notes Theor. Comput. Sci._ 346 (2019), 425–436.
  * [16] A. El Sahili, Trees in tournaments, _J. Combin. Theory Ser. B_ 92 (2004), 183–187.
  * [17] P. Erdős and A. Hajnal, Ramsey-type theorems, _Discrete Appl. Math._ 25 (1989), 37–52.
  * [18] P. Erdős and L. Moser, On the representation of directed graphs as unions of orderings, _Publ. Math. Inst. Hung. Acad. Sci., Ser. A_ 9 (1964), 125–132.
  * [19] J. Fox and B. Sudakov, Two remarks on the Burr–Erdős conjecture, _European J. Combin._ 30 (2009), 1630–1645.
  * [20] T. Gallai, On directed paths and circuits, _Theory of graphs (Proc. Colloq., Tihany, 1966)_ (1968), 115–118.
  * [21] R. L. Graham, V. Rödl, and A. Ruciński, On graphs with linear Ramsey numbers, _J. Graph Theory_ 35 (2000), 176–192.
  * [22] A. Gyárfás and J. Lehel, A Ramsey-type problem in directed and bipartite graphs, _Period. Math. Hungar._ 3 (1973), 299–304.
  * [23] R. Häggkvist and A. Thomason, Trees in tournaments, _Combinatorica_ 11 (1991), 123–130.
  * [24] M. Hasse, Zur algebraischen Begründung der Graphentheorie. I, _Mathematische Nachrichten_ 28 (1965), 275–290.
  * [25] F. Havet, Trees in tournaments, _Discr. Math._ 243 (2002), 121–134.
  * [26] F. Havet and S. Thomassé, Median orders of tournaments: A tool for the second neighborhood problem and Sumner’s conjecture, _J. Graph Theory_ 35 (2000), 244–256.
  * [27] S. Janson, T. Łuczak, and A. Ruciński, _Random graphs_ , Wiley, New York, 2000.
  * [28] A. Kostochka and B. Sudakov, On Ramsey numbers of sparse graphs, _Combin. Probab. Comput._ 12 (2003), 627–641.
  * [29] D. Kühn, R. Mycroft, and D. Osthus, A proof of Sumner’s universal tournament conjecture for large tournaments, _Proc. Lond. Math. Soc. (3)_ 102 (2011), 731–766.
  * [30] C. Lee, Ramsey numbers of degenerate graphs, _Ann. of Math._ 185 (2017), 791–829.
  * [31] L. Lovász, _Graphs and Geometry_ , American Mathematical Society Colloquium Publications, American Mathematical Society, Providence, RI, 2019.
  * [32] B. Roy, Nombre chromatique et plus longs chemins d’un graphe, _Rev. Française Informat. Recherche Opérationnelle_ 1 (1967), 129–132.
  * [33] A. Sah, Diagonal Ramsey via effective quasirandomness, 2020. Preprint available at arXiv:2005.09251.
  * [34] J. Spencer, Ramsey’s theorem—a new lower bound, _J. Combin. Theory Ser. A_ 18 (1975), 108–115.
  * [35] R. Stearns, The voting problem, _Amer. Math. Monthly_ 66 (1959), 761–763.
  * [36] B. Sudakov, A conjecture of Erdős on graph Ramsey numbers, _Adv. Math._ 227 (2011), 601–609.
  * [37] A. Thomason, Paths and cycles in tournaments, _Trans. Amer. Math. Soc._ 296 (1986), 167–180.
  * [38] L. M. Vitaver, Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix, _Dokl. Akad. Nauk SSSR_ 147 (1962), 728.
  * [39] N. C. Wormald, Models of random regular graphs. In _Surveys in combinatorics,_ 1999 (Canterbury), volume 267 of _London Math. Soc. Lecture Note Ser._ , pages 239–298. Cambridge Univ. Press, Cambridge, 1999.
  * [40] R. Yuster, Paths with many shortcuts in tournaments, _Discrete Math._ 334 (2021), 112–168.