# Path decompositions of random directed graphs

Alberto Espuny Díaz  Institut für Mathematik, Technische Universität Ilmenau,
98684 Ilmenau, Germany<EMAIL_ADDRESS>,  Viresh Patel
and  Fabian Stroh  Korteweg-de Vries Institute, Universiteit van Amsterdam,
1090 GE Amsterdam, The Netherlands<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We consider the problem of decomposing the edges of a directed graph into as
few paths as possible. There is a natural lower bound for the number of paths
needed in an edge decomposition of a directed graph $D$ in terms of its degree
sequence: this is given by the excess of $D$, which is the sum of
$|d^{+}(v)-d^{-}(v)|/2$ over all vertices $v$ of $D$ (here $d^{+}(v)$ and
$d^{-}(v)$ are, respectively, the out- and indegree of $v$).

A conjecture due to Alspach, Mason and Pullman from 1976 states that this
bound is correct for tournaments of even order. The conjecture was recently
resolved for large tournaments. Here we investigate to what extent the
conjecture holds for directed graphs in general. In particular, we prove that
the conjecture holds with high probability for the random directed graph
$D_{n,p}$ for a large range of $p$ (thus proving that it holds for most
directed graphs). To be more precise, we define a deterministic class of
directed graphs for which we can show the conjecture holds, and later show
that the random digraph belongs to this class with high probability. Our
techniques involve absorption and flows.

This project started during a research visit of the first author to the
Korteweg-de Vries Institute, which was partially funded by an LMS Early Career
Research Travel Grant (Ref ECR-1920-23) and the University of Birmingham. A.
Espuny Díaz has also received partial funding from the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (grant agreement no. 786198) and the Carl Zeiss Foundation. V. Patel
is supported by the Netherlands Organisation for Scientific Research (NWO)
through the Gravitation Programme Networks (024.002.003). F. Stroh is
supported by the NWO TOP grant (613.001.601).

##  1\. Introduction

An area of extremal combinatorics that has seen a lot of activity recently is
the study of decompositions of combinatorial structures. The prototypical
question in this area asks whether, for some given class $\mathcal{C}$ of
graphs, directed graphs, or hypergraphs, the edge set of each
$H\in\mathcal{C}$ can be decomposed into parts satisfying some given property.
When studying decompositions, one often wishes to minimise the number of
parts; e.g., in the case of edge colourings, determining the chromatic index
amounts to partitioning the edges of a graph into as few matchings as
possible. In this paper, we will be concerned with decomposing the edges of
directed graphs into as few (directed) paths as possible.

Let $D$ be a directed graph (or digraph for short) with vertex set $V(D)$ and
edge set $E(D)$. A path decomposition of $D$ is a collection of paths
$P_{1},\ldots,P_{k}$ of $D$ whose edge sets $E(P_{1}),\ldots,E(P_{k})$
partition $E(D)$. Given any directed graph $D$, it is natural to ask what the
minimum number of paths in a path decomposition of $D$ is. This is called the
_path number_ of $D$ and is denoted ${\mbox{\rm pn}}(D)$. A natural lower
bound on ${\mbox{\rm pn}}(D)$ is obtained by examining the degree sequence of
$D$. For each vertex $v\in V(D)$, write $d^{+}_{D}(v)$ (resp. $d_{D}^{-}(v)$)
for the number of edges exiting (resp. entering) $v$. The _excess_ at vertex
$v$ is defined to be ${\mbox{\rm ex}}_{D}(v)\coloneqq
d_{D}^{+}(v)-d_{D}^{-}(v)$. We note that, in any path decomposition of $D$, at
least $|{\mbox{\rm ex}}_{D}(v)|$ paths must start (resp. end) at $v$ if
${\mbox{\rm ex}}_{D}(v)\geq 0$ (resp. ${\mbox{\rm ex}}_{D}(v)\leq 0$).
Therefore, we have

${\mbox{\rm pn}}(D)\geq{\mbox{\rm ex}}(D)\coloneqq\frac{1}{2}\sum_{v\in
V(D)}|{\mbox{\rm ex}}_{D}(v)|,$

where ${\mbox{\rm ex}}(D)$ is called the _excess_ of $D$. Any digraph for
which equality holds above is called _consistent_. Clearly, not every digraph
is consistent; in particular, any Eulerian digraph $D$ has excess $0$ and so
cannot be consistent.

For the class of tournaments (that is, orientations of the complete graph),
Alspach, Mason, and Pullman [2] conjectured that every tournament with an even
number of vertices is consistent.

######  Conjecture 1.1.

Every tournament $T$ with an even number of vertices is consistent.

Many cases of this conjecture were resolved by the second author together with
Lo, Skokan, and Talbot [16], and the conjecture has very recently been
completely resolved (for sufficiently large tournaments) by Girão, Granet,
Kühn, Lo, and Osthus [7]. Both results relied on the robust expanders
technique, developed by Kühn and Osthus with several coauthors, which has been
instrumental in resolving several conjectures about edge decompositions of
graphs and directed graphs; see, e.g., [3, 14, 15].

The conjecture seems likely to hold for many digraphs other than tournaments:
indeed, the conjecture was stated only for even tournaments probably because
it considerably generalised the following conjecture of Kelly, which was wide
open at the time. Kelly’s conjecture states that every regular tournament has
a decomposition into Hamilton cycles. The solution of Kelly’s conjecture for
sufficiently large tournaments was one of the first applications of the robust
expanders technique [14].

A natural question then arises from 1.1: which directed graphs are consistent?
It is NP-complete to determine whether a digraph is consistent [18], and so we
should not expect to characterise consistent digraphs. Nonetheless, here we
begin to address this question by showing that the large majority of digraphs
are consistent. We consider the random digraph $D_{n,p}$, which is constructed
by taking $n$ isolated vertices and inserting each of the $n(n-1)$ possible
directed edges independently with probability $p$. Our main result is the
following theorem.

######  Theorem 1.2.

Let $\log^{4}n/n^{1/3}\leq p\leq 1-\log^{5/2}n/n^{1/5}$. Then, asymptotically
almost surely (a.a.s. for short)111That is, with probability tending to $1$ as
$n$ goes to infinity. $D_{n,p}$ is consistent.

Notice that some upper bound on $p$, as in the above theorem, is necessary
because, when $p=1$, we have that ${\mbox{\rm ex}}(D_{n,p})=0$ (with
probability $1$) and so $D_{n,p}$ cannot be consistent. Moreover the property
of being consistent is not a monotone property, that is, adding edges to a
consistent digraph does not imply the resulting digraph is consistent.
Therefore, unlike many other properties, we should not necessarily expect a
threshold for the consistency of random digraphs. We believe that the theorem
holds for much smaller (and larger) values of $p$, and perhaps even that no
lower bound on $p$ is necessary. For this reason, we have not tried to
optimise the polylogarithmic terms in our bounds on $p$.

It is interesting to compare Theorem 1.2 to the situation of the chromatic
index for random graphs. Recall that $\chi^{\prime}(G)$ (the chromatic index
of $G$) is the minimum number of matchings in an edge decompostion of a graph
$G$ into matchings, and that $\Delta(G)$ (the maximum degree of $G$) is an
obvious lower bound for this number (just as ${\mbox{\rm ex}}(D)$ is an
obvious lower bound for ${\mbox{\rm pn}}(D)$). Erdős and Wilson [4] showed
that a.a.s. the random graph $G=G_{n,p}$ satisfies
$\chi^{\prime}(G)=\Delta(G)$ for $p=1/2$. Frieze, Jackson, McDiarmid, and Reed
[6] extended this to all constant values of $p\in(0,1)$. Recently, this was
extended to all $p=o(n)$ by Haxell, Krivelevich, and Kronenberg [9]; this
might suggest that Theorem 1.2 could also hold with no lower bound on $p$.

The proof of Theorem 1.2 does not use randomness in a very significant way. In
fact, we give a set of sufficient conditions for a digraph to be consistent
and show that the random digraph (for suitable $p$) satisfies these conditions
with high probability. Here we give a simplified version of our main
deterministic result (see Theorem 4.3 for the full statement). For a digraph
$D$, a subset of vertices $S\subseteq V(D)$, and a vertex $v\in V(D)$, we
write $e_{D}(v,S)$ (resp. $e_{D}(S,v)$) for the number of outneighbours (resp.
inneighbours) of $v$ in $S$.

######  Theorem 1.3.

There exist constants $n_{0}$ and $c$ such that the following holds. Let
$D=(V,E)$ be a digraph on $n\geq n_{0}$ vertices. Set $t\coloneqq c(n\log
n)^{2/5}$ and let $A^{+}\coloneqq\\{v\in V:{\mbox{\rm ex}}_{D}(v)\geq t\\}$,
$A^{-}\coloneqq\\{v\in V:{\mbox{\rm ex}}_{D}(v)\leq-t\\}$, and $A^{0}\coloneqq
V\setminus(A^{+}\cup A^{-})$. Assume there is some $d\geq t$ such that

  1. $(\mathrm{i})$

for every $v\in A^{+}$ we have $d/4\leq e_{D}(v,A^{-})\leq d$,

  2. $(\mathrm{ii})$

for every $v\in A^{-}$ we have $d/4\leq e_{D}(A^{+},v)\leq d$,

  3. $(\mathrm{iii})$

for every $v\in A^{+}\cup A^{-}$ we have
$e_{D}(v,A^{0}),e_{D}(A^{0},v)\leq\min\\{d/3,t^{2}/10^{6}\\}$, and

  4. $(\mathrm{iv})$

for every $v\in A^{0}$ we have $e_{D}(A^{+},v),e_{D}(v,A^{-})\geq d/3$.

Then, $D$ is consistent.

Here is a concrete class of examples to which Theorem 1.3 applies. Take the
edge-disjoint union of $D=(V,E)$ and $D^{\prime}=(V,E^{\prime})$, where $D$ is
any digraph obtained by taking a regular bipartite graph of degree $t\geq
c(n\log n)^{2/5}$ and orienting all edges from one part to the other, and
$D^{\prime}$ is any Eulerian digraph of maximum degree at most $3t$. One can
easily check that Theorem 1.3 applies to such digraphs (here $A^{0}$ is
empty), and so such digraphs are consistent. Note therefore that Theorem 1.3
can be applied to many digraphs that are far from having any expansion or
pseudorandom properties; e.g., digraphs satisfying the conditions of Theorem
1.3 could easily be disconnected or weakly connected.

Broadly speaking, our proof relies on the use of the so-called absorption
technique, an idea due to Rödl, Ruciński, and Szemerédi [17] (with special
forms appearing in earlier work, e.g., [13]). We adapt and refine some of the
absorption ideas used in [16], but we also require several new ingredients. We
explain the main ideas of our proof in the next section. In contrast to the
previous work on this question [16, 7], our proof does not make use of robust
expanders. Preliminary ideas for this work came from de Vos [18].

The rest of this paper is organised as follows. We give a sketch of the proof
of Theorem 1.2 in Section 2. Section 3 is dedicated to giving common
definitions and citing results we use. In Section 4 we describe the _absorbing
structure_ and we show how to use it to decompose directed graphs $D$
satisfying certain properties into ${\mbox{\rm ex}}(D)$ paths. Finally, in
Section 5 we show that the random digraph contains the absorbing structure and
satisfies these properties with high probability. The proof of Theorem 1.2
appears in Section 5 and the proof of Theorem 1.3 appears in Section 4.

##  2\. Proof sketch

Let $D=D_{n,p}$ with $p$ as in Theorem 1.2. We divide the vertices of $D$ into
sets $A^{+}$, $A^{-}$ and $A^{0}$ depending on whether ${\mbox{\rm
ex}}_{D}(v)\geq t$, ${\mbox{\rm ex}}_{D}(v)\leq-t$, or $-t<{\mbox{\rm
ex}}_{D}(v)<t$, respectively, for a suitable choice of $t$ (as a function of
$n$ and $p$). One can show that, with high probability, $A^{+}$ and $A^{-}$
have roughly the same size and $A^{0}$ is small.

We start by setting aside an absorbing structure $\mathcal{A}$ which consists
of a set of edge-disjoint (short) paths of $D$. Each vertex $v\in V(D)$ will
have a set of paths $f(v)$ from $\mathcal{A}$ assigned to it, where the sets
$f(v)$ partition $\mathcal{A}$. In particular, for each $v\in A^{+}$ (resp.
$v\in A^{-}$), $f(v)$ consists of single-edge paths from $v$ to $A^{-}$ (resp.
$A^{+}$ to $v$) and, for each $v\in A^{0}$, $f(v)$ consists of a path with two
edges which goes from $A^{+}$ to $A^{-}$ through $v$. We think of
$\mathcal{A}$ interchangeably as a set of paths and as a digraph that is the
union of those paths. We will require that $|f(v)|$ is sufficiently large for
every vertex $v$ but at the same time that ${\mbox{\rm
ex}}_{\mathcal{A}}(v)\leq{\mbox{\rm ex}}_{D}(v)$ for every vertex $v$. We give
a set of conditions that ensure the existence of one such absorbing structure
in Definition 4.1 (see Lemmas 4.5 and 4.6), and Section 5 is devoted to
showing, by using concentration inequalities for martingales, that $D_{n,p}$
fulfils these conditions (with high probability) for all values of $p$ in the
desired range (and, in fact, for a slightly larger range than stated in
Theorem 1.2).

Next it is straightforward to obtain a set of edge-disjoint paths
$\mathcal{P}$ in $D\setminus E(\mathcal{A})$ such that
$|\mathcal{P}|+|\mathcal{A}|={\mbox{\rm ex}}(D)$, and such that, writing
$D^{\prime}\coloneqq D\setminus(E(\mathcal{A})\cup E(\mathcal{P}))$, we have
${\mbox{\rm ex}}(D^{\prime})=0$. So $\mathcal{P}\cup\mathcal{A}$ gives the
correct number (i.e., ${\mbox{\rm ex}}(D)$) of edge-disjoint paths but the
edges in $D^{\prime}$ are not covered, and moreover $D^{\prime}$ is Eulerian.
Our goal now is to slowly combine edges of $\mathcal{A}$ with edges of
$D^{\prime}$ to create longer paths in such a way that we maintain exactly
${\mbox{\rm ex}}(D)$ paths at every stage (_absorbing_ the edges of
$D^{\prime}$). If we manage to combine all the edges of $D^{\prime}$ in this
way, then we have decomposed $D$ into ${\mbox{\rm ex}}(D)$ paths, thus proving
that $D$ is consistent.

To begin the process of absorption, we apply a recent result of Knierim,
Larcher, Martinsson and Noever [12] (improving on an earlier result of Huang,
Ma, Shapira, Sudakov and Yuster [10]) which allows us to decompose the edges
of $D^{\prime}$ into $O(n\log n)$ cycles. The core idea then is to combine
certain paths from $\mathcal{A}$ with each cycle $C$ given by the
decomposition, and to decompose their union into paths; we refer to this as
_absorbing_ the cycle. Crucially, in order to keep the number of paths
invariant, we will combine each cycle $C$ with a set $\mathcal{A}_{C}$ of two
paths from $\mathcal{A}$ and decompose $C\cup\mathcal{A}_{C}$ into two paths,
as illustrated in Figure 1 (and thereafter, the edges $\mathcal{A}_{C}$ are no
longer available for use in absorbing other cycles).

Figure 1. Left: One example of absorbing a cycle using two absorbing paths. We
have $v_{1},v_{2}$ on our cycle $C$ with $v_{1}\in A^{+}$, $v_{2}\in A^{-}$.
We find paths $(v_{1},v_{1}^{\prime})\in f(v_{1})$ and
$(v_{2}^{\prime},v_{2})\in f(v_{2})$ with $v_{1}^{\prime}\in A^{-}\setminus
V(C)$ and $v_{2}^{\prime}\in A^{+}\setminus V(C)$.
Right: The solid red and dashed blue lines show the two new paths
$P_{1}\coloneqq v_{2}^{\prime}v_{2}Cv_{1}v_{1}^{\prime}$ and $P_{2}\coloneqq
v_{1}Cv_{2}$, which use all involved edges.
Note that under certain circumstances, if $v_{1}^{\prime},v_{2}^{\prime}$ lie
on $C$, we can still decompose all involved edges into two paths.

Therefore, we must allocate suitable absorbing paths to the cycles. The two
main challenges here are the following.

  1. (i)

The absorbing paths need to _fit_ the specific cycle, meaning they and the
cycle can be decomposed into two paths. Generally, given a cycle $C$, if we
can find vertices $v_{1},v_{2}\in V(C)\setminus A^{0}$ and paths $P_{1}\in
f(v_{1})$ and $P_{2}\in f(v_{2})$ where $P_{1}$ and $P_{2}$ have distinct
endpoints not on $C$, then $P_{1}$ and $P_{2}$ will fit $C$ (see Figure 1 for
an example). If both endpoints are on $C$, it is still sometimes possible (but
not always) that $P_{1}$ and $P_{2}$ fit $C$. If $v_{1}$ or $v_{2}$ lie in
$V(C)\cap A^{0}$, a similar idea can be used to find fitting paths.

  2. (ii)

We only have a limited number of absorbing paths available at each vertex.

In order to address (i), we prepare more absorbing paths than we plan to use,
as having the option to select from a sufficiently large number ensures that
at least two fit a given cycle. Any paths from $\mathcal{A}$ that we do not
end up using to absorb a cycle remain as paths in the final decomposition. In
order to address point (ii), we employ different strategies to assign
absorbing edges to cycles, depending on the number of vertices that the cycle
has in $A^{+}\cup A^{-}$.

For cycles $C$ that are long (meaning they have many vertices in $A^{+}\cup
A^{-}$), we greedily choose two paths that fit the cycle. This is possible as
each cycle contains a large number of vertices, so there are many choices for
the possible absorbing paths, and we can always find two that fit the cycle.
Here, we allow both endpoints of the paths to be on $C$.

For cycles of medium length, we use a flow problem to assign vertices to
cycles in such a way that each cycle is assigned a suitably large number of
vertices dependent on its length, but such that no vertex is assigned to too
many cycles. It turns out that this choice of assignment means we can find two
assigned vertices $v_{1}$ and $v_{2}$ per cycle and pick paths $P_{i}\in
f(v_{i})$ for $i=1,2$ that fit the cycle. This strategy is wasteful in the
sense that we sometimes assign more than two vertices to a cycle and thereby
reserve more absorbing paths than we use.

For cycles that are short, it is easier to find fitting paths, as we are
guaranteed to find absorbing paths that have their other endpoint off the
cycle, as in the example in Figure 1. However, it is harder to ensure that we
do not use too many paths per vertex. In this case, we also use a flow problem
to assign vertices to cycles, but we take multiple rounds and only decompose
certain “safe” cycles in each round. In addition, we absorb certain closed
walks in each round, so we need to apply the result by Knierim et al. between
rounds in order to re-decompose the remaining edges into cycles, and this may
generate new cycles which are long or of medium length. Absorbing the short
cycles is the most complicated process of the three, but it is the process we
apply first so that the long and medium cycles that are produced as a
byproduct can be absorbed by the appropriate processes described above. It is
also the only process in which we use the absorbing paths attached to vertices
in $A^{0}$.

##  3\. Preliminaries

###  3.1. Basic definitions and notation

For any $n\in\mathbb{Z}$, we will write $[n]\coloneqq\\{i\in\mathbb{Z}:1\leq
i\leq n\\}$ and $[n]_{0}\coloneqq\\{i\in\mathbb{Z}:0\leq i\leq n\\}$. Whenever
we write $a=b\pm c$ for any $a,b,c\in\mathbb{R}$, we mean that
$a\in[b-c,b+c]$. Given any set $X$, $2^{X}$ denotes the set of all subsets of
$X$. Our logarithms are always natural logarithms. We use the standard
$\mathcal{O}$-notation for asymptotic statements, where the asymptotics will
always be with respect to a parameter $n$. Throughout, we ignore rounding
whenever it does not affect our arguments.

In this paper, a _digraph_ $D=(V(D),E(D))$ is a loopless directed graph where,
for each pair of distinct vertices $x,y\in V(D)$, we allow up to two edges
between them, at most one in each direction. We usually denote edges $(x,y)\in
E(D)$ simply as $xy$. The _complement_ of $D$ is a digraph on the same vertex
set as $D$ which contains exactly all the edges which are not contained in
$D$. Given any digraph $D$, we write $H\subseteq D$ to mean that $H$ is a
_subdigraph_ of $D$, that is, $V(H)\subseteq V(D)$ and $E(H)\subseteq E(D)$.
If $\mathcal{H}$ is a set of subdigraphs of $D$, we will sometimes abuse
notation and treat $\mathcal{H}$ as the digraph obtained as the union of the
digraphs which comprise $\mathcal{H}$. In particular, we will write
$V(\mathcal{H})\coloneqq\bigcup_{H\in\mathcal{H}}V(H)$ and
$E(\mathcal{H})\coloneqq\bigcup_{H\in\mathcal{H}}E(H)$. Given any disjoint
sets $A,B\subseteq V(D)$, we denote $E_{D}(A)\coloneqq\\{ab\in E(D):a,b\in
A\\}$ and $E_{D}(A,B)\coloneqq\\{ab\in E(D):a\in A,b\in B\\}$. If one of the
sets consists of a single element (say, $A=\\{a\\}$), we will simplify the
notation by setting $E(a,B)\coloneqq E(\\{a\\},B)$, and similarly for the rest
of the notation. We will write $e_{D}(A)\coloneqq|E_{D}(A)|$ and
$e_{D}(A,B)\coloneqq|E_{D}(A,B)|$. We denote $D[A]\coloneqq(A,E_{D}(A))$ for
the subdigraph _induced_ by $A$ and, similarly, $D[A,B]\coloneqq(A\cup
B,E_{D}(A,B))$ for the bipartite subdigraph _induced_ by $(A,B)$. Given any
$E\subseteq E(D)$, we write $D\setminus E\coloneqq(V(D),E(D)\setminus E)$.
Given any vertex $x\in V(D)$, we define its _outneighbourhood_ and
_inneighbourhood_ as $N_{D}^{+}(x)\coloneqq\\{y\in V(D):xy\in E(D)\\}$ and
$N_{D}^{-}(x)\coloneqq\\{y\in V(D):yx\in E(D)\\}$, respectively. The
_outdegree_ and _indegree_ of $x$ are given by
$d_{D}^{+}(x)\coloneqq|N_{D}^{+}(x)|$ and
$d_{D}^{-}(x)\coloneqq|N_{D}^{-}(x)|$, respectively. Throughout, we may
sometimes abuse notation by referring to a digraph by its edge set, especially
in subscripts; the vertex set of such digraphs will always be clear from
context.

As in the introduction, we define the _excess_ at $x$ to be ${\mbox{\rm
ex}}_{D}(x)\coloneqq d_{D}^{+}(x)-d_{D}^{-}(x)$, and similarly define the
_positive excess_ and _negative excess_ at $x$ as ${\mbox{\rm
ex}}_{D}^{+}(x)\coloneqq\max\\{{\mbox{\rm ex}}_{D}(x),0\\}$ and ${\mbox{\rm
ex}}_{D}^{-}(x)\coloneqq\max\\{-{\mbox{\rm ex}}_{D}(x),0\\}$, respectively.
Observe that $\sum_{x\in V(D)}{\mbox{\rm ex}}_{D}(x)=0$. We define the
_excess_ of $D$ as

${\mbox{\rm ex}}(D)\coloneqq\sum_{x\in V(D)}{\mbox{\rm
ex}}_{D}^{+}(x)=\sum_{x\in V(D)}{\mbox{\rm
ex}}_{D}^{-}(x)=\frac{1}{2}\sum_{x\in V(D)}|{\mbox{\rm ex}}_{D}(x)|.$

When we refer to paths, cycles, and walks in digraphs, we mean _directed_
paths, cycles, and walks, i.e., the edges are oriented consistently. Given a
digraph $D$, a _walk_ $W$ in $D$ is given by a sequence of (not necessarily
distinct) vertices $W=v_{1}v_{2}\cdots v_{k}$ where
$v_{1}v_{2},v_{2}v_{3},\ldots,v_{k-1}v_{k}$ are distinct edges of $D$. We also
think of $W$ as being a subdigraph of $D$ with vertex set
$\\{v_{1},\ldots,v_{k}\\}$ and edge set
$\\{v_{1}v_{2},v_{2}v_{3},\ldots,v_{k-1}v_{k}\\}$. We also call $W$ a
$(v_{1},v_{k})$-walk and sometimes denote it by $v_{1}Wv_{k}$ to emphasise
that it starts at $v_{1}$ and ends at $v_{k}$, and we say $W$ is _closed_ if
$v_{1}=v_{k}$. For two edge-disjoint walks $W_{1}=aW_{1}b=av_{1}\cdots v_{k}b$
and $W_{2}=bW_{2}c=bv_{1}^{\prime}\cdots v_{\ell}^{\prime}c$, we write
$W_{1}W_{2}=av_{1}\cdots v_{k}bv_{1}^{\prime}\cdots v_{\ell}^{\prime}c$ for
the concatenation of $W_{1}$ and $W_{2}$. This notation extends in the natural
way for concatenating more than two walks. For a walk $W=v_{1}\cdots v_{k}$,
and $1\leq i<j\leq k$, we write $v_{i}Wv_{j}$ for the $(v_{i},v_{j})$-walk
$v_{i}v_{i+1}\cdots v_{j}$ between $v_{i}$ and $v_{j}$.

In fact, we will mostly be concerned with paths and cycles rather than walks.
A walk $W=v_{1}\cdots v_{k}$ is a _path_ if $v_{1},\ldots,v_{k}$ are distinct
vertices, and it is a _cycle_ if $v_{1},\ldots,v_{k}$ are distinct except that
$v_{1}=v_{k}$. The length of a walk, path, or cycle is the number of edges it
contains. We sometimes also consider degenerate single-vertex paths. Note
that, if $P_{1}$ is an $(a,b)$-path and $P_{2}$ is a $(b,c)$-path, where
$P_{1}$ and $P_{2}$ are vertex-disjoint except at $b$, then $P_{1}P_{2}$ is an
$(a,c)$-path. For sets of vertices $X$ and $Y$, we say that a path $P$ is an
$(X,Y)$-path if it starts in $X$ and ends in $Y$.

In this paper, we say a digraph $D$ is _Eulerian_ if
$d^{+}_{D}(v)=d^{-}_{D}(v)$ for every $v\in V(D)$ or, equivalently, if
${\mbox{\rm ex}}(D)=0$.222This is different from the standard definition,
which also asks that $D$ is strongly connected. A well-known consequence of
this definition is the fact that the edge set of any Eulerian digraph can be
decomposed into cycles.

We will sometimes need to consider a _multidigraph_ $D$, which is allowed to
have multiple edges between any two vertices, in both directions (but it is
still loopless). Whenever $D$ is a multidigraph, all edge sets should be seen
as multisets, while all vertex sets will remain simple sets. The notation and
terminology above extend in the natural way to multidigraphs.

###  3.2. Path and cycle decompositions

The following definitions are convenient.

######  Definition 3.1.

A _perfect decomposition_ of a digraph $D$ is a set
$\mathcal{P}=\\{P_{1},\ldots,P_{r}\\}$ of edge-disjoint paths of $D$ that
together cover $E(D)$ with $r={\mbox{\rm ex}}(D)$. (Thus, a digraph $D$ is
consistent if and only if it has a perfect decomposition.)

We will need the following basic facts.

######  Proposition 3.2.

Let $D$ be a digraph with ${\mbox{\rm ex}}(D)>0$. Then, there exists a path in
$D$ from a vertex of positive excess to a vertex of negative excess.

###### Proof.

First, repeatedly remove cycles from $D$ until this is no longer possible and
call the resulting digraph $D^{\prime}$; note that this does not affect the
excess of any vertex. Now any maximal path $P$ in $D^{\prime}$ starts at a
vertex that has no inneighbours (so it has positive excess) and ends at a
vertex that has no outneighbours (so it has negative excess). ∎

######  Proposition 3.3.

Suppose $D$ is a digraph, and let $X,Y\subseteq V(D)$ be disjoint. If
$P_{1},\ldots,P_{k}$ are edge-disjoint $(X,Y)$-paths and
$E(P_{1})\cup\ldots\cup E(P_{k})=E(D)$, then $\\{P_{1},\ldots,P_{k}\\}$ is a
perfect decomposition of $D$.

###### Proof.

If we construct $D$ by adding the $k$ paths one at a time, we notice that the
excess increases by one every time a path is added, so that ${\mbox{\rm
ex}}(D)=k$. ∎

As mentioned in Section 2, we will use “absorbing structures” (see Definition
4.4) to absorb Eulerian digraphs. For this, we will first decompose the
Eulerian digraphs into cycles. We will use the following theorem of Knierim,
Larcher, Martinsson and Noever [12] to achieve this.

######  Theorem 3.4.

There exists a constant $c^{\prime}$ such that every Eulerian digraph $D$ on
$n$ vertices can be decomposed into at most $c^{\prime}n\log n$ edge-disjoint
cycles.333In fact, the result of Knierim, Larcher, Martinsson and Noever [12]
is slightly stronger, in the sense that $\log n$ can be replaced by
$\log\Delta$, where $\Delta$ is the maximum (out- or in-)degree of $D$.

###  3.3. Flows

We recall some common definitions and facts about flow networks. We note that
flows are only used in the proofs of Lemmas 4.11 and 4.14.

A _flow network_ is a tuple $(F,w,s,t)$, where $F=(V,E)$ is a digraph,
$w\colon E\to\mathbb{R}$ is the _capacity_ function, and $s\in V$ is a
_source_ (i.e., it only has outedges incident to it) and $t\in V$ is a _sink_
(i.e., it only has inedges incident to it). A _flow_ for the flow network
$(F,w,s,t)$ is a function $\phi\colon E\to\mathbb{R}^{+}$ such that, for all
$e\in E$, we have $\phi(e)\leq w(e)$ and, for all $v\in V\setminus\\{s,t\\}$,
we have $\sum_{u\in N^{-}_{F}(v)}\phi(uv)=\sum_{u\in N^{+}_{F}(v)}\phi(vu)$.
We define the _value_ of $\phi$ as $val(\phi)\coloneqq\sum_{v\in
N^{+}_{F}(s)}\phi(sv)$. A _maximum flow_ on a given flow network is a flow
$\phi$ that maximises $val(\phi)$.

A partition $(U,W)$ of $V$ with $s\in U$, $t\in W$ is called a _cut_ , and we
call the edge set $E_{F}(U,W)$ its corresponding _cut-set_. The _capacity_
$w((U,W))$ of a cut $(U,W)$ is the sum of the capacities of the edges of its
cut-set, i.e., $w((U,W))\coloneqq w(E_{F}(U,W))\coloneqq\sum_{e\in
E_{F}(U,W)}w(e)$. A _minimum cut_ of the given flow network is a cut of
minimum capacity. We make use of the following well-known theorem.

######  Theorem 3.5 (Max-flow min-cut [5]).

For every flow network with maximum flow $\phi$ and minimum cut $(U,W)$ we
have that $\mathit{val}(\phi)=\mathit{w}((U,W))$.

An easy fact states that, if all edge capacities are integers, then there
exists a maximum flow such that all flow values are integers.

Given a flow $\phi$ on a flow network $(F,w,s,t)$, we define the _residual
digraph_ $G_{\phi}$ of $G$ under $\phi$ as a directed graph with vertex set
$V$ and edge set $\\{uv\in E:\phi(uv)<w(uv)\\}\cup\\{vu:uv\in
E,\;\phi(uv)>0\\}$. An $(s,t)$-path in a residual graph $G_{\phi}$ is called
an _augmenting path_ , and it is easy to see that an augmenting path exists in
$G_{\phi}$ if and only if $\phi$ is not a maximum flow.

###  3.4. Random digraphs and probabilistic estimates

In Section 5, we begin working with random digraphs in the binomial model
(although we also introduce slight variants of this model in the proofs of
Lemmas 4.5 and 4.6). We denote by $D_{n,p}$ a random digraph on vertex set
$[n]$ obtained by adding each of the possible $n^{2}-n$ edges with probability
$p$, independently of all other edges. Most of our results will be asymptotic
in nature. In particular, given a (di)graph property $\mathcal{P}$ and a
sequence of random (di)graphs $\\{G_{i}\\}_{i>0}$ with $|V(G_{i})|\to\infty$
as $i\to\infty$, we say that $G_{i}$ satisfies $\mathcal{P}$ _asymptotically
almost surely_ (a.a.s.) if $\mathbb{P}[G_{i}\in\mathcal{P}]\to 1$ as
$i\to\infty$.

We will need to prove concentration results for different random variables.
For this, we will often use Chernoff bounds (see, e.g., the book of Janson,
Łuczak and Ruciński [11, Corollary 2.3]).

######  Lemma 3.6.

Let $X$ be the sum of $n$ mutually independent Bernoulli random variables, and
let $\mu\coloneqq\mathbb{E}[X]$. Then, for all $\delta\in(0,1)$ we have that
$\mathbb{P}[X\geq(1+\delta)\mu]\leq e^{-\delta^{2}\mu/3}$ and
$\mathbb{P}[X\leq(1-\delta)\mu]\leq e^{-\delta^{2}\mu/2}$. In particular,
$\mathbb{P}[|X-\mu|\geq\delta\mu]\leq 2e^{-\delta^{2}\mu/3}$.

The following Chernoff-type bound extends Lemma 3.6 to allow us to deal with
large deviations (see, e.g., the book of Alon and Spencer [1, Theorem
A.1.12]).

######  Lemma 3.7.

Let $X$ be the sum of $n$ mutually independent Bernoulli random variables. Let
$\mu\coloneqq\mathbb{E}[X]$, and let $\beta>1$. Then,
$\mathbb{P}[X\geq\beta\mu]\leq\left(e/\beta\right)^{\beta\mu}$.

We will sometimes deal with random variables which are not independent, in
which case we cannot obtain concentration results as above. To deal with them,
we will need the following version of the well-known Azuma-Hoeffding
inequality (see, e.g., [11, Theorem 2.25]). Given any sequence of random
variables $X=(X_{1},\ldots,X_{n})$ taking values in a set $\Omega$ and a
function $f\colon\Omega^{n}\to\mathbb{R}$, for each $i\in[n]_{0}$ define
$Y_{i}\coloneqq\mathbb{E}[f(X)\mid X_{1},\ldots,X_{i}]$. The sequence
$Y_{0},\ldots,Y_{n}$ is called the _Doob martingale_ for $f$ and $X$. All the
martingales that appear in this paper will be of this form.

######  Lemma 3.8 (Azuma’s inequality).

Let $Y_{0},\ldots,Y_{n}$ be a martingale and suppose $|Y_{i}-Y_{i-1}|\leq
c_{i}$ for all $i\in[n]$. Then, for any $t>0$,

$\mathbb{P}[|Y_{n}-Y_{0}|\geq t]\leq
2\exp\left(\frac{-t^{2}}{2\sum_{i=1}^{n}c_{i}^{2}}\right).$

We will also make use of the following well-known inequality; see, e.g., [8,
Theorem 368].

######  Lemma 3.9 (rearrangement inequality).

Let $n\in\mathbb{N}$, and let $x_{1}\leq\ldots\leq x_{n}$ and
$y_{1}\leq\ldots\leq y_{n}$ be real numbers. Let $\sigma\in\mathfrak{S}_{n}$
be an arbitrary permutation. Then,

$\sum_{i=1}^{n}x_{i}y_{n+1-i}\leq\sum_{i=1}^{n}x_{i}y_{\sigma(i)}\leq\sum_{i=1}^{n}x_{i}y_{i}.$

##  4\. Optimal path decompositions of digraphs

In this section we give sufficient conditions for a digraph to be consistent.
These conditions will ensure that our digraph has a certain absorbing
structure, and the absorbing structure will help us to decompose $D$ into
${\mbox{\rm ex}}(D)$ paths.

We begin by defining the classes of digraphs we will be working with
throughout the rest of the paper.

######  Definition 4.1.

Fix $p\in[0,1]$ and $0\leq\lambda,\kappa\leq n$. We say that $D=(V,E)$ is an
_$(n,p,\kappa,\lambda)$ -digraph_ if $|V|=n$ and the vertex set $V$ can be
partitioned into three parts, $A^{+}$, $A^{-}$ and $A^{0}$ (where $A^{0}$ may
be empty), in such a way that the following properties are satisfied:

  1. $(\mathrm{P}1)$

For every $v\in A^{+}$ we have ${\mbox{\rm ex}}_{D}(v)\geq 155\kappa$ and
$np/4\leq e_{D}(v,A^{-})\leq np$.

  2. $(\mathrm{P}2)$

For every $v\in A^{-}$ we have ${\mbox{\rm ex}}_{D}(v)\leq-155\kappa$ and
$np/4\leq e_{D}(A^{+},v)\leq np$.

  3. $(\mathrm{P}3)$

For every $v\in A^{+}\cup A^{-}$ we have
$e_{D}(v,A^{0}),e_{D}(A^{0},v)\leq\lambda$.

  4. $(\mathrm{P}4)$

For every $v\in A^{0}$ we have $e_{D}(A^{+},v)\geq np/3$ and
$e_{D}(v,A^{-})\geq np/3$.

We say that $D$ is an _$(n,p,\kappa,\lambda)$ -pseudorandom digraph_ if it is
an $(n,p,\kappa,\lambda)$-digraph and, additionally, the following property
holds:

  1. $(\mathrm{P}5)$

For every set $U\subseteq V$ with $|U|\geq\log n/(50p)$ we have $e_{D}(U)\leq
100|U|^{2}p$.

Whenever we are given an $(n,p,\kappa,\lambda)$-digraph, we implicitly
consider a partition of its vertex set into sets $A^{+}$, $A^{-}$ and $A^{0}$
which satisfy the properties described in Definition 4.1. This partition is
not necessarily unique; throughout this section, we simply assume that one
such partition is given. We will write $\dot{A}\coloneqq A^{+}\cup A^{-}$.

######  Remark 4.2.

If $D$ is an $(n,p,\kappa,\lambda)$-(pseudorandom) digraph and
$\kappa^{\prime}\leq\kappa$ and $\lambda^{\prime}\geq\lambda$, then $D$ is an
$(n,p,\kappa^{\prime},\lambda^{\prime})$-(pseudorandom) digraph.

We will see in Section 5 that a.a.s. $D_{n,p}$ is an
$(n,p,\kappa,\lambda)$-pseudorandom digraph, for a suitable choice of
parameters. Our goal in this section is to prove the following theorem.

######  Theorem 4.3.

There exists $n_{0}\in\mathbb{N}$ with the following property. Suppose
$n\in\mathbb{N}$, $p\in(0,1)$ and $\kappa,\lambda\in\mathbb{R}$ are parameters
satisfying $n\geq n_{0}$ and

  1. $(\mathrm{C}1)$

$\kappa=3N^{2/5}$,

  2. $(\mathrm{C}2)$

$np\geq 365N^{2/5}$, and

  3. $(\mathrm{C}3)$

$\lambda=\min\\{{np}/{3},{\kappa^{2}}/{12}\\}$,

where $N\coloneqq c^{\prime}n\log n$ and $c^{\prime}$ is the constant from
Theorem 3.4. Then, any $(n,p,\kappa,\lambda)$-digraph $D$ admits a perfect
decomposition.

The same conclusion holds if $D$ is an $(n,p,\kappa,\lambda)$-pseudorandom
digraph and $(\mathrm{C}1)$ and $(\mathrm{C}2)$ are replaced by

  1. $(\mathrm{C}^{\prime}1)$

$\kappa=6(N^{2}p)^{1/5}$, and

  2. $(\mathrm{C}^{\prime}2)$

$p\geq n^{-1/3}\log^{4}n$.

Observe that, by Remark 4.2, we can extend Theorem 4.3 to any
$(n,p,\kappa,\lambda)$-(pseudorandom) digraph where $\kappa$ is larger than
the value given in $(\mathrm{C}1)$ or $(\mathrm{C}^{\prime}1)$, respectively,
and $\lambda$ is smaller than the value given in $(\mathrm{C}3)$.

We further remark that the constants in Theorem 4.3 as well as in Definition
4.1 are not optimal. In fact, there is a trade-off between some of them: by
making one worse, others can be improved. In order to ease readability, we
refrain from stating the most general result possible, and simply note that a
host of similar statements, with different constants, can be obtained by going
through the proofs of the lemmas in this section. Furthermore, we note that
some of the conditions in Definition 4.1 can be relaxed; in particular,
$(\mathrm{P}3)$ is only used in the proof of Lemma 4.11, where only one of the
two bounds stated in $(\mathrm{P}3)$ is required. Thus, as long as all
vertices in $A^{+}\cup A^{-}$ satisfy one (and the same) of the two bounds,
Theorem 4.3 still holds, so it can be applied to a larger class of digraphs
than stated in Definition 4.1.

Assuming Theorem 4.3, we give the proof of Theorem 1.3.

###### Proof of Theorem 1.3.

We set $n_{0}$ as in Theorem 4.3 and $c\coloneqq 500{(c^{\prime})}^{2/5}$,
where $c^{\prime}$ is the constant from Theorem 3.4. Then, properties
$(\mathrm{i})$–$(\mathrm{iv})$ of Theorem 1.3 and our choice of $A^{+},A^{-}$
and $A^{0}$ correspond to $(\mathrm{P}1)$–$(\mathrm{P}4)$ with $t\coloneqq
c(n\log n)^{2/5}$, $d$, and $\min\\{d/3,t^{2}/10^{6}\\}$ playing the roles of
$155\kappa$, $np$, and $\lambda$, respectively, so $D$ is an
$(n,p,\kappa,\lambda)$-digraph. By Remark 4.2 and our choice of $t$ and $d$,
we then conclude that $D$ is also an
$(n,p,\kappa^{\prime},\lambda^{\prime})$-digraph which satisfies properties
$(\mathrm{C}1)$–$(\mathrm{C}3)$ of Theorem 4.3. Thus, we may apply Theorem 4.3
and $D$ is consistent. ∎

###  4.1. Finding absorbing structures

The next definition describes the absorbing structure that we will find in
$(n,p,\kappa,\lambda)$-digraphs $D$. It will be used to absorb the majority of
edges of $D$ into a set of $(A^{+},A^{-})$-paths that will end up being part
of our perfect decomposition. We will essentially show that, when we take an
edge-disjoint union of our absorbing structure with any Eulerian subdigraph of
$D$, the resulting digraph has a perfect decomposition.

######  Definition 4.4.

Let $D$ be an $(n,p,\kappa,\lambda)$-digraph, and let $Z\subseteq V(D)$ and
$t\in\mathbb{N}$. A _$(Z,t)$ -absorbing structure_ is a pair
$\mathcal{A}=(E^{\mathrm{ab}},f)$, where $E^{\mathrm{ab}}\subseteq E(D)$ and
$f\colon Z\to 2^{E^{\mathrm{ab}}}$, such that

  1. $(\mathrm{A}1)$

if $z\in Z\cap A^{+}$, then $f(z)$ contains exactly $t$ edges from
$E_{D}(z,A^{-})$;

  2. $(\mathrm{A}2)$

if $z\in Z\cap A^{-}$, then $f(z)$ contains exactly $t$ edges from
$E_{D}(A^{+},z)$;

  3. $(\mathrm{A}3)$

if $z\in Z\cap A^{0}$, then $f(z)$ contains exactly $t$ edges from
$E_{D}(A^{+},z)$ and exactly $t$ edges from $E_{D}(A^{+},z)$, and

  4. $(\mathrm{A}4)$

the collection $\\{f(z)\\}_{z\in Z}$ is a partition of $E^{\mathrm{ab}}$; in
particular, the sets $f(z)$ are disjoint.

Note that, for convenience, for $z\in A^{+}\cup A^{-}$, we often think of the
$t$ edges in $f(z)$ as $t$ edge-disjoint $(A^{+},A^{-})$-paths of length $1$.
For $z\in A^{0}$, we arbitrarily pair up the in- and outedges in $f(z)$ to
create $t$ edge-disjoint $(A^{+},A^{-})$-paths of length $2$ through $z$.

The following lemmas show the existence of absorbing structures in
$(n,p,\kappa,\lambda)$ digraphs.

######  Lemma 4.5.

Let $D$ be an $(n,p,\kappa,\lambda)$-digraph with $100\log n<\kappa\leq
np/120$. Then, $D$ contains an $(\dot{A},12\kappa)$-absorbing structure which
contains at most $150\kappa$ edges incident to each $v\in\dot{A}$.

###### Proof.

Consider $D[A^{+},A^{-}]$. We define a random subdigraph $D_{q}$ of
$D[A^{+},A^{-}]$ by including each of the edges of $E_{D}(A^{+},A^{-})$ with
probability $q\coloneqq 120\kappa/(np)$, independently of each other. For each
$v\in A^{+}$, let $\mathcal{B}_{v}$ be the event that
$d^{+}_{D_{q}}(v)\notin[25\kappa,150\kappa]$. Similarly, for each $v\in
A^{-}$, let $\mathcal{B}_{v}$ be the event that
$d^{-}_{D_{q}}(v)\notin[25\kappa,150\kappa]$. By $(\mathrm{P}1)$,
$(\mathrm{P}2)$ and Lemma 3.6, it follows that, for each $v\in\dot{A}$,
$\mathbb{P}[\mathcal{B}_{v}]\leq e^{-\kappa/50}$. Then, by a union bound over
all $v\in\dot{A}$ and the lower bound on $\kappa$, we conclude that there
exists a digraph $D^{\prime}\subseteq D[A^{+},A^{-}]$ such that, for each
$v\in A^{+}$, $d^{+}_{D^{\prime}}(v)\in[25\kappa,150\kappa]$, and for each
$v\in A^{-}$, $d^{-}_{D^{\prime}}(v)\in[25\kappa,150\kappa]$.

We are now going to randomly split the edges of $D^{\prime}$ into two sets
$E^{+}$ and $E^{-}$, and then prove that, with positive probability, $E^{+}$
contains an $(A^{+},12\kappa)$-absorbing structure $\mathcal{A}^{+}$, and
$E^{-}$ contains an $(A^{-},12\kappa)$-absorbing structure $\mathcal{A}^{-}$.
It then immediately follows that $\mathcal{A}^{+}\cup\mathcal{A}^{-}$ is the
desired $(\dot{A},12\kappa)$-absorbing structure.

For each $e\in E(D^{\prime})$, with probability $1/2$ and independently of all
other edges, we assign $e$ to $E^{+}$, and otherwise we assign it to $E^{-}$.
Let $D^{+}\coloneqq(\dot{A},E^{+})$ and $D^{-}\coloneqq(\dot{A},E^{-})$ (so,
in particular, $D^{\prime}=D^{+}\cup D^{-}$). Now, for each $v\in A^{+}$, let
$\mathcal{B}_{v}^{\prime}$ be the event that $d^{+}_{D^{+}}(v)<12\kappa$, and
for each $v\in A^{-}$, let $\mathcal{B}_{v}^{\prime}$ be the event that
$d^{-}_{D^{-}}(v)<12\kappa$. In particular, by Lemma 3.6, it follows that, for
each $v\in\dot{A}$, $\mathbb{P}[\mathcal{B}_{v}^{\prime}]\leq
e^{-\kappa/100}$. By a union bound, we conclude that there exists a partition
of $E(D^{\prime})$ into $E^{+}$ and $E^{-}$ such that, for each $v\in A^{+}$,
we have $d^{+}_{D^{+}}(v)\geq 12\kappa$, and for each $v\in A^{-}$ we have
$d^{-}_{D^{-}}(v)\geq 12\kappa$.

In order to obtain the desired absorbing structure, for each $v\in A^{+}$ let
$f(v)$ be an arbitrary set of $12\kappa$ of the edges of $E^{+}$ which contain
$v$, and for each $v\in A^{-}$ let $f(v)$ be an arbitrary set of $12\kappa$ of
the edges of $E^{-}$ which contain $v$. ∎

######  Lemma 4.6.

Let $D$ be an $(n,p,\kappa,\lambda)$-digraph with $8\log(4n)<\kappa\leq
np/12$, $\lambda\leq np/3$ and $\kappa\lambda\geq 4np\log(2n)$. Then, $D$
contains an $(A^{0},3\kappa)$-absorbing structure which contains at most
$5\kappa$ edges incident to each $v\in\dot{A}$.

###### Proof.

Let $D^{\prime}\coloneqq D[A^{+},A^{0}]\cup D[A^{0},A^{-}]$, and let $D_{q}$
be a random subdigraph of $D^{\prime}$ obtained by adding each edge of
$D^{\prime}$ with probability $q\coloneqq 12\kappa/(np)$ and independently of
each other. For each $v\in A^{+}$, let $\mathcal{B}_{v}$ be the event that
$d^{+}_{D_{q}}(v)>5\kappa$. Similarly, for each $v\in A^{-}$, let
$\mathcal{B}_{v}$ be the event that $d^{-}_{D_{q}}(v)>5\kappa$. Finally, for
each $v\in A^{0}$, let $\mathcal{B}_{v}^{+}$ and $\mathcal{B}_{v}^{-}$ be the
events that $d^{-}_{D_{q}}(v)<3\kappa$ and $d^{+}_{D_{q}}(v)<3\kappa$,
respectively.

It follows from $(\mathrm{P}3)$ and Lemma 3.6 that, for each $v\in\dot{A}$, we
have $\mathbb{P}[\mathcal{B}_{v}]\leq e^{-{\kappa\lambda}/{(4np)}}$.
Similarly, by $(\mathrm{P}4)$ and Lemma 3.6, for each $v\in A^{0}$ we have
that $\mathbb{P}[\mathcal{B}_{v}^{+}],\mathbb{P}[\mathcal{B}_{v}^{-}]\leq
e^{-\kappa/8}$. By a union bound, we conclude that there exists
$D^{*}\subseteq D^{\prime}$ such that, for each $v\in A^{+}$, we have
$d^{+}_{D_{q}}(v)\leq 5\kappa$; for each $v\in A^{-}$, we have
$d^{-}_{D_{q}}(v)\leq 5\kappa$, and for each $v\in A^{0}$, we have
$d^{+}_{D_{q}}(v),d^{-}_{D_{q}}(v)\geq 3\kappa$.

In order to obtain the absorbing structure, for each $v\in A^{0}$, let $f(v)$
be the union of an arbitrary subset of $E_{D^{*}}(A^{+},v)$ of size $3\kappa$
and an arbitrary subset of $E_{D^{*}}(v,A^{-})$ of size $3\kappa$. ∎

###  4.2. Using absorbing structures

In this subsection, we show how to use absorbing structures to obtain perfect
decompositions, and we use this to prove Theorem 4.3. As mentioned earlier,
the idea will be to use these absorbing structures to absorb Eulerian
digraphs. The Eulerian digraphs will be decomposed into cycles, using Theorem
3.4, and absorbed one cycle at a time.

Given an $(n,p,\kappa,\lambda)$-digraph $D$, we set $N\coloneqq
c^{\prime}n\log n$, where $c^{\prime}$ is the constant given by Theorem 3.4,
so any Eulerian subdigraph of $D$ can be decomposed into at most $N$ cycles.
We call a cycle $C\subseteq D$ _short_ if $|V(C)\cap\dot{A}|\leq\kappa$,
_long_ if $|V(C)\cap\dot{A}|\geq N/\kappa$, and _medium_ otherwise. We will
need a different strategy to absorb the set of cycles of each type. We will
show how to absorb long, medium and short cycles in Lemmas 4.9, 4.11 and 4.14,
respectively.

The following lemma shows how to absorb a single long or medium cycle, under
suitable conditions, and will be used in Lemmas 4.9 and 4.11.

######  Lemma 4.7.

Let $D$ be an $(n,p,\kappa,\lambda)$-digraph. Let $C\subseteq D$ be a cycle
with $\ell\coloneqq|V(C)\cap\dot{A}|>\kappa$ and $S\subseteq V(C)\cap\dot{A}$
with $|S|\geq\ell/\kappa+1$. Let $\mathcal{A}=(E^{\mathrm{ab}},f)$ be an
$(S,\kappa+2)$-absorbing structure such that $E(C)\cap
E^{\mathrm{ab}}=\varnothing$. Then, there exist distinct vertices
$v_{1},v_{2}\in S$ and edges $e_{1}\in f(v_{1})$ and $e_{2}\in f(v_{2})$ such
that $E(C)\cup\\{e_{1},e_{2}\\}$ can be decomposed into two
$(A^{+},A^{-})$-paths.

###### Proof.

Assume first that there are two distinct vertices $v_{1},v_{2}\in S$ such
that, for each $i\in[2]$, there is an edge $e_{i}\in f(v_{i})$ whose other
vertex is not contained in $V(C)$. Observe that the definition of
$\mathcal{A}$ ensures that $e_{1}\cup e_{2}$ is not a path of length $2$. Now,
for each $i\in[2]$, if $e_{i}=v_{i}x_{i}$, let $P_{i}^{+}\coloneqq v_{i}x_{i}$
and $P_{i}^{-}\coloneqq v_{i}$, and if $e_{i}=x_{i}v_{i}$, let
$P_{i}^{+}\coloneqq v_{i}$ and $P_{i}^{-}\coloneqq x_{i}v_{i}$. Let $P$ be the
$(v_{1},v_{2})$-subpath of $C$, and let $P^{\prime}$ be the
$(v_{2},v_{1})$-subpath of $C$. The paths described in the statement are now
given by $P_{1}\coloneqq P_{1}^{-}PP_{2}^{+}$ and $P_{2}\coloneqq
P_{2}^{-}P^{\prime}P_{1}^{+}$. Since $e_{1}\cup e_{2}$ is not a path of length
$2$, these two structures must indeed be paths and in all cases they are
$(A^{+},A^{-})$-paths since the paths have the same start- and endpoints as
$e_{1}$ and $e_{2}$. See Figure 2 for a visual representation of two of the
four possible outcomes.

$v_{1}$$v_{2}$$e_{1}$$e_{2}$

$v_{1}$$v_{2}$$e_{1}$$e_{2}$

Figure 2. A representation of the path decomposition of a cycle and two edges
as proposed in Lemma 4.7, in the case where we can find said edges with their
endpoints outside $V(C)$.

Therefore, we may assume that there are at least ${\ell}/{\kappa}>1$ vertices
$v\in S$ such that all $e\in f(v)$ have both endpoints in $V(C)$. Let us
denote the set of these vertices by $S^{\prime}$. For each $v\in S^{\prime}$,
let $P_{v}$ be the shortest subpath of $C$ which does not contain $v$ and
contains all other endpoints of the edges $e\in f(v)$ (recall that all said
endpoints lie in $\dot{A}$). In particular,
$|V(P_{v})\cap\dot{A}|\geq\kappa+2$. Now label the vertices of
$V(C)\cap\dot{A}$ as $y_{1},\ldots,y_{\ell}$ in such a way that, when
traversing $C$, they are visited in this (cyclic) order. A simple counting
argument shows the following.

######  Claim 4.8.

There exist two distinct vertices $v_{1},v_{2}\in S^{\prime}$ such that
$P_{v_{1}}$ and $P_{v_{2}}$ share at least two consecutive vertices of
$V(C)\cap\dot{A}$.

###### Proof.

Assume the statement does not hold. Then, any two paths from $\\{P_{v}:v\in
S^{\prime}\\}$ can intersect only at their endpoints, and any vertex of
$V(C)\cap\dot{A}$ can be an endpoint of at most two paths. This means that

$\sum_{v\in S^{\prime}}|V(P_{v})\cap\dot{A}|\leq\ell+|S^{\prime}|.$

However, using the bounds we have obtained so far, we can confirm that

$\sum_{v\in
S^{\prime}}|V(P_{v})\cap\dot{A}|\geq|S^{\prime}|(\kappa+2)\geq\ell+2|S^{\prime}|>\ell+|S^{\prime}|.\qed$

By 4.8, we can choose two edges $e_{1}\in f(v_{1})$ and $e_{2}\in f(v_{2})$
which form a “crossing configuration”, that is, such that the vertices of
$e_{1}$ and $e_{2}$ alternate when traversing $C$ (e.g., $wy$ and $zx$ are
crossing edges in Figure 3). In order to complete the proof, label the
vertices of $e_{1}$ and $e_{2}$ as $w,x,y,z$ in such a way that, when
traversing the cycle, they appear in this (cyclic) order and such that the
edges are oriented towards $x$ and towards $y$, respectively (note that in any
crossing configuration there exist two consecutive vertices into which the
edges are directed). The two paths of the statement are now given by
$P_{1}\coloneqq wyCzx$ and $P_{2}\coloneqq zCy$, and these are
$(A^{+},A^{-})$-paths since they have the same start- and endpoints as $e_{1}$
and $e_{2}$. See Figure 3 for a visual representation.

$z$$y$$w$$x$ Figure 3. A representation of the path decomposition of a cycle
and two edges as proposed in Lemma 4.7, in the case where we can find a
“crossing configuration”.

∎

We now prove Lemma 4.9, which shows how an absorbing structure can be used to
absorb a collection of long cycles.

######  Lemma 4.9.

Let $D$ be an $(n,p,\kappa,\lambda)$-digraph with $10\leq\kappa<N^{1/2}$. Let
$\mathcal{C}_{1}$ be a collection of edge-disjoint cycles in $D$ with
$|\mathcal{C}_{1}|\leq 2N$ and such that, for each $C\in\mathcal{C}_{1}$, we
have $|V(C)\cap\dot{A}|\geq N/\kappa$. Let $\mathcal{A}=(E^{\mathrm{ab}},f)$
be an $(\dot{A},7\kappa-1)$-absorbing structure with $E(\mathcal{C}_{1})\cap
E^{\mathrm{ab}}=\varnothing$. Then, the digraph with edge set
$E(\mathcal{C}_{1})\cup E^{\mathrm{ab}}$ has a perfect decomposition in which
each path is an $(A^{+},A^{-})$-path.

###### Proof.

For each $C\in\mathcal{C}_{1}$, we are going to use Lemma 4.7 to find two
edges $e_{1},e_{2}\in E^{\mathrm{ab}}$ such that $E(C)\cup\\{e_{1},e_{2}\\}$
can be decomposed into two $(A^{+},A^{-})$-paths. We proceed iteratively as
follows.

Assume that, for some of the cycles in $\mathcal{C}_{1}$, we have already
found two edges as described above, and we now wish to do this for the next
cycle $C\in\mathcal{C}_{1}$. Let $\ell\coloneqq|V(C)\cap\dot{A}|\geq
N/\kappa$. We say that an edge $e\in E^{\mathrm{ab}}$ is _available_ if it has
not been used to absorb any of the earlier cycles. We say that a vertex $v\in
V(C)\cap\dot{A}$ is _available_ if at least $\kappa+2$ edges of $f(v)$ are
available, and we say that it is _unavailable_ otherwise. Let $S_{C}\subseteq
V(C)\cap\dot{A}$ be the set of available vertices. Then, we can define an
$(S_{C},\kappa+2)$-absorbing structure $\mathcal{A}_{C}$ using edges from
$E^{\mathrm{ab}}$ by selecting, for each $v\in S_{C}$, any set of $\kappa+2$
available edges from $f(v)$.

Note that the total number of edges assigned to cycles so far is at most
$2|\mathcal{C}_{1}|\leq 4N$. On the other hand, for each $v\in
V(C)\cap\dot{A}$ which is unavailable, at least $5\kappa$ edges of $f(v)$ have
already been assigned to cycles. Therefore, the total number of unavailable
vertices is at most $4N/(5\kappa)$, so
$|S_{C}|\geq\ell-4N/(5\kappa)\geq\ell/5\geq\ell/\kappa+1$. Therefore (noting
that $\ell\geq N/\kappa>\kappa$), we can apply Lemma 4.7 (with $S_{C}$ and
$\mathcal{A}_{C}$ playing the roles of $S$ and $\mathcal{A}$, respectively) to
obtain two (available) edges $e_{1},e_{2}\in E^{\mathrm{ab}}$ such that
$E(C)\cup\\{e_{1},e_{2}\\}$ can be decomposed into two $(A^{+},A^{-})$-paths.

After each cycle has been handled in this way and, together with two edges,
decomposed into two $(A^{+},A^{-})$-paths, we are left with some edges in
$E^{\mathrm{ab}}$, which we treat as $(A^{+},A^{-})$-paths. We therefore have
a decomposition of $E(\mathcal{C}_{1})\cup E^{\mathrm{ab}}$ into
$(A^{+},A^{-})$-paths, which is a perfect decomposition by Proposition 3.3. ∎

We will use flow problems in order to prove Lemmas 4.11 and 4.14. All our flow
problems will follow a similar structure, so we introduce the following
definition in addition to the common definitions given in Section 3.3.

######  Definition 4.10.

Let $D$ be a multidigraph and $\mathcal{C}$ be a set of edge-disjoint cycles
of $D$. Set $B\coloneqq V(\mathcal{C})$. We define a flow network $(F,w,s,t)$
as follows. We define a digraph $F=F(\mathcal{C})$ on vertex set
$\\{s\\}\mathbin{\dot{\cup}}\mathcal{C}\mathbin{\dot{\cup}}B\mathbin{\dot{\cup}}\\{t\\}$,
where $s$ and $t$ are the source and sink of the flow problem, respectively.
We set $E_{1}\coloneqq\\{sC:C\in\mathcal{C}\\}$,
$E_{2}\coloneqq\\{Cb:C\in\mathcal{C},b\in V(C)\\}$, $E_{3}\coloneqq\\{bt:b\in
B\\}$ and $E(F)\coloneqq E_{1}\cup E_{2}\cup E_{3}$. Given any two functions
$g\colon\mathcal{C}\to\mathbb{R}$ and $h\colon B\to\mathbb{R}$, we will write
$\mathit{FP}(\mathcal{C};g,h)$ to denote the maximum flow problem on the
digraph $F=F(\mathcal{C})$ defined above where each edge $sC\in E_{1}$ has
capacity $w(sC)=g(C)$, each edge $Cb\in E_{2}$ has capacity $w(Cb)=1$, and
each edge $bt\in E_{3}$ has capacity $w(bt)=h(b)$. If $g$ or $h$ are constant
functions, we will simply replace them by the corresponding constant in the
notation.

The following lemma shows how an absorbing structure can be used to absorb a
collection of medium cycles.

######  Lemma 4.11.

Let $D$ be an $(n,p,\kappa,\lambda)$-digraph $D$ with
$\kappa\geq\max\\{12,(12\lambda)^{1/2},(72N^{2})^{1/5}\\}$, or an
$(n,p,\kappa,\lambda)$-pseudorandom digraph $D$ with
$\kappa\geq\max\\{12,(12\lambda)^{1/2},(7200N^{2}p)^{1/5},\sqrt{12/(25p)}\log
n\\}$. Let $\mathcal{C}_{2}$ be a collection of at most $2N$ edge-disjoint
cycles in $D$ such that, for each $C\in\mathcal{C}_{2}$, we have

$\kappa<|V(C)\cap\dot{A}|<N/\kappa.$ (4.1)

Let $\mathcal{A}=(E^{\mathrm{ab}},f)$ be an $(\dot{A},2\kappa+1)$-absorbing
structure with $E(\mathcal{C}_{2})\cap E^{\mathrm{ab}}=\varnothing$. Then, the
digraph with edge set $E(\mathcal{C}_{2})\cup E^{\mathrm{ab}}$ has a perfect
decomposition in which each path is an $(A^{+},A^{-})$-path.

###### Proof.

Given any digraph $H$ with $V(H)\subseteq V(D)$, let
$g(H)\coloneqq\lceil{|V(H)\cap\dot{A}|}/\kappa\rceil+1$. We use a flow problem
to assign, to each $C\in\mathcal{C}_{2}$, a set of $g(C)$ vertices of
$V(C)\cap\dot{A}$ in such a way that no vertex is assigned to more than
$\kappa$ cycles. We will then use Lemma 4.7 to find two edges in
$E^{\mathrm{ab}}$ with which to absorb $C$. To this end, we construct a
multiset of auxiliary cycles $\mathcal{C}_{2}^{\prime}$ as follows. We obtain
$\mathcal{C}_{2}^{\prime}$ from $\mathcal{C}_{2}$ by replacing each cycle
$C\in\mathcal{C}_{2}$ by the auxiliary cycle $i(C)$ with vertices
$V(C)\setminus A^{0}$ and whose cyclic vertex order is inherited from $C$.
Note that the cycles in $\mathcal{C}_{2}^{\prime}$ are not necessarily cycles
of $D$ and, indeed, the set $E(\mathcal{C}_{2}^{\prime})$ (which forms a
multidigraph) includes all the edges of $E(\mathcal{C}_{2})$ inside $\dot{A}$
as well as an extra edge every time a cycle in $\mathcal{C}_{2}$ leaves and
reenters $\dot{A}$. We note for later that, since $e_{D}(v,A^{0})\leq\lambda$
by $(\mathrm{P}3)$, the number of these extra edges contained in any
$T\subseteq\dot{A}$ is at most $\lambda|T|$. Consider
$\mathit{FP}(\mathcal{C}^{\prime}_{2};g,\kappa)$.

######  Claim 4.12.

$\mathit{FP}(\mathcal{C}^{\prime}_{2};g,\kappa)$ has a flow $\phi$ with
$\mathit{val}(\phi)=\sum_{C\in\mathcal{C}^{\prime}_{2}}g(C)$.

###### Proof.

Throughout this proof we use the notation set up in Definition 4.10 and
Section 3.3. As $M_{0}\coloneqq\\{sC:C\in\mathcal{C}^{\prime}_{2}\\}$ is the
cut-set of a cut of $F=F(\mathcal{C}_{2}^{\prime})$ of capacity
$\sum_{C\in\mathcal{C}^{\prime}_{2}}g(C)$, by Theorem 3.5 it remains to show
that this is a minimum cut. We assume the existence of a cut-set $M$ of $F$
with smaller capacity and will show that this contradicts our assumption on
the value of $\kappa$. Let $T\subseteq
V(\mathcal{C}_{2}^{\prime})\subseteq\dot{A}$ be the set of vertices that are
separated from $t$ by $M$ and $T^{\prime}\coloneqq
V(\mathcal{C}_{2}^{\prime})\setminus T$. Let
$S\subseteq\mathcal{C}^{\prime}_{2}$ be the set of cycles which are not
separated from $s$ by $M$, and
$S^{\prime}\coloneqq\mathcal{C}_{2}^{\prime}\setminus S$. These sets are
illustrated in Figure 4.

Figure 4. The graph $F(\mathcal{C}^{\prime}_{2})$. The thick dotted line
illustrates the cut-set $M_{0}$. The regular thick line illustrates the cut-
set $M$.

Let $D_{S}$ be the multidigraph that is the union of the cycles in $S$. We
have that

$w(M)=\sum_{C\in
S^{\prime}}g(C)+e_{F}(S,T^{\prime})+|T|\kappa<\sum_{C\in\mathcal{C}_{2}^{\prime}}g(C)=w(M_{0}),$

which is equivalent to

$\sum_{C\in S}g(C)>e_{F}(S,T^{\prime})+|T|\kappa.$ (4.2)

(Note that we may assume $T\neq\varnothing$, as otherwise (4.2) cannot hold.)
Now observe that

$\sum_{C\in S}g(C)=\sum_{C\in
S}\left(\left\lceil\frac{|V(C)|}{\kappa}\right\rceil+1\right)<\frac{e(D_{S})}{\kappa}+2|S|.$
(4.3)

By (4.1), we have $|V(C)|>\kappa$ for all $C\in\mathcal{C}_{2}^{\prime}$, so
it follows that

$|S|<\sum_{C\in S}|V(C)|/\kappa=e(D_{S})/\kappa.$ (4.4)

Combining (4.2), (4.3) and (4.4), it follows that

$\frac{3e(D_{S})}{\kappa}>e_{F}(S,T^{\prime})+|T|\kappa.$ (4.5)

Next, since $|V(C)|\leq N/\kappa$ for all $C\in\mathcal{C}_{2}^{\prime}$ by
(4.1) and $|\mathcal{C}_{2}^{\prime}|=|\mathcal{C}_{2}|\leq 2N$, we have

$e(D_{S})<2N^{2}/\kappa,$ (4.6)

Furthermore, since
$e(D_{S})=e_{D_{S}}(T)+e_{D_{S}}(T^{\prime})+e_{D_{S}}(T^{\prime},T)+e_{D_{S}}(T,T^{\prime})$,
we have

$\displaystyle e_{F}(S,T^{\prime})$ $\displaystyle=\sum_{v\in
T^{\prime}}\frac{1}{2}(d^{+}_{D_{S}}(v)+d^{-}_{D_{S}}(v))$
$\displaystyle\geq\frac{1}{2}(e_{D_{S}}(T^{\prime})+e_{D_{S}}(T^{\prime},T)+e_{D_{S}}(T,T^{\prime}))=\frac{1}{2}(e({D_{S}})-e_{D_{S}}(T)).$

Combining this with (4.5), we have

$\frac{6e({D_{S}})}{\kappa}>2e_{F}(S,T^{\prime})\geq e({D_{S}})-e_{D_{S}}(T),$

which implies

$e_{D_{S}}(T)\geq\left(1-\frac{6}{\kappa}\right)e({D_{S}})\geq\frac{1}{2}e({D_{S}}).$
(4.7)

By the discussion before the claim concerning the construction of
$\mathcal{C}_{2}^{\prime}$, we have $e_{D_{S}}(T)\leq e_{D}(T)+\lambda|T|$.
This implies that either $e_{D_{S}}(T)\leq 2e_{D}(T)$ or $e_{D_{S}}(T)\leq
2\lambda|T|$. If $e_{D_{S}}(T)\leq 2\lambda|T|$, then using (4.7) we obtain
that $|T|\geq e(D_{S})/(4\lambda)$, and combining this with (4.5) we have

$\frac{3e(D_{S})}{\kappa}>|T|\kappa\geq\frac{\kappa e(D_{S})}{4\lambda},$

so that $\kappa^{2}<12\lambda$, contradicting our choice of $\kappa$.
Therefore, we may assume

$e_{D_{S}}(T)\leq 2e_{D}(T).$ (4.8)

Now we distinguish between the two cases in the statement of the lemma, i.e.,
when $D$ is an $(n,p,\kappa,\lambda)$-digraph and when $D$ is an
$(n,p,\kappa,\lambda)$-pseudorandom digraph.

Case 1: $D$ is an $(n,p,\kappa,\lambda)$-digraph. By (4.8) we have
$e_{D_{S}}(T)\leq 2e_{D}(T)\leq 2|T|^{2}$. Combined with (4.7), we conclude
that $|T|\geq\sqrt{e(D_{S})/4}$. By (4.5), we have

$\frac{3e(D_{S})}{\kappa}>|T|\kappa\geq\kappa\sqrt{e(D_{S})/4}$

Combining this with (4.6), we obtain that

$2N^{2}/\kappa>e(D_{S})>\kappa^{4}/36,$

contradicting our choice of $\kappa\geq(72N^{2})^{1/5}$.

Case 2: $D$ is an $(n,p,\kappa,\lambda)$-pseudorandom digraph. We further
split this into two cases. Assume first that $|T|\geq\log n/(50p)$, so by
$(\mathrm{P}5)$ and (4.8) we have that $e_{D_{S}}(T)\leq 2e_{D}(T)\leq
200|T|^{2}p$. Combined with (4.7), we have that
$|T|\geq\sqrt{e(D_{S})/(400p)}$. By (4.5), we have

$\frac{3e(D_{S})}{\kappa}>|T|\kappa\geq\kappa\sqrt{e(D_{S})/(400p)}$

Combining this with (4.6), we obtain that

$2N^{2}/\kappa>e(D_{S})>\kappa^{4}/(3600p),$

contradicting our choice of $\kappa\geq(7200N^{2}p)^{1/5}$.

We may thus assume that $|T|<\log n/(50p)$. In this case, we may consider any
superset of $T$ of size $\log n/(50p)$ and, by applying $(\mathrm{P}5)$ to
this superset and considering (4.8), we have that $e_{D_{S}}(T)\leq
2e_{D}(T)\leq 2\log^{2}n/(25p)$. Then, by (4.7),

$e(D_{S})\leq 4\log^{2}n/(25p).$

Now, using (4.5) and the fact that $T\neq\varnothing$, we also have that

$e(D_{S})>|T|\kappa^{2}/3\geq\kappa^{2}/3.$

But these two bounds on $e(D_{S})$ lead to a contradiction on our choice of
$\kappa\geq\sqrt{12/(25p)}\log n$. ∎

We interpret the flow given by 4.12 as follows. As all capacities are
integers, there exists an integer flow with value
$\sum_{C\in\mathcal{C}^{\prime}_{2}}g(C)$, so assume $\phi$ is such an integer
flow. For each cycle $C\in\mathcal{C}_{2}$, writing $C^{\prime}=i(C)$, let
$V_{C}\coloneqq\\{v\in V(C^{\prime})\subseteq V(C):\phi(C^{\prime}v)=1\\}$ be
the vertices assigned to $C$. As $\phi$ saturates all edges $sC^{\prime}$, we
have $|V_{C}|=g(C^{\prime})=g(C)$. The capacity $\kappa$ of the edges $vt$
with $v\in\dot{A}$ ensures that no vertex is assigned to more than $\kappa$
cycles of $\mathcal{C}_{2}$.

We will now iteratively assign two edges $e_{1},e_{2}$ to each cycle
$C\in\mathcal{C}_{2}$ so that $E(C)\cup\\{e_{1},e_{2}\\}$ can be decomposed
into two $(A^{+},A^{-})$-paths, where $e_{1}\in f(v_{1})$, $e_{2}\in f(v_{2})$
and $v_{1},v_{2}\in V_{C}$. We do this as follows using Lemma 4.7. Assume
that, for some of the cycles in $\mathcal{C}_{2}$, we have already found two
edges as described above, and assume that we next want to do this for
$C\in\mathcal{C}_{2}$. We say that an edge $e\in E^{\mathrm{ab}}$ is
_available_ if it has not been assigned to any of the previous cycles. Then,
for each $v\in V_{C}$, the number of edges $e\in f(v)$ that are available is
at least $\kappa+2$ (since no vertex is assigned to more than $\kappa$ cycles
and $\mathcal{A}=(E^{\mathrm{ab}},f)$ is an $(\dot{A},2\kappa+1)$-absorbing
structure). Thus, we may define a $(V_{C},\kappa+2)$-absorbing structure
$\mathcal{A}_{C}$ using available edges from $E^{\mathrm{ab}}$ by selecting,
for each $v\in V_{C}$, any set of $\kappa+2$ available edges at $v$. Then,
with $V_{C}$ and $\mathcal{A}_{C}$ playing the roles of $S$ and $\mathcal{A}$,
respectively, Lemma 4.7 gives two edges $e_{1}\in f(v_{1})$ and $e_{2}\in
f(v_{2})$ with $v_{1},v_{2}\in V_{C}$ such that $E(C)\cup\\{e_{1},e_{2}\\}$
can be decomposed into two $(A^{+},A^{-})$-paths. After repeating this for
every cycle $C\in\mathcal{C}_{2}$ and treating each of the remaining edges in
$E^{\mathrm{ab}}$ as an $(A^{+},A^{-})$-path, we have an edge decomposition of
$E(\mathcal{C}_{2})\cup E^{\mathrm{ab}}$ into $(A^{+},A^{-})$-paths, which is
a perfect decomposition by Proposition 3.3. ∎

We have seen earlier in Lemma 4.7 how a single long or medium cycle can be
absorbed using an absorbing structure. The following lemma shows how to absorb
a single short cycle using our absorbing structure. In fact, it is slightly
more general: it shows how to absorb a short Eulerian digraph, namely one that
is the union of two short edge-disjoint paths. Another difference is that now
we must work with vertices in $A^{0}$. As before, in order to absorb a cycle
$C$, we take two suitable vertices $v_{1},v_{2}\in V(C)$. For long and medium
cycles, both $v_{1}$ and $v_{2}$ had been in $\dot{A}$, and we used a single
edge in $f(v_{1})$ and a single edge in $f(v_{2})$ for absorption. For short
cycles, if $v_{1},v_{2}\in\dot{A}$, we do the same, but here one or both may
be in $A^{0}$. If, for instance, $v_{1}\in A^{0}$, we use a pair of edges from
$f(v_{1})$ (which should be thought of as an $(A^{+},A^{-})$-path of length
two through $v_{1}$) for absorption.

######  Lemma 4.13.

Let $D$ be a $(n,p,\kappa,\lambda)$-digraph and $v_{1},v_{2}\in V(D)$. Let
$P_{1}\subseteq D$ be a $(v_{1},v_{2})$-path and $P_{2}\subseteq D$ be a
$(v_{2},v_{1})$-path which are edge-disjoint. Let
$k\geq\max_{i\in[2]}|V(P_{i})\cap\dot{A}|$. Let
$\mathcal{A}=(E^{\mathrm{ab}},f)$ be a $(\\{v_{1},v_{2}\\},k+1)$-absorbing
structure such that, for each $i\in[2]$, $E(P_{i})\cap
E^{\mathrm{ab}}=\varnothing$. Then, for each $i\in[2]$ there exists a set
$E_{i}\subseteq f(v_{i})$, where $|E_{i}|=1$ if $v_{i}\in\dot{A}$ and
$|E_{i}|=2$ otherwise, such that the digraph with edge set $E(P_{1})\cup
E(P_{2})\cup E_{1}\cup E_{2}$ can be decomposed into two
$(A^{+},A^{-})$-paths.

###### Proof.

For each $i\in[2]$, we consider three cases. If $v_{i}\in A^{+}$, by our
choice of $k$, there is some edge $v_{i}y_{i}\in f(v_{i})$ with $y_{i}\notin
V(P_{3-i})$. In such a case, we let $P_{i}^{+}\coloneqq v_{i}y_{i}$ and
$P_{i}^{-}\coloneqq v_{i}$. If $v_{i}\in A^{-}$, similarly, there is some edge
$x_{i}v_{i}\in f(v_{i})$ with $x_{i}\notin V(P_{i})$, and we let
$P_{i}^{+}\coloneqq v_{i}$ and $P_{i}^{-}\coloneqq x_{i}v_{i}$. Otherwise, we
have $v_{i}\in A^{0}$ and, again by assumption, there must be two edges
$x_{i}v_{i},v_{i}y_{i}\in f(v_{i})$ such that $x_{i}\notin V(P_{i})$ and
$y_{i}\notin V(P_{3-i})$. In this case, we let $P_{i}^{+}\coloneqq v_{i}y_{i}$
and $P_{i}^{-}\coloneqq x_{i}v_{i}$. In all cases we set $E_{i}\coloneqq
E(P_{i}^{+})\cup E(P_{i}^{-})$.

Now let $P\coloneqq P_{1}^{-}P_{1}P_{2}^{+}$ and $P^{\prime}\coloneqq
P_{2}^{-}P_{2}P_{1}^{+}$. Clearly, $P$ and $P^{\prime}$ decompose
$E(P_{1})\cup E(P_{2})\cup E_{1}\cup E_{2}$. Furthermore, both $P$ and
$P^{\prime}$ are $(A^{+},A^{-})$-paths by the definition of $\mathcal{A}$ and
our choice of $x_{i},y_{i}$. Indeed, for each $i\in[2]$, by definition we have
that the first vertex of $P_{i}^{-}$ lies in $A^{+}$, and the last vertex of
$P_{i}^{+}$ lies in $A^{-}$, which immediately yields the result. ∎

The following lemma shows how an absorbing structure can be used to absorb a
collection of short cycles.

######  Lemma 4.14.

Let $D$ be an $(n,p,\kappa,\lambda)$-digraph with $\kappa\geq 4N/n$. Let
$\mathcal{C}_{3}$ be a collection of at most $N$ edge-disjoint cycles such
that, for each $C\in\mathcal{C}_{3}$, we have $|V(C)\cap\dot{A}|\leq\kappa$.
Let $\mathcal{A}=(E^{\mathrm{ab}},f)$ be an
$(A^{0}\cup\dot{A},3\kappa)$-absorbing structure with $E(\mathcal{C}_{3})\cap
E^{\mathrm{ab}}=\varnothing$. Then, the digraph with edge set
$E(\mathcal{C}_{3})\cup E^{\mathrm{ab}}$ can be decomposed into a set of
cycles $\mathcal{C}^{*}$ and a digraph $Q$ such that

  1. $(\mathrm{S}1)$

$E(\mathcal{C}^{*})\subseteq E(\mathcal{C}_{3})$;

  2. $(\mathrm{S}2)$

for all $C\in\mathcal{C}^{*}$ we have $|V(C)\cap\dot{A}|>\kappa$, and

  3. $(\mathrm{S}3)$

$Q$ has a perfect decomposition in which each path is an $(A^{+},A^{-})$-path.

###### Proof.

We will construct $Q$ and $\mathcal{C}^{*}$ over multiple rounds. We start
with a set of cycles $\mathcal{C}\coloneqq\mathcal{C}_{3}$ and a set of edges
$F^{\mathrm{ab}}\coloneqq E^{\mathrm{ab}}$, and we set
$Q\coloneqq(V(D),\varnothing)$ and $\mathcal{C}^{*}\coloneqq\varnothing$. In
each round, we will update $\mathcal{C}$, $F^{\mathrm{ab}}$, $Q$ and
$\mathcal{C}^{*}$ by moving some edges from $E(\mathcal{C})\cup
F^{\mathrm{ab}}$ to $E(Q)\cup E(\mathcal{C}^{*})$. In particular, in each
round, we will combine edges from $F^{\mathrm{ab}}$ with some Eulerian
subdigraph of $E(\mathcal{C})$ to form $(A^{+},A^{-})$-paths (by using Lemma
4.13) and move the (edges of these) paths into $Q$. Since we only ever add
$(A^{+},A^{-})$-paths to $Q$, then $Q$ always has a perfect decomposition by
Proposition 3.3. (Throughout we will also maintain that $F^{\mathrm{ab}}$ can
be decomposed into $(A^{+},A^{-})$-paths.) After these paths have been added
to $Q$, what remains of $E(\mathcal{C})$ will be Eulerian and reside on a
significantly smaller number of vertices. We will then apply Theorem 3.4 to
decompose what remains of $E(\mathcal{C})$ into cycles: any medium or long
cycle in this decomposition (i.e., those that have more than $\kappa$ vertices
in $\dot{A}$) will be added to $\mathcal{C}^{*}$, while the remaining cycles
in the decomposition form the set $\mathcal{C}$ for the next round. Since
$|V(\mathcal{C})|$ decreases in each round, this process will stop after a
finite number of rounds. At that point, we add any remaining edges from
$F^{\mathrm{ab}}$, decomposed into $(A^{+},A^{-})$-paths, into $Q$, which will
have a perfect decomposition.

It is important that we use edges/paths from our absorbing structure carefully
in each round so that there are sufficiently many choices available at each
vertex in future rounds. By solving a suitable flow problem, we will make sure
that, over the course of all rounds, we use at most $\kappa$ edges/paths from
$E^{\mathrm{ab}}$ at each vertex. This will ensure there are always at least
$2\kappa$ choices of edges/paths available in $F^{\mathrm{ab}}$ at every
vertex in every round, which will allow us to construct suitable absorbing
(sub)structures in order to apply Lemma 4.13.

Let us now give the details of this iterative process. At the start of each
round we are given a digraph $Q$, a set of edges $F^{\mathrm{ab}}\subseteq
E^{\mathrm{ab}}$ and two sets of cycles $\mathcal{C}$ and $\mathcal{C}^{*}$,
which have been updated in previous rounds and satisfy the following
properties:

  1. (a)

$E(\mathcal{C}_{3})\cup E^{\mathrm{ab}}$ is the disjoint union of $E(Q)$,
$F^{\mathrm{ab}}$, $E(\mathcal{C})$, and $E(\mathcal{C}^{*})$;

  2. (b)

$Q$ can be decomposed into $(A^{+},A^{-})$-paths;

  3. (c)

writing $n^{\prime}\coloneqq|V(\mathcal{C})|$, we have $|\mathcal{C}|\leq
c^{\prime}n^{\prime}\log n^{\prime}$ (where $c^{\prime}$ is the constant from
Theorem 3.4) and $|V(C)\cap\dot{A}|\leq\kappa$ for all $C\in\mathcal{C}$, and

  4. (d)

$|V(C)\cap\dot{A}|>\kappa$ for all $C\in\mathcal{C}^{*}$.

The digraph $Q$ and the sets $F^{\mathrm{ab}}$ and $\mathcal{C}$ are updated
several times throughout each round, and the notation will always refer to
their updated form.

Recall that, as stated in Definition 4.4, we may think of
$\mathcal{A}=(E^{\mathrm{ab}},f)$ as a set of edge-disjoint paths of length
$1$ or $2$. In the same way, we also think of the edges of $F^{\mathrm{ab}}$
as paths of length $1$ or $2$. For any $v\in A^{+}\cup A^{-}$, we think of
each edge in $F^{\mathrm{ab}}\cap f(v)$ as an $(A^{+},A^{-})$-path of length
$1$. Because of the way we use edges for absorption (i.e., by using Lemma
4.13), for any $v\in A^{0}$, the set $F^{\mathrm{ab}}\cap f(v)$ will always
contain the same number of edges from $A^{+}$ to $v$ as from $v$ to $A^{-}$,
and these will be (implicitly) paired up arbitrarily and thought of as
$(A^{+},A^{-})$-paths of length $2$. Note that the pairing is updated
(arbitrarily) every time $F^{\mathrm{ab}}$ is updated. For each vertex $v$,
let $a(v)$ denote the current number of available paths in
$F^{\mathrm{ab}}\cap f(v)$, that is,

$a(v)=\begin{cases}d^{+}_{F^{\mathrm{ab}}\cap f(v)}(v)&\text{if }v\in
A^{+},\\\ d^{-}_{F^{\mathrm{ab}}\cap f(v)}(v)&\text{if }v\in A^{-},\\\
d^{+}_{F^{\mathrm{ab}}\cap f(v)}(v)=d^{-}_{F^{\mathrm{ab}}\cap
f(v)}(v)&\text{if }v\in A^{0}.\end{cases}$

As we want to use at most $\kappa$ paths at each vertex $v\in V(\mathcal{C})$,
we define the number of _ready paths_ at $v$ as $r(v)\coloneqq a(v)-2\kappa$.
Throughout, we implicitly update the values of $a(v)$ and $r(v)$ each time we
update $F^{\mathrm{ab}}$.

We further assume the following property about $\mathcal{C}$ at the start of
the round:

  1. (e)

for all $v\in V(\mathcal{C})$ we have at least one of
$d^{+}_{\mathcal{C}}(v)\leq r(v)$, or $r(v)=\kappa$ (i.e., the number of
cycles in $\mathcal{C}$ passing through $v$ is bounded above by $r(v)$ or
$r(v)=\kappa$).

Note that, at the start of the first round, we have $Q=(V(D),\varnothing)$,
$F^{\mathrm{ab}}=E^{\mathrm{ab}}$, $\mathcal{C}=\mathcal{C}_{3}$ and
$\mathcal{C}^{*}=\varnothing$, so (a)–(e) hold.

We now show how to update $Q$, $\mathcal{C}$, and $\mathcal{C}^{*}$ and check
that (a)–(e) hold at the end of the round. Consider the flow problem
$\mathit{FP}(\mathcal{C};2,\kappa)$ and let $\phi$ be a maximum integer flow.
Let $F_{\phi}$ be the residual digraph of $F=F(\mathcal{C})$ under $\phi$. Set
$T\coloneqq\\{v\in V(\mathcal{C}):F_{\phi}\text{ contains an
}(s,v)\text{-path}\\}$ and $T^{\prime}\coloneqq V(\mathcal{C})\setminus T$.

We establish a bound on $|T|$ for later. Since the cut-set
$M_{0}\coloneqq\\{sC:C\in\mathcal{C}\\}$, by (c), has capacity
$2|\mathcal{C}|\leq 2c^{\prime}n^{\prime}\log n^{\prime}$, the max-flow min-
cut theorem (Theorem 3.5) implies that $\mathit{val}(\phi)\leq
2c^{\prime}n^{\prime}\log n^{\prime}$. Furthermore, all vertices in $T$ must
have $\kappa$ units of flow going through them in $\phi$, as otherwise we
would immediately be able to increase the flow. Therefore,

$\kappa|T|\leq\mathit{val}(\phi)\leq 2c^{\prime}n^{\prime}\log n^{\prime},$

which implies

$|T|\leq\frac{2c^{\prime}n^{\prime}\log
n^{\prime}}{\kappa}\leq\frac{n^{\prime}}{2},$ (4.9)

as $\kappa\geq 4N/n\geq 4c^{\prime}\log n^{\prime}$.

We use $\phi$ to assign vertices to cycles as follows. First, we greedily
decompose $\phi$ into single-unit flows. As each single-unit flow goes through
one cycle $C\in\mathcal{C}$ and one vertex $v\in V(C)$, we understand this as
assigning $v$ to $C$. Note that for every $v\in V(\mathcal{C})$, the flow
$\phi(vt)$ through the edge $vt$ satisfies

$\phi(vt)\leq\min\\{d^{+}_{\mathcal{C}}(v),\kappa\\}\leq r(v),$ (4.10)

where the last inequality holds by (e).

We partition $\mathcal{C}$ into three sets
$\mathcal{C}=\mathcal{C}^{0}\cup\mathcal{C}^{1}\cup\mathcal{C}^{2}$, where
$\mathcal{C}^{i}$ is the set of cycles $C\in\mathcal{C}$ that are assigned
exactly $i$ vertices from $T^{\prime}$. Recall that we decomposed the flow
$\phi$ into single-unit flows. For each $i\in[2]_{0}$, let $\phi^{i}$ be the
flow that is given by the sum of the single-unit flows of the decomposition
that pass through cycles in $\mathcal{C}^{i}$. In particular, this means that
$\phi=\phi^{1}+\phi^{2}+\phi^{3}$ and, for each $v\in V(\mathcal{C})$,
$\phi^{i}(vt)$ is the number of cycles in $\mathcal{C}^{i}$ to which $v$ is
assigned. We next show how to process the cycles in each $\mathcal{C}^{i}$,
but first we need the following claim.

######  Claim 4.15.

For all cycles $C\in\mathcal{C}^{1}$, we have $|V(C)\cap T^{\prime}|=1$ (and
so the unique vertex in $V(C)\cap T^{\prime}$ must be assigned to $C$). In
particular, for all $v\in T^{\prime}$ we have
$\phi^{1}(vt)=d^{+}_{\mathcal{C}^{1}}(v)$.

For all cycles $C\in\mathcal{C}^{0}$, we have $|V(C)\cap T^{\prime}|=0$.

###### Proof.

For all $C\in\mathcal{C}^{0}\cup\mathcal{C}^{1}$, note first that there is a
path from $s$ to $C$ in $F_{\phi}$. Indeed, if $C$ is assigned fewer than two
vertices, then the path is immediate, while if $C$ is assigned two vertices,
at least one of them, say $u$, is in $T$, and so the $(s,u)$-path in
$F_{\phi}$ (which exists by the definition of $T$) can be extended to $C$. Now
any vertices $v\in V(C)$ that are not assigned to $C$ must lie in $T$ by
definition, as we can extend the $(s,C)$-path in $F_{\phi}$ to $v$. Therefore,
for each $i\in\\{0,1\\}$ and all $C\in\mathcal{C}^{i}(v)$ we must have
$|V(C)\cap T^{\prime}|=i$.

Now, any vertex $v\in T^{\prime}$ that belongs to a cycle
$C\in\mathcal{C}^{1}$ is also assigned to it, establishing that
$\phi^{1}(vt)=d^{+}_{\mathcal{C}^{1}}(v)$ for all $v\in T^{\prime}$. ∎

We start by processing the cycles in $\mathcal{C}^{2}$. For each cycle
$C\in\mathcal{C}^{2}$, let $v_{1},v_{2}\in T^{\prime}$ be such that
$\phi(Cv_{i})=1$ for each $i\in[2]$, i.e., these are the vertices assigned to
$C$. We split $C$ into a $(v_{1},v_{2})$-path $P_{12}$ and a
$(v_{2},v_{1})$-path $P_{21}$. We select any $\kappa+1$ available paths at
each $v_{i}$ from $F^{\mathrm{ab}}$ to define a
$(\\{v_{1},v_{2}\\},\kappa+1)$-absorbing structure $\mathcal{A}_{C}$ (we show
below that this is always possible). We then apply Lemma 4.13 to the paths
$P_{12},P_{21}$ and the absorbing structure $\mathcal{A}_{C}$ with $k=\kappa$.
Thus, for each $i\in[2]$ we obtain an available path $E_{i}\subseteq
f(v_{i})\cap F^{\mathrm{ab}}$ such that $E(P_{12})\cup E(P_{21})\cup E_{1}\cup
E_{2}$ can be decomposed into two $(A^{+},A^{-})$-paths $P_{1}^{\prime}$ and
$P_{2}^{\prime}$. For each $i\in[2]$, we add the edges of $P_{i}^{\prime}$ to
$Q$, remove $E_{i}$ from $F^{\mathrm{ab}}$ and remove $C$ from $\mathcal{C}$.
We repeat this for all cycles in $\mathcal{C}^{2}$.

We now check that it is always possible to find the desired absorbing
structure $\mathcal{A}_{C}$. Notice that, in order to process
$\mathcal{C}^{2}$, the number of available paths that we use at any vertex $v$
is the number of cycles of $\mathcal{C}^{2}$ to which $v$ is assigned, which
at the start of the round is
$\phi^{2}(vt)\leq\min\\{d^{+}_{\mathcal{C}}(v),\kappa\\}\leq
r(v)=a(v)-2\kappa$ (by (4.10)). This means there are always $2\kappa$
available paths at every vertex each time we apply Lemma 4.13.

After processing $\mathcal{C}^{2}$, for any vertex $v\in T^{\prime}$, we have
used at most $\phi^{2}(vt)$ available paths from $f(v)$. Recalling that we
always update $a(v)$, we now have for any $v\in T^{\prime}$ that

$a(v)\geq\phi(vt)+2\kappa-\phi^{2}(vt)=\phi^{1}(vt)+2\kappa=d^{+}_{\mathcal{C}^{1}}(v)+2\kappa,$
(4.11)

where we have used (4.10) for the first inequality and 4.15 for the last
equality. The first equality holds as $\phi^{0}(vt)=0$ by definition, since
$v\in T^{\prime}$. Note that (e) holds for the current value of $a(v)$ and the
current set of cycles $\mathcal{C}=\mathcal{C}^{0}\cup\mathcal{C}^{1}$, since
$a(v)$ is unchanged for $v\in T$, and that (4.11) confirms (e) for $v\in
T^{\prime}$ (by using 4.15 to note that $d^{+}_{\mathcal{C}^{0}}(v)=0$ for all
$v\in T^{\prime}$).

Next we process cycles in $\mathcal{C}^{1}$. Recall that, by 4.15, such cycles
contain exactly one vertex of $T^{\prime}$. Let $R$ be an empty set of edges;
this set will be updated while processing $\mathcal{C}^{1}$ and will always
form an Eulerian digraph. We say a pair of cycles
$C_{1},C_{2}\in\mathcal{C}^{1}$ is $T$-intersecting if
$\varnothing\not=V(C_{1})\cap V(C_{2})\subseteq T$ (and thus their unique
vertices in $T^{\prime}$ are distinct). Whenever we have a $T$-intersecting
pair of cycles $C_{1},C_{2}\in\mathcal{C}^{1}$, we process them as follows.
Let $v_{1}\neq v_{2}$ be the vertices of $C_{1}$ and $C_{2}$ in $T^{\prime}$,
respectively. Starting from $v_{1}$, let $v^{\prime}_{1}$ be the first vertex
along $C_{1}$ in $V(C_{1})\cap V(C_{2})$ and define $P_{12}\coloneqq
v_{1}C_{1}v^{\prime}_{1}C_{2}v_{2}$. Define $v^{\prime}_{2}$ analogously, and
let $P_{21}\coloneqq v_{2}C_{2}v^{\prime}_{2}C_{1}v_{1}$. It is easy to see
that $P_{12}$ and $P_{21}$ are edge-disjoint. Again, we construct a
$(\\{v_{1},v_{2}\\},2\kappa+1)$-absorbing structure $\mathcal{A}_{C_{1}C_{2}}$
by taking $2\kappa+1$ available paths at each $v_{i}$ from $F^{\mathrm{ab}}$;
this is always possible by (4.11), as we find an absorbing structure for
$v_{i}$ at most $d^{+}_{\mathcal{C}^{1}}(v_{i})$ times. We apply Lemma 4.13 to
the paths $P_{12},P_{21}$ and the absorbing structure
$\mathcal{A}_{C_{1}C_{2}}$ with $k=2\kappa$ to obtain available paths
$E_{i}\subseteq f(v_{i})\cap F^{\mathrm{ab}}$, for $i\in[2]$, such that
$E(P_{12})\cup E(P_{21})\cup E_{1}\cup E_{2}$ can be decomposed into two
$(A^{+},A^{-})$-paths $P_{1}^{\prime}$ and $P_{2}^{\prime}$. For each
$i\in[2]$, we add the edges of $P_{i}^{\prime}$ to $Q$ and remove the edges of
$E_{i}$ from $F^{\mathrm{ab}}$. The remaining edges of the cycles $C_{1}$ and
$C_{2}$, namely $(E(C_{1})\cup E(C_{2}))\setminus(E(P_{12})\cup E(P_{21}))$,
are then added to the residual digraph $R$. Notice that the set of edges added
to $R$ is Eulerian, so $R$ remains Eulerian. Furthermore, note that all edges
added to $R$ have both endpoints in $T$. Finally, we remove $C_{1}$ and
$C_{2}$ from $\mathcal{C}$ (and from $\mathcal{C}^{1}$).

We repeat this as long as we can find a $T$-intersecting pair of cycles in
$\mathcal{C}^{1}$. When no such pair can be found, then, among the remaining
cycles of $\mathcal{C}^{1}$, any two either share a vertex in $T^{\prime}$ or
are vertex-disjoint. This implies that, at this stage, the set
$\overline{T}\coloneqq V(\mathcal{C}^{1})\cap T^{\prime}$ satisfies
$|\overline{T}|\leq|T|/2$. (To see this, for each vertex $v\in\overline{T}$,
pick a cycle $C_{v}\in\mathcal{C}^{1}$ containing $v$. Notice that each such
cycle has all its (at least two) remaining vertices in $T$ and, furthermore,
the cycles $C_{v}$ are vertex-disjoint.) We move all the remaining cycles of
$\mathcal{C}$ (i.e., all that remain in $\mathcal{C}^{1}$ and all in
$\mathcal{C}^{0}$) to $R$. Then, $R$ is Eulerian and $V(R)\subseteq
T\cup\overline{T}$ (recall any cycle in $\mathcal{C}^{0}$ has all its vertices
in $T$ by 4.15). Then,

$n^{\prime\prime}\coloneqq|V(R)|\leq|T|+|\overline{T}|\leq 3|T|/2\leq
3n^{\prime}/4,$ (4.12)

where the last inequality follows by (4.9).

Now we decompose $R$ into at most $c^{\prime}n^{\prime\prime}\log
n^{\prime\prime}$ cycles using Theorem 3.4; any resulting cycles with more
than $\kappa$ vertices in $\dot{A}$ are added to $\mathcal{C}^{*}$, while all
other cycles are added to (the currently empty) $\mathcal{C}$. This completes
the round and the description of the sets $\mathcal{C}$, $\mathcal{C}^{*}$,
$F^{\mathrm{ab}}$, and $Q$ ready for the next round. Notice that at the end of
the round $V(\mathcal{C})$ is smaller than at the start, by (4.12). It remains
to check that (a)–(e) hold.

It immediately follows by construction that (a)–(d) hold ((a) holds because we
only move edges between the sets, and (b) holds because we only add
$(A^{+},A^{-})$-paths to $Q$). Finally, we prove that (e) holds too. As noted
after (4.11), we know (e) holds after $\mathcal{C}^{2}$ is processed. After
that, when processing $\mathcal{C}^{1}$, whenever an application of Lemma 4.13
reduces $a(v)$ by $1$, it also reduces $d^{+}_{\mathcal{C}}(v)$ by $1$, so
condition (e) is maintained to the end of the round.

Thus, we may iterate the described process through the rounds, until we obtain
the final sets $Q$, $\mathcal{C}=\varnothing$, $\mathcal{C}^{*}$ and $F^{{\rm
ab}}$ satisfying (a)–(e). (Recall that the process must terminate since, by
(4.12), the set of cycles that is considered for each subsequent round is
contained in a smaller set of vertices than the previous.) The remaining paths
of $F^{{\rm ab}}$ are $(A^{+},A^{-})$-paths; these paths are removed from
$F^{{\rm ab}}$ and added to $Q$.

It is straightforward to check that $Q$ and $\mathcal{C}^{*}$ now satisfy the
conclusion of the lemma. Indeed, over the course of all rounds, we moved all
edges from $E(\mathcal{C}_{3})\cup E^{\mathrm{ab}}$ to $E(Q)\cup
E(\mathcal{C}^{*})$. At every stage, $Q$ was updated by adding
$(A^{+},A^{-})$-paths (which gives a perfect decomposition of $Q$ by
Proposition 3.3), and $\mathcal{C}^{*}$ was updated by adding cycles that have
more than $\kappa$ vertices in $\dot{A}$. ∎

We are finally ready to prove the main result.

###### Proof of Theorem 4.3.

Recall that $D$ is either an $(n,p,\kappa,\lambda)$-digraph satisfying
$(\mathrm{C}1)$–$(\mathrm{C}3)$ or an $(n,p,\kappa,\lambda)$-pseudorandom
digraph satisfying $(\mathrm{C}^{\prime}1)$, $(\mathrm{C}^{\prime}2)$, and
$(\mathrm{C}3)$, with $n\geq n_{0}$ (for a suitably large choice of $n_{0}$).
We work with both cases simultaneously.

First, one can easily check that the conditions
$(\mathrm{C}1)$–$(\mathrm{C}3)$ together with $n\geq n_{0}$, for a
sufficiently large $n_{0}$, imply the conditions $(\mathrm{a})$–$(\mathrm{c})$
below, which are precisely the parameter conditions required in order to apply
Lemmas 4.5, 4.6, 4.9, 4.11 and 4.14 to an $(n,p,\kappa,\lambda)$-digraph:

  1. $(\mathrm{a})$

$\max\\{100\log
n,12,(12\lambda)^{1/2},(72N^{2})^{1/5},{4N}/{n}\\}\leq\kappa<\min\\{{np}/{120},N^{1/2}\\}$,

  2. $(\mathrm{b})$

$\lambda\leq{np}/{3}$,

  3. $(\mathrm{c})$

$4np\log(2n)\leq\kappa\lambda$,

where $N\coloneqq c^{\prime}n\log n$ and $c^{\prime}$ is the constant from
Theorem 3.4. Similarly, one can easily check that the conditions
$(\mathrm{C}^{\prime}1)$, $(\mathrm{C}^{\prime}2)$, and $(\mathrm{C}3)$
together with $n\geq n_{0}$, for a sufficiently large $n_{0}$, imply the
conditions $(\mathrm{a}^{\prime})$, $(\mathrm{b})$, and $(\mathrm{c})$ (with
$(\mathrm{a}^{\prime})$ given below), which are precisely the parameter
conditions required in order to apply Lemmas 4.5, 4.6, 4.9, 4.11 and 4.14 to
an $(n,p,\kappa,\lambda)$-pseudorandom digraph:

  1. $(\mathrm{a}^{\prime})$

$\max\\{100\log
n,12,(12\lambda)^{1/2},(7200N^{2}p)^{1/5},\frac{4N}{n},\sqrt{12/(25p)}\log
n\\}\leq\kappa<\min\\{\frac{np}{120},N^{1/2}\\}$.

The pseudorandom case only makes a difference for Lemma 4.11.

For the $(n,p,\kappa,\lambda)$-(pseudorandom) digraph $D$, let $A^{+}\cup
A^{-}\cup A^{0}$ be the associated partition of $V(D)$. Write $B^{+}$,
$B^{-}$, and $B^{0}$ for the set of vertices $v\in V(D)$ such that ${\mbox{\rm
ex}}_{D}(v)>0$, ${\mbox{\rm ex}}_{D}(v)<0$, and ${\mbox{\rm ex}}_{D}(v)=0$,
respectively. From Definition 4.1, clearly $A^{+}\subseteq B^{+}$ and
$A^{-}\subseteq B^{-}$.

Let $\dot{\mathcal{A}}=(\dot{E}^{\mathrm{ab}},\dot{f})$ be an
$(\dot{A},12\kappa)$-absorbing structure contained in $D$, which exists by
Lemma 4.5, and let $\mathcal{A}^{0}=(E_{0}^{\mathrm{ab}},f_{0})$ be an
$(A^{0},3\kappa)$-absorbing structure contained in $D$, which exists by Lemma
4.6. Note that these two absorbing structures must be edge-disjoint by
definition. We next split up $\dot{\mathcal{A}}$ into an
$(\dot{A},7\kappa-1)$-absorbing structure
$\dot{\mathcal{A}}_{1}=(\dot{E}^{\mathrm{ab}}_{1},\dot{f}_{1})$, an
$(\dot{A},2\kappa+1)$-absorbing structure
$\dot{\mathcal{A}}_{2}=(\dot{E}^{\mathrm{ab}}_{2},\dot{f}_{2})$, and an
$(\dot{A},3\kappa)$-absorbing structure
$\dot{\mathcal{A}}_{3}=(\dot{E}^{\mathrm{ab}}_{3},\dot{f}_{3})$. To do so, for
each $v\in\dot{A}$, we arbitrarily split the $12\kappa$ edges in $\dot{f}(v)$
into sets of size $7\kappa-1$, $2\kappa+1$ and $3\kappa$ and set these to be
$\dot{f}_{1}(v)$, $\dot{f}_{2}(v)$ and $\dot{f}_{3}(v)$, respectively, and set
$\dot{E}^{\mathrm{ab}}_{i}\coloneqq\bigcup_{v\in\dot{A}}\dot{f}_{i}(v)$ for
each $i\in[3]$. Lastly, we combine $\dot{\mathcal{A}}_{3}$ and
$\mathcal{A}^{0}$ into an $(\dot{A}\cup A^{0},3\kappa)$-absorbing structure
$\mathcal{A}_{3}=(\dot{E}^{\mathrm{ab}}_{3}\cup E_{0}^{\mathrm{ab}},f_{3})$,
where $f_{3}\rvert_{\dot{A}}=\dot{f}_{3}$ and $f_{3}\rvert_{A^{0}}=f_{0}$.

Consider a set of paths which consists of every individual edge in
$\dot{E}^{\mathrm{ab}}$ and a partition of the edges in $E^{\mathrm{ab}}_{0}$
into paths of length two. Each path is an $(A^{+},A^{-})$-path and, therefore,
a $(B^{+},B^{-})$-path. Moreover, note that, by Lemmas 4.5 and 4.6,
$\dot{E}^{\mathrm{ab}}\cup E^{\mathrm{ab}}_{0}$ contains at most
$150\kappa+5\kappa=155\kappa$ edges incident to each $v\in\dot{A}$. This means
(by $(\mathrm{P}1)$ and $(\mathrm{P}2)$) that removing all these paths from
$D$ will not change the sign of the excess of any vertex $v\in V(D)$, that is,
if we write $D^{\prime}\coloneqq D\setminus(\dot{E}^{\mathrm{ab}}\cup
E^{\mathrm{ab}}_{0})$, then a vertex of positive (resp. negative) excess in
$D^{\prime}$ belongs to $B^{+}$ (resp. $B^{-}$).

Next, we greedily remove paths from $D^{\prime}$ that start in vertices with
positive excess in $D^{\prime}$ and end in vertices with negative excess in
$D^{\prime}$ until this is no longer possible. We call the set of these paths
$\mathcal{P}^{\prime}$ (so every path in $\mathcal{P}^{\prime}$ is a
$(B^{+},B^{-})$-path) and set $D^{*}\coloneqq D^{\prime}\setminus
E(\mathcal{P}^{\prime})$ (so that ${\mbox{\rm ex}}(D^{*})=0$ by Proposition
3.2).

We apply Theorem 3.4 to every component of $D^{*}$ and obtain a decomposition
$\mathcal{C}$ of the edges of $D^{*}$ into at most $N\coloneqq c^{\prime}n\log
n$ cycles. Let

$\displaystyle\mathcal{C}_{1}$
$\displaystyle\coloneqq\\{C\in\mathcal{C}:|V(C)\cap\dot{A}|\geq N/\kappa\\},$
$\displaystyle\mathcal{C}_{2}$
$\displaystyle\coloneqq\\{C\in\mathcal{C}:\kappa<|V(C)\cap\dot{A}|<N/\kappa\\},\text{
and}$ $\displaystyle\mathcal{C}_{3}$
$\displaystyle\coloneqq\\{C\in\mathcal{C}:|V(C)\cap\dot{A}|\leq\kappa\\}.$

At this point, we have

$\displaystyle E(D)$ $\displaystyle=E(D^{\prime})\cup\dot{E}^{\rm ab}\cup
E_{0}^{\rm ab}$ $\displaystyle=E(D^{\prime})\cup\dot{E}_{1}^{\rm
ab}\cup\dot{E}_{2}^{\rm ab}\cup\dot{E}_{3}^{\rm ab}\cup E_{0}^{\rm ab}$
$\displaystyle=E(\mathcal{P}^{\prime})\cup E(D^{*})\cup\dot{E}_{1}^{\rm
ab}\cup\dot{E}_{2}^{\rm ab}\cup\dot{E}_{3}^{\rm ab}\cup E_{0}^{\rm ab}$
$\displaystyle=E(\mathcal{P}^{\prime})\cup\left(E(\mathcal{C}_{1})\cup\dot{E}_{1}^{\rm
ab}\right)\cup\left(E(\mathcal{C}_{2})\cup\dot{E}_{2}^{\rm
ab}\right)\cup\left(E(\mathcal{C}_{3})\cup\dot{E}_{3}^{\rm ab}\cup E_{0}^{\rm
ab}\right).$

Noting that $|\mathcal{C}_{3}|\leq N$, we apply Lemma 4.14 to
$\mathcal{C}_{3}$ and $\mathcal{A}_{3}$ to decompose the edges of
$E(\mathcal{C}_{3})\cup\dot{E}_{3}^{\rm ab}\cup E_{0}^{\rm ab}$ into a set of
cycles $\mathcal{C}^{*}_{3}$ and a digraph $Q$, where $Q$ has a perfect
decomposition $\mathcal{P}_{3}$ into $(A^{+},A^{-})$-paths,
$|\mathcal{C}^{*}_{3}|\leq|\mathcal{C}_{3}|$, and for all
$C\in\mathcal{C}^{*}_{3}$ we have $|V(C)\cap\dot{A}|>\kappa$. (Indeed, the
fact that $|\mathcal{C}_{3}^{*}|\leq|\mathcal{C}_{3}|$ follows from
conclusions $(\mathrm{S}1)$ and $(\mathrm{S}2)$ of Lemma 4.14. To see this,
note that any cycle $C\subseteq D$ satisfies $|\\{uv\in
E(C):v\in\dot{A}\\}|=|V(C)\cap\dot{A}|$. Thus, by $(\mathrm{S}2)$, for each
$C\in\mathcal{C}_{3}^{*}$ and each $C^{\prime}\in\mathcal{C}_{3}$ we must have
$|\\{uv\in E(C):v\in\dot{A}\\}|>|\\{uv\in E(C^{\prime}):v\in\dot{A}\\}|$, so
by $(\mathrm{S}1)$, $\mathcal{C}^{*}$ must have fewer cycles than
$\mathcal{C}_{3}$.) Let
$\mathcal{C}^{*}_{1}\coloneqq\\{C\in\mathcal{C}^{*}_{3}:|V(C)\cap\dot{A}|\geq
N/\kappa\\}$ and
$\mathcal{C}^{*}_{2}\coloneqq\\{C\in\mathcal{C}:\kappa<|V(C)\cap\dot{A}|<N/\kappa\\}$
and note that, as $|\mathcal{C}^{*}_{3}|\leq|\mathcal{C}_{3}|$, we have
$|\mathcal{C}^{*}_{1}|,|\mathcal{C}^{*}_{2}|\leq N$.

Next, we apply Lemma 4.9 to $\mathcal{C}_{1}\cup\mathcal{C}^{*}_{1}$ and
$\dot{\mathcal{A}}_{1}$; this shows that the digraph with edge set
$E(\mathcal{C}_{1}\cup\mathcal{C}^{*}_{1})\cup\dot{E}^{\mathrm{ab}}_{1}$ has a
perfect decomposition $\mathcal{P}_{1}$ into $(A^{+},A^{-})$-paths.

In the same way, applying Lemma 4.11 to
$\mathcal{C}_{2}\cup\mathcal{C}^{*}_{2}$ and $\dot{\mathcal{A}}_{2}$ shows
that the digraph with edge set
$E(\mathcal{C}_{2}\cup\mathcal{C}^{*}_{2})\cup\dot{E}^{\mathrm{ab}}_{2}$ has a
perfect decomposition $\mathcal{P}_{2}$ into $(A^{+},A^{-})$-paths.

Now it is easy to check that
$\mathcal{P}^{\prime}\cup\mathcal{P}_{1}\cup\mathcal{P}_{2}\cup\mathcal{P}_{3}$
is a decomposition of $E(D)$ into paths, and every path is a
$(B^{+},B^{-})$-path, so this is a perfect decomposition of $D$ by Proposition
3.3. ∎

##  5\. Path decompositions of random digraphs

In this section we derive Theorem 1.2. This will follow immediately as a
consequence of Theorem 4.3 and the following result.

######  Theorem 5.1.

Let $13\log^{2}n/\sqrt{n}\leq p\leq 1-150\log^{4}n/n$. Let
$\kappa\coloneqq\sqrt{np(1-p)}/(155\log^{3/4}n)$ and $\lambda\coloneqq
5\sqrt{n/(1-p)}\log^{2}n$. Then, a.a.s. $D_{n,p}$ is an
$(n,p,\kappa,\lambda)$-pseudorandom digraph.

Now we prove Theorem 1.2.

###### Proof of Theorem 1.2.

Let $\log^{4}n/n^{1/3}\leq p\leq 1-\log^{5/2}n/n^{1/5}$ (so within the range
stated in the theorem), and let $n$ be sufficiently large. As usual, let
$N\coloneqq c^{\prime}n\log n$, where $c^{\prime}$ is the constant from
Theorem 3.4.

If we let $D=D_{n,p}$, then by Theorem 5.1 we have that a.a.s. $D$ is an
$(n,p,\kappa,\lambda)$-pseudorandom digraph, where
$\kappa=\sqrt{np(1-p)}/(155\log^{3/4}n)$ and
$\lambda=5\sqrt{n/(1-p)}\log^{2}n$. As mentioned in Remark 4.2, $D$ is also an
$(n,p,\kappa^{\prime},\lambda^{\prime})$-pseudorandom digraph for any
$\kappa^{\prime}\leq\kappa$ and any $\lambda^{\prime}\geq\lambda$. Taking
$\kappa^{\prime}=6(N^{2}p)^{1/5}$ and
$\lambda^{\prime}=\min\\{np/3,(\kappa^{\prime})^{2}/12\\}$, and checking that
$\kappa^{\prime}<\kappa$ and $\lambda^{\prime}>\lambda$ for the given range of
$p$ and $n$ sufficiently large, we have that $D$ is an
$(n,p,\kappa^{\prime},\lambda^{\prime})$-pseudorandom digraph, so we can apply
Theorem 4.3 to conclude that $D$ has a perfect decomposition (that is, it is
consistent). ∎

In order to prove Theorem 5.1, we will show that each of the properties of
Definition 4.1 holds a.a.s. First, we require some properties about the edge
distribution in $D_{n,p}$.

######  Lemma 5.2.

There exists a constant $C>0$ such that, for all $p\geq C\log n/n$, a.a.s. the
digraph $D=D_{n,p}$ satisfies that, for all $A\subseteq V(D)$ with
$|A|\geq\log n/(50p)$, we have

$e_{D}(A)<100|A|^{2}p.$

###### Proof.

Fix some $\log n/(50p)\leq i\leq n$, and fix a set $A\subseteq V(D)$ with
$|A|=i$. Let $X\coloneqq e_{D}(A)$, so $\mathbb{E}[X]=(1-1/i)i^{2}p$. A direct
application of Lemma 3.7 shows that, for sufficiently large $n$,

$\mathbb{P}[X\geq 100i^{2}p]\leq(e/100)^{99i^{2}p}.$

Now consider all sets $A$ with $|A|=i$, and let $\mathcal{E}_{i}$ be the event
that at least one of these sets induces at least $100i^{2}p$ edges. By a union
bound, it follows that

$\mathbb{P}[\mathcal{E}_{i}]\leq\binom{n}{i}\left(\frac{e}{100}\right)^{99i^{2}p}\leq\left(\frac{en}{i}\right)^{i}\left(\frac{e}{100}\right)^{99i^{2}p}\leq\frac{1}{n^{3}},$

where one can check the final inequality using the lower bound on $i$. The
conclusion follows by a union bound over all values of $i$. ∎

######  Lemma 5.3.

There exist constants $C,c>0$ such that, for all $C\log n/n\leq p\leq 1-C\log
n/n$, with probability at least $1-o(1/n^{3})$ the digraph $D=D_{n,p}$
satisfies that, for all $v\in V$, we have

$d_{D}^{+}(v)=np\pm c\sqrt{np(1-p)\log n}\qquad\text{ and }\qquad
d_{D}^{-}(v)=np\pm c\sqrt{np(1-p)\log n}.$

###### Proof.

We split the proof into two cases. Assume first that $p\leq 1/2$. Fix a vertex
$v\in V(D)$ and a symbol $*\in\\{+,-\\}$. Then,
$\mathbb{E}[d_{D}^{*}(v)]=(n-1)p$ and, if $C$ and $n$ are sufficiently large
(we need $C$ to be sufficiently large so that the value of $\delta$ in Lemma
3.6 satisfies $\delta\in(0,1)$), by Lemma 3.6 we conclude that

$\mathbb{P}\left[d_{D}^{*}(v)\neq np\pm c\sqrt{np(1-p)\log n}\right]\leq
e^{-c^{2}\log n/50}.$

Now, by a union bound over all choices of $v$ and $*$, it follows that the
probability that the statement fails is at most $2ne^{-c^{2}\log
n/50}=o(1/n^{3})$ (where this equality holds for sufficiently large $c$).

For the second case, assume $p>1/2$, and consider the complement digraph
$\overline{D}\sim D_{n,1-p}$. We have that $1-p<1/2$, so we can apply the same
argument as above to obtain that, for each $v\in V(D)$ and $*\in\\{+,-\\}$,

$\mathbb{P}\left[d_{\overline{D}}^{*}(v)\neq n(1-p)\pm c\sqrt{np(1-p)\log
n}\right]\leq e^{-c^{2}\log n/50}.$

The conclusion follows by a union bound over all $v\in V(D)$ and
$*\in\\{+,-\\}$ and going back to $D$. ∎

Our next aim is to show that most vertices will have “high” excess, meaning
that its absolute value is “close” to the maximum possible value (around
$\sqrt{np(1-p)}$, up to a polylog factor) that follows from Lemma 5.3. The
following remark will come in useful.

######  Remark 5.4.

Let $p\in[0,1]$ and $n\in\mathbb{Z}$ with $n\geq 0$. Let
$X\sim\mathrm{Bin}(n,p)$. For each $i\in\mathbb{Z}$, let
$p_{i}\coloneqq\mathbb{P}[X=i]$. Let $D$ be a digraph and $v\in V(D)$ be such
that $d^{+}(v)=d^{-}(v)=n$. Let $D_{p}$ be a random subdigraph of $D$ obtained
by deleting each edge of $D$ with probability $1-p$ independently of all other
edges. Then, ${\mbox{\rm ex}}_{D_{p}}(v)$ follows a probability distribution
which, for each $i\in\\{-n,\ldots,n\\}$, satisfies that

$\mathbb{P}[{\mbox{\rm ex}}_{D_{p}}(v)=i]=\sum_{j=0}^{n}p_{j}p_{j-i}.$

In particular, the probability function is symmetric around $i=0$.

######  Lemma 5.5.

Consider the setting described in Remark 5.4, and assume $n\geq 2$. Then,
there exists an absolute constant $K$ such that

$\mathbb{P}[{\mbox{\rm ex}}_{D_{p}}(v)=0]\leq K\sqrt{\frac{\log n}{np(1-p)}}.$

###### Proof.

First note that, by adjusting the value of $K$, we may assume that $n$ is
larger than any fixed $n_{0}$ (by making the right hand side above greater
than $1$); we choose a sufficiently large $n_{0}$ so that all subsequent
claims hold. By similarly adjusting the value of $K$, for any given constant
$C_{0}$ we may assume that $C_{0}\log n/n\leq p\leq 1-C_{0}\log n/n$.

So assume $C\log n/n\leq p\leq 1-C\log n/n$, for a constant $C$ defined below.
One can readily check that $p^{*}\coloneqq\max_{i\in[n]_{0}}p_{i}$ is achieved
for $i=np\pm 2$ (where the $p_{i}$ are as defined in Remark 5.4). By using
Stirling’s approximation, it follows that $p^{*}\leq 1/\sqrt{np(1-p)}$. On the
other hand, by an application of Lemma 3.6, there exist constants $c,C>0$ such
that for all $C\log n/n\leq p\leq 1-C\log n/n$ we have that

$\sum_{i=0}^{np-c\sqrt{np(1-p)\log n}}p_{i}+\sum_{i=np+c\sqrt{np(1-p)\log
n}}^{n}p_{i}\leq e^{-c^{2}\log n/50}.$

Combining the above with Remark 5.4, it follows that

$\mathbb{P}[{\mbox{\rm ex}}_{D_{p}}(v)=0]\leq 2c\sqrt{np(1-p)\log
n}\cdot(p^{*})^{2}+e^{-c^{2}\log n/50}\leq K\sqrt{\frac{\log
n}{np(1-p)}}.\qed$

######  Lemma 5.6.

There exists a constant $C>0$ such that, for all $C\log n/n\leq p\leq 1-C\log
n/n$, a.a.s. the digraph $D=D_{n,p}$ contains at most $n/\log^{1/8}n$ vertices
$v$ such that $|{\mbox{\rm ex}}_{D}(v)|\leq\sqrt{np(1-p)}/\log^{3/4}n$.

###### Proof.

Take some vertex $v\in V(D)$. For each $i\in\mathbb{Z}$, let
$p_{i}\coloneqq\mathbb{P}[d_{D}^{+}(v)=i]=\mathbb{P}[d_{D}^{-}(v)=i]$. Now, by
Remark 5.4 we have that $q_{0}\coloneqq\mathbb{P}[{\mbox{\rm
ex}}_{D}(v)=0]=\sum_{j=0}^{n-1}p_{j}^{2}$ and, for all $i\in[n-1]$, we have
that $q_{i}\coloneqq\mathbb{P}[|{\mbox{\rm
ex}}_{D}(v)|=i]=\sum_{j=0}^{n-1}p_{j}(p_{j-i}+p_{j+i})$. In particular, by
Lemma 3.9, it follows that

$q_{i}\leq 2q_{0}$ (5.1)

for all $i\in[n-1]$. By combining this with Lemma 5.5 (with $n-1$ playing the
role of $n$), it follows that

$\mathbb{P}[|{\mbox{\rm
ex}}_{D}(v)|\leq\sqrt{np(1-p)}/\log^{3/4}n]=\mathcal{O}(1/\log^{1/4}n).$ (5.2)

Let $Y\coloneqq|\\{v\in V(D):|{\mbox{\rm
ex}}_{D}(v)|\leq\sqrt{np(1-p)}/\log^{3/4}n\\}|$. The statement follows by
applying Markov’s inequality to this random variable. ∎

We consider a partition of the vertices of $D_{n,p}$ into those with high
excess, low excess, and the rest. In general, given $D=D_{n,p}$, we write

$\displaystyle A^{+}$ $\displaystyle=A^{+}(D)\coloneqq\\{v\in V(D):{\mbox{\rm
ex}}_{D}(v)\geq\sqrt{np(1-p)}/\log^{3/4}n\\},$ $\displaystyle A^{-}$
$\displaystyle=A^{-}(D)\coloneqq\\{v\in V(D):{\mbox{\rm
ex}}_{D}(v)\leq-\sqrt{np(1-p)}/\log^{3/4}n\\}\text{ and}$ $\displaystyle
A^{0}$ $\displaystyle=A^{0}(D)\coloneqq V(D)\setminus(A^{+}\cup A^{-}).$

Lemma 5.6 shows that $|A^{0}|=o(n)$, and it is reasonable to expect that
$A^{+}$ and $A^{-}$ have roughly the same size. Even more, we will need the
property that, with high probability, all vertices have roughly the expected
number of neighbours in the sets $A^{+}$ and $A^{-}$, as we show next. The
proof, while rather technical, follows standard martingale arguments and does
not really require any new insights.

######  Lemma 5.7.

There exists a constant $C>0$ such that, for all $C\log n/n\leq p\leq 1-C\log
n/n$, a.a.s. the graph $D=D_{n,p}$ satisfies that, for all $v\in V(D)$,

$e(v,A^{+}),e(v,A^{-}),e(A^{+},v),e(A^{-},v)=np/2\pm
2\sqrt{n/(1-p)}\log^{2}n.$

###### Proof.

Let $V\coloneqq V(D)$, and let $E\coloneqq\\{uv:u,v\in V,u\neq v\\}$. Let
$N\coloneqq\binom{n}{2}=|E|/2$. For each $k\in[n-1]_{0}$, let
$Z_{k}\sim\mathrm{Bin}(k,p)$ and, for each $j\in\mathbb{Z}$, let
$p_{j}^{(k)}\coloneqq\mathbb{P}[Z_{k}=j]$.

We begin by setting some notation. Consider any labelling $e_{1},\ldots,e_{N}$
of all (unordered) pairs of distinct vertices $e=\\{u,u^{\prime}\\}$ with
$u,u^{\prime}\in V$. We will later reveal the edges in succession following
one such labelling. For each $i\in[N]$, let
$e_{i}=\\{u_{i},u_{i}^{\prime}\\}$, define $e_{i}^{1}\coloneqq
u_{i}u_{i}^{\prime}$ and $e_{i}^{2}\coloneqq u_{i}^{\prime}u_{i}$ (the choice
of $e_{i}^{1}$ and $e_{i}^{2}$ is arbitrary), and consider the random variable
$X_{i}\coloneqq(X_{i}^{1},X_{i}^{2})$, where $X_{i}^{1}$ and $X_{i}^{2}$ are
indicator random variables for the events $\\{e_{i}^{1}\in E(D)\\}$ and
$\\{e_{i}^{2}\in E(D)\\}$, respectively. For each $i\in[N]_{0}$, let
$D^{i}\coloneqq(V,E^{i})$, where
$E^{i}\coloneqq\bigcup_{j\in[i]}\\{e_{j}^{1},e_{j}^{2}\\}$. We set
$D^{i}_{\mathrm{cond}}\coloneqq(V,E^{i}_{\mathrm{cond}})$ to be the subdigraph
of $D^{i}$ with
$E^{i}_{\mathrm{cond}}\coloneqq\\{e_{j}^{1}:j\in[i],X_{j}^{1}=1\\}\cup\\{e_{j}^{2}:j\in[i],X_{j}^{2}=1\\}$.
(That is, without conditioning, $D^{i}_{\mathrm{cond}}$ is a random subdigraph
of $D^{i}$ where each edge is retained with probability $p$ independently of
all other edges, and it becomes a deterministic graph after conditioning on
the outcomes of $X_{1},\ldots,X_{i}$.) We also define
$D^{i}_{p}\coloneqq(V,E_{i,p})$, where $E_{i,p}\subseteq E\setminus{E^{i}}$ is
obtained by adding each edge of $E\setminus{E^{i}}$ with probability $p$,
independently of all other edges. In particular, for any $i\in[N]_{0}$ and any
digraph $F$ on $V$ such that $D^{i}_{\mathrm{cond}}\subseteq F$, we have that
$\mathbb{P}[D_{n,p}=F\mid X_{1},\ldots,X_{i}]=\mathbb{P}[D^{i}_{p}=F\setminus
D^{i}_{\mathrm{cond}}]$. For each $i\in[N]_{0}$ and each $v\in V$, we define
$k_{i}(v)\coloneqq n-1-|\\{u\in V:uv\in E^{i}\\}|$. This is the number of
(pairs of) edges incident to $v$ which have not been revealed after revealing
$X_{1},\ldots,X_{i}$. Thus, by Remark 5.4, the variable ${\mbox{\rm
ex}}_{D^{i}_{p}}(v)$ follows a probability distribution which, for each
$j\in\mathbb{Z}$, satisfies that

$\mathbb{P}[{\mbox{\rm
ex}}_{D^{i}_{p}}(v)=j]=\sum_{\ell=0}^{k_{i}(v)}p^{(k_{i}(v))}_{\ell}p^{(k_{i}(v))}_{\ell-j}.$
(5.3)

Observe that, by Lemma 3.9 (in a similar way to (5.1)), for all $i\in[N]_{0}$,
$v\in V$ and $j\in\mathbb{Z}$ we have that

$\mathbb{P}[{\mbox{\rm ex}}_{D^{i}_{p}}(v)=j]\leq
q_{0}^{(k_{i}(v))}\coloneqq\mathbb{P}[{\mbox{\rm
ex}}_{D^{i}_{p}}(v)=0]=\sum_{\ell=0}^{k_{i}(v)}\left(p^{(k_{i}(v))}_{\ell}\right)^{2}.$
(5.4)

Furthermore, observe the following. Choose a vertex $v\in V$ and an index
$i\in[N-1]_{0}$ such that $d^{+}_{D^{i+1}}(v)-d^{+}_{D^{i}}(v)=1$, and let
$a\in\mathbb{Z}$. Then,

$\displaystyle\mathbb{P}[{\mbox{\rm ex}}_{D^{i}_{p}}(v)\geq a+1\mid
X_{1},\ldots,X_{i}]$ $\displaystyle\leq\mathbb{P}[{\mbox{\rm
ex}}_{D^{i+1}_{p}}(v)\geq a\mid X_{1},\ldots,X_{i+1}]$
$\displaystyle\leq\mathbb{P}[{\mbox{\rm ex}}_{D^{i}_{p}}(v)\geq a-1\mid
X_{1},\ldots,X_{i}].$

(Note that the events above are actually independent from the variables upon
which we condition. This notation, however, makes the statement more intuitive
and is what we will require later in the proof.) In particular, this means
that

$\left\lvert\mathbb{P}[{\mbox{\rm ex}}_{D^{i}_{p}}(v)\geq a\mid
X_{1},\ldots,X_{i}]-\mathbb{P}[{\mbox{\rm ex}}_{D^{i+1}_{p}}(v)\geq a\mid
X_{1},\ldots,X_{i+1}]\right\rvert\leq q_{0}^{(k_{i}(v))}.$ (5.5)

(Indeed, we may bound $\mathbb{P}[{\mbox{\rm ex}}_{D^{i+1}_{p}}(v)\geq a\mid
X_{1},\ldots,X_{i+1}]$ by one of the two terms in the previous expression,
which gives us two cases to consider. In either of the cases, the difference
becomes equal to the probability that ${\mbox{\rm ex}}_{D^{i}_{p}}(v)$ takes a
specific value, which is in turn bounded by (5.4).)

Fix a vertex $v\in V$ and reveal all of its in- and outneighbours. Label all
pairs of distinct vertices $e$ as $e_{1},\ldots,e_{N}$ in such a way that,
first, we have all pairs containing $v$, and then the rest, in any arbitrary
order. In particular, we have already revealed the outcome of
$X_{1},\ldots,X_{n-1}$. Let $\mathcal{E}$ be the event that
$d_{D}^{+}(v),d_{D}^{-}(v)=np\pm c\sqrt{np(1-p)\log n}$, where $c$ is the
constant from the statement of Lemma 5.3. By Lemma 5.3, we have that
$\mathbb{P}[\mathcal{E}]\geq 1-1/n^{3}$. Condition on this event. We will
denote probabilities in this conditional space by $\mathbb{P}^{\prime}$, and
expectations by $\mathbb{E}^{\prime}$. Observe that the variables
$X_{n},\ldots,X_{N}$ are independent of $\mathcal{E}$. Then, for all $u\in
N^{+}_{D}(v)$ we have that ${\mbox{\rm ex}}_{D}(u)={\mbox{\rm
ex}}_{D^{n-1}_{\mathrm{cond}}}(u)+{\mbox{\rm ex}}_{D^{n-1}_{p}}(u)$, where
${\mbox{\rm ex}}_{D^{n-1}_{\mathrm{cond}}}(u)=0$ if $u\in N^{-}_{D}(v)$ and
${\mbox{\rm ex}}_{D^{n-1}_{\mathrm{cond}}}(u)=-1$ otherwise, and ${\mbox{\rm
ex}}_{D^{n-1}_{p}}(u)$ follows a probability distribution which, by (5.3), for
each $j\in\\{2-n,\ldots,n-2\\}$ satisfies that

$\mathbb{P}^{\prime}[{\mbox{\rm
ex}}_{D^{n-1}_{p}}(u)=j]=\sum_{\ell=0}^{n-2}p^{(n-2)}_{\ell}p^{(n-2)}_{\ell-j}.$

By a similar argument as the one used to obtain (5.2), i.e., combining (5.4)
and the above with Lemma 5.5 (with $n-2$ playing the role of $n$), it follows
that, for all $u\in V\setminus\\{v\\}$,

$\mathbb{P}^{\prime}[|{\mbox{\rm
ex}}_{D^{n-1}_{p}}(u)|\geq\sqrt{np(1-p)}/\log^{3/4}n]=1-\mathcal{O}(1/\log^{1/4}n)$

and, therefore, one easily deduces (by symmetry and conditioning on the event
that $|{\mbox{\rm ex}}_{D^{n-1}_{p}}(u)|\geq\sqrt{np(1-p)}/\log^{3/4}n$) that

$\mathbb{P}^{\prime}[u\in A^{+}]=1/2-\mathcal{O}(1/\log^{1/4}n).$ (5.6)

Consider the edge-exposure martingale given by the variables
$Y_{i}\coloneqq\mathbb{E}^{\prime}[|A^{+}\cap N^{+}_{D}(v)|\mid
X_{1},\ldots,X_{i}]$, for $i\in[N]\setminus[n-2]$. By (5.6), it follows that
$Y_{n-1},\ldots,Y_{N}$ is a Doob martingale with
$Y_{n-1}=\mathbb{E}^{\prime}[|A^{+}\cap N^{+}_{D}(v)|]=(1\pm 2c\sqrt{(1-p)\log
n/(np)}-\mathcal{O}(1/\log^{1/4}n))np/2$ and $Y_{N}=|A^{+}\cap N^{+}_{D}(v)|$.
In order to prove that $Y_{N}$ is concentrated around $Y_{n-1}$, we need to
bound the martingale differences with a view to applying Lemma 3.8. Observe
that, for all $i\in[N]\setminus[n-2]$, we have that $Y_{i}=\sum_{u\in
N^{+}_{D}(v)}\mathbb{P}^{\prime}[u\in A^{+}\mid X_{1},\ldots,X_{i}]$.

For all $i\in[N-1]\setminus[n-2]$ such that $e_{i+1}\cap
N^{+}_{D}(v)=\varnothing$, we have that $Y_{i+1}=Y_{i}$, and we set

$c_{i}\coloneqq|Y_{i+1}-Y_{i}|=0.$ (5.7)

Consider now any $i\in[N-1]\setminus[n-2]$ such that
$e_{i+1}=\\{u,u^{\prime}\\}$ satisfies that $e_{i+1}\cap
N^{+}_{D}(v)=\\{u\\}$. Then,

$\displaystyle Y_{i+1}-Y_{i}$ $\displaystyle=\mathbb{P}^{\prime}[u\in
A^{+}\mid X_{1},\ldots,X_{i+1}]-\mathbb{P}^{\prime}[u\in A^{+}\mid
X_{1},\ldots,X_{i}]$ $\displaystyle=\mathbb{P}^{\prime}[{\mbox{\rm
ex}}_{D}(u)\geq\sqrt{np(1-p)}/\log^{3/4}n\mid X_{1},\ldots,X_{i+1}]$
$\displaystyle\ \ \ \qquad\qquad-\mathbb{P}^{\prime}[{\mbox{\rm
ex}}_{D}(u)\geq\sqrt{np(1-p)}/\log^{3/4}n\mid X_{1},\ldots,X_{i}]$
$\displaystyle=\mathbb{P}^{\prime}[{\mbox{\rm
ex}}_{D^{i+1}_{p}}(u)\geq\sqrt{np(1-p)}/\log^{3/4}n-{\mbox{\rm
ex}}_{D^{i+1}_{\mathrm{cond}}}(u)\mid X_{1},\ldots,X_{i+1}]$ $\displaystyle\ \
\ \qquad\qquad-\mathbb{P}^{\prime}[{\mbox{\rm
ex}}_{D^{i}_{p}}(u)\geq\sqrt{np(1-p)}/\log^{3/4}n-{\mbox{\rm
ex}}_{D^{i}_{\mathrm{cond}}}(u)\mid X_{1},\ldots,X_{i}],$

so by (5.4) and (5.5), and using the fact that $|{\mbox{\rm
ex}}_{D^{i+1}_{\mathrm{cond}}}(u)-{\mbox{\rm
ex}}_{D^{i}_{\mathrm{cond}}}(u)|\leq 1$, we conclude that

$|Y_{i+1}-Y_{i}|\leq 2q_{0}^{(k_{i}(u))}\eqqcolon c_{i}.$ (5.8)

Finally, for any $i\in[N-1]\setminus[n-2]$ such that
$e_{i+1}=\\{u,u^{\prime}\\}\subseteq N^{+}_{D}(v)$, one can similarly show
that

$|Y_{i+1}-Y_{i}|\leq
2(q_{0}^{(k_{i}(u))}+q_{0}^{(k_{i}(u^{\prime}))})\eqqcolon c_{i}.$ (5.9)

This covers all the range of $i\in[N-1]\setminus[n-2]$.

By combining (5.7)–(5.9), we observe that, for each $u\in N^{+}(v)$ and each
$k\in[n-2]$, the value $q_{0}^{(k)}$ appears as part of $c_{i}$ for exactly
one value of $i\in[N-1]\setminus[n-2]$. Then, we have

$\sum_{i=n-1}^{N-1}c_{i}^{2}\leq\sum_{u\in
N_{D}^{+}(v)}\sum_{k=1}^{n-2}8\left(q_{0}^{(k)}\right)^{2},$

where we have used the fact that $(x+y)^{2}\leq 2x^{2}+2y^{2}$. Now, using
Lemma 5.5 and the conditioning on $\mathcal{E}$, we have that

$\sum_{i=n-1}^{N-1}c_{i}^{2}\leq\left(1\pm c\sqrt{\frac{(1-p)\log
n}{np}}\right)8K^{2}np\left(1+\sum_{k=2}^{n-2}\frac{\log
k}{kp(1-p)}\right)=\mathcal{O}\left(\frac{n\log^{2}n}{(1-p)}\right).$

Therefore, we can apply Lemma 3.8 to conclude that

$\mathbb{P}^{\prime}[|A^{+}\cap N_{D}^{+}(v)|\neq np/2\pm
2\sqrt{n/(1-p)}\log^{2}n]=e^{-\Omega(\log^{2}n)}.$ (5.10)

By similar arguments, we can show that

$\displaystyle\mathbb{P}^{\prime}[|A^{-}\cap N_{D}^{+}(v)|\neq np/2\pm
2\sqrt{n/(1-p)}\log^{2}n]=e^{-\Omega(\log^{2}n)},$ (5.11)
$\displaystyle\mathbb{P}^{\prime}[|A^{+}\cap N_{D}^{-}(v)|\neq np/2\pm
2\sqrt{n/(1-p)}\log^{2}n]=e^{-\Omega(\log^{2}n)},$ (5.12)
$\displaystyle\mathbb{P}^{\prime}[|A^{-}\cap N_{D}^{-}(v)|\neq np/2\pm
2\sqrt{n/(1-p)}\log^{2}n]=e^{-\Omega(\log^{2}n)}.$ (5.13)

Let $\mathcal{E}^{\prime}$ be the event that $|A^{+}\cap
N_{D}^{+}(v)|,|A^{-}\cap N_{D}^{+}(v)|,|A^{+}\cap N_{D}^{-}(v)|,|A^{-}\cap
N_{D}^{-}(v)|=np/2\pm 2\sqrt{n/(1-p)}\log^{2}n$. By combining (5.10)–(5.13)
with a union bound, it follows that
$\mathbb{P}^{\prime}[\mathcal{E}^{\prime}]=1-e^{-\Omega(\log^{2}n)}$.
Therefore, $\mathbb{P}[\mathcal{E}^{\prime}]\geq 1-2/n^{3}$. Finally, the
statement follows by a union bound over all vertices $v\in V$. ∎

###### Proof of Theorem 5.1.

Condition on the event that the statements of Lemmas 5.2, 5.3, 5.6 and 5.7
hold, which occurs a.a.s. Then, Lemma 5.2 directly implies $(\mathrm{P}5)$
holds. We may partition the vertices by defining $A^{+}\coloneqq\\{v\in
V(D):{\mbox{\rm ex}}_{D}(v)\geq 155\kappa\\}$, $A^{-}\coloneqq\\{v\in
V(D):{\mbox{\rm ex}}_{D}(v)\leq-155\kappa\\}$ and $A^{0}\coloneqq
V(D)\setminus(A^{+}\cup A^{-})$. In particular, by Lemma 5.6 we have that
$|A^{0}|$ is sublinear. The condition on the excess in $(\mathrm{P}1)$ and
$(\mathrm{P}2)$ holds now by definition. The conditions on the edge
distribution in $(\mathrm{P}1)$ and $(\mathrm{P}2)$ as well as $(\mathrm{P}4)$
follow by Lemma 5.7 in the given range of $p$. Finally, $(\mathrm{P}3)$ holds
by combining Lemma 5.3 and Lemma 5.7. ∎

##  6\. Conclusion

We have shown in Theorem 1.2 that, for $p$ in the range $n^{-1/3}\log^{4}n\leq
p\leq 1-n^{-1/5}\log^{5/2}n$, a.a.s. $D_{n,p}$ is consistent. Of course, we
should expect to be able to improve this range, particularly the lower bound,
and perhaps even no lower bound is necessary. Indeed, when $p\ll 1/n$, we know
$D_{n,p}$ is acyclic, and it is easy to see that acyclic digraphs are
consistent (simply iteratively remove maximal length paths and observe that
the excess decreases by $1$ each time).

The bottleneck in our current approach is in Lemma 4.11 where we process
medium length cycles. An improvement in the bounds there would lead to an
improvement in the range of $p$ in Theorem 1.2. However this alone can only
achieve a lower bound for $p$ of approximately $n^{-1/2}$: beyond that one
needs to improve other aspects of the argument and new ideas are necessary.

Finally, we saw that our methods can be used to show that a fairly broad class
of digraphs (that are far from pseudorandom) are consistent; see Theorem 1.3
and Theorem 4.3. It would be interesting to find other classes of digraphs
that are consistent.

## References

  * Alon and Spencer [2016] N. Alon and J. H. Spencer, _The probabilistic method_. Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 4th ed. (2016), ISBN 978-1-119-06195-3.
  * Alspach, Mason and Pullman [1976] B. Alspach, D. W. Mason and N. J. Pullman, Path numbers of tournaments. _J. Comb. Theory, Ser. B_ 20 (1976), 222–228, doi: 10.1016/0095-8956(76)90013-7.
  * Csaba, Kühn, Lo, Osthus and Treglown [2016] B. Csaba, D. Kühn, A. Lo, D. Osthus and A. Treglown, Proof of the 1-factorization and Hamilton decomposition conjectures. _Mem. Amer. Math. Soc._ 244 (2016), v+164, doi: 10.1090/memo/1154.
  * Erdős and Wilson [1977] P. Erdős and R. J. Wilson, On the chromatic index of almost all graphs. _J. Combinatorial Theory Ser. B_ 23.2-3 (1977), 255–257, doi: 10.1016/0003-4916(63)90266-5.
  * Ford and Fulkerson [1956] L. R. Ford and D. R. Fulkerson, Maximal Flow Through a Network. _Canadian Journal of Mathematics_ 8 (1956), 399–404, doi: 10.4153/CJM-1956-045-5.
  * Frieze, Jackson, McDiarmid and Reed [1988] A. M. Frieze, B. Jackson, C. J. H. McDiarmid and B. Reed, Edge-colouring random graphs. _J. Combin. Theory Ser. B_ 45.2 (1988), 135–149, doi: 10.1016/0095-8956(88)90065-2.
  * Girão, Granet, Kühn, Lo and Osthus [2020] A. Girão, B. Granet, D. Kühn, A. Lo and D. Osthus, Path decompositions of tournaments. _arXiv e-prints_ (2020). arXiv: 2010.14158.
  * Hardy, Littlewood and Pólya [1988] G. H. Hardy, J. E. Littlewood and G. Pólya, _Inequalities_. Cambridge Mathematical Library, Cambridge University Press, Cambridge (1988), ISBN 0-521-35880-9. Reprint of the 1952 edition.
  * Haxell, Krivelevich and Kronenberg [2019] P. Haxell, M. Krivelevich and G. Kronenberg, Goldberg’s conjecture is true for random multigraphs. _J. Combin. Theory Ser. B_ 138 (2019), 314–349, doi: 10.1016/j.jctb.2019.02.005.
  * Huang, Ma, Shapira, Sudakov and Yuster [2013] H. Huang, J. Ma, A. Shapira, B. Sudakov and R. Yuster, Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs. _Comb. Probab. Comput._ 22.6 (2013), 859–873, doi: 10.1017/S0963548313000394.
  * Janson, Łuczak and Ruciński [2000] S. Janson, T. Łuczak and A. Ruciński, _Random graphs_. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York (2000), ISBN 0-471-17541-2, doi: 10.1002/9781118032718.
  * Knierim, Larcher, Martinsson and Noever [2021] C. Knierim, M. Larcher, A. Martinsson and A. Noever, Long cycles, heavy cycles and cycle decompositions in digraphs. _J. Comb. Theory, Ser. B_ 148 (2021), 125–148, doi: 10.1016/j.jctb.2020.12.008.
  * Krivelevich [1997] M. Krivelevich, Triangle factors in random graphs. _Comb. Probab. Comput._ 6.3 (1997), 337–347, doi: 10.1017/S0963548397003106.
  * Kühn and Osthus [2013] D. Kühn and D. Osthus, Hamilton decompositions of regular expanders: A proof of Kelly’s conjecture for large tournaments. _Adv. Math._ 237 (2013), 62–146, doi: 10.1016/j.aim.2013.01.005.
  * Kühn and Osthus [2014] ———, Hamilton decompositions of regular expanders: applications. _J. Comb. Theory, Ser. B_ 104 (2014), 1–27, doi: 10.1016/j.jctb.2013.10.006.
  * Lo, Patel, Skokan and Talbot [2020] A. Lo, V. Patel, J. Skokan and J. Talbot, Decomposing tournaments into paths. _Proc. Lond. Math. Soc. (3)_ 121.2 (2020), 426–461, doi: 10.1112/plms.12328.
  * Rödl, Ruciński and Szemerédi [2006] V. Rödl, A. Ruciński and E. Szemerédi, A Dirac-type theorem for 3-uniform hypergraphs. _Comb. Probab. Comput._ 15.1-2 (2006), 229–251, doi: 10.1017/S0963548305007042.
  * de Vos [2020] T. de Vos, _Decomposing directed graphs into paths_. Master’s thesis, Universiteit van Amsterdam (2020).