###### Proof.

###### Separating paths systems of almost linear size

###### Abstract

A _separating path system_ for a graph $G$ is a collection $\mathcal{P}$ of
paths in $G$ such that for every two edges $e$ and $f$ in $G$, there is a path
in $\mathcal{P}$ that contains $e$ but not $f$. We show that every $n$-vertex
graph has a separating path system of size $O(n\log^{\star}n)$. This improves
upon the previous best upper bound of $O(n\log n)$, and makes progress towards
a conjecture of Falgas-Ravry–Kittipassorn–Korándi–Letzter–Narayanan and
Balogh–Csaba–Martin–Pluhár, according to which an $O(n)$ bound should hold.

##  1 Introduction

Given a set $A$ and a family $\mathcal{F}$ of sets, we say that $\mathcal{F}$
is a _strongly-separating system_ for $A$, or that $\mathcal{F}$ _strongly-
separates_ $A$, if for every two elements $a,b\in A$ there is a set
$S\in\mathcal{F}$ satisfying $a\in S$ and $b\notin S$. Similarly, we that
$\mathcal{F}$ is a _weakly-separating_ system for $A$, or that $\mathcal{F}$
_weakly-separates_ $A$, if for every two elements $a,b\in A$ there is a set
$S\in\mathcal{F}$ that contains exactly one of $a$ and $b$.111The notion of
weak separation is sometimes referred to, simply, as _separation_. We keep the
word ‘weak’ in the definition, as our focus will be on the strong version. In
particular, if $\mathcal{F}$ strongly-separates $A$ then every element of $A$
is in some set in $\mathcal{F}$, and if it weakly-separates $A$ then there is
at most one element in $A$ not contained in any set in $\mathcal{F}$.

The notion of separation was introduced by Rényi [35] in 1961. It is easy to
see that the smallest weakly-separating system for a set of size $n$ has size
$\left\lceil\log_{2}n\right\rceil$, and that the smallest strongly-separating
system has size $(1+o(1))\log_{2}n$ (see [36]). The problem of determining the
size of a smallest separating system becomes more interesting when one imposes
restrictions on the members of the separating system. For example, separating
systems with restrictions on the size of their members were studied in [24,
40, 34, 28], and different extremal questions about separating systems were
studied in [5, 6, 18].

Another interesting direction is to consider separating systems where the
ground set is a graph and the members of the separating system satisfy some
graph theoretic properties; see [8, 17, 16, 23] for extremal examples [37, 38,
19] for algorithmic examples. Our focus will be on _separating path systems_ ,
where the ground set is the set of edges of a given graph $G$ and the members
of the separating system are paths in $G$. This variant was proposed by Gyula
Katona in the $5^{\text{th}}$ Emléktábla Workshop (2013). Define
$\operatorname{sep}^{*}(G)$ to be the size of a smallest weakly-separating
path system for $G$, and let $\operatorname{sep}^{*}(n)$ be the maximum of
$\operatorname{sep}^{*}(G)$ over all $n$-vertex graphs $G$; define
$\operatorname{sep}(G)$ and $\operatorname{sep}(n)$ analogously for strongly-
separating path systems. Katona asked to determine
$\operatorname{sep}^{*}(n)$.

Separating path systems were first studied by Falgas-
Ravry–Kittipassorn–Korándi–Narayanan and the author [12], who focused on the
weak version, and, independently, by Balogh–Csaba–Martin–Pluhár [3], who
focused on the strong version. Both groups considered path separation in
various classes of graphs, including random graphs and trees. Moreover, both
groups conjectured that the answer to Katona’s question is
$O(n)$.222Balogh–Csaba–Martin–Pluhár’s version is slightly stronger because
they use the stronger notion of separation; we suspect the two variants are
equally hard.

######  Conjecture 1.1 (Falgas-Ravry–Kittipassorn–Korándi–Letzter–Narayanan
[12] and Balogh–Csaba–Martin–Pluhár [3]).

There exists a constant $c$ such that every graph on $n$ vertices has a
(weakly- or strongly-)separating path system of size at most $cn$.

In fact, Falgas-Ravry–Kittipassorn–Korándi–Letzter–Narayanan [12] make the
bold suggestion that perhaps, for weak separation, $c$ could be taken to be
arbitrarily close to $1$, for sufficiently large $n$. If true, that would be
tight, as can be seen by considering the complete graph $K_{n}$. In fact,
determining $\operatorname{sep}^{*}(K_{n})$ and $\operatorname{sep}(K_{n})$
seems hard; see Wickes [41] for the best-known upper bound on
$\operatorname{sep}^{*}(K_{n})$.

The study of separating path systems of graphs is related to the well-
researched topic of path decompositions. A famous conjecture of Gallai asserts
that every connected graph on $n$ vertices can be decomposed into at most
$\left\lfloor\frac{n+1}{2}\right\rfloor$ paths; here by _decomposition_ we
mean that each edge is covered exactly once. A fundamental result of Lovász
[33] proves the following slightly weaker version of Gallai’s conjecture.

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

Every $n$-vertex graph can be decomposed into at most $n/2$ paths and cycles.
Consequently, every $n$-vertex graph can be decomposed into at most $n$ paths.

Theorem 1.2 will play an important role in our proof. We sometimes use instead
its following easy corollary.

######  Corollary 1.3.

Every $n$-vertex graph can be decomposed into at most $e(G)/d+n$ paths of
length at most $d$.

###### Proof.

By Theorem 1.2, there is a collection $\mathcal{P}$ of at most $n$ paths that
decomposes the edges of $G$. Decompose each path in $\mathcal{P}$ into paths
of length $d$ and at most one shorter path. We thus obtain a decomposition $G$
into paths of length at most $d$, at most $n$ of which have length shorter
than $d$. The corollary follows as there can be at most $e(G)/d$ pairwise
edge-disjoint paths of length $d$. ∎

The currently best-known bounds towards Gallai’s conjecture are due to,
independently, Dean–Kouider [9] and Yan [42], who proved that every $n$-vertex
graph can be decomposed into at most $\frac{2n}{3}$ paths. The conjecture was
proved to hold for various families of graphs; see Blanché–Bonamy–Bonichon [4]
for a proof for connected planar graphs and the citations therein for other
families of graphs.

Theorem 1.2 implies an upper bound of $\operatorname{sep}(n)=O(n\log n)$.
Indeed, given an $n$-vertex graph $G$, let $\mathcal{H}$ be a collection of
$O(\log n)$ subgraphs of $G$ that separate the edges of $G$; this exists by an
aforementioned result regarding separating a set without underlying structure.
Now decompose each $H\in\mathcal{H}$ into at most $n$ paths. This yields a
collection of $O(n\log n)$ paths separating $G$. Until now, this was the best-
known general upper bound on $\operatorname{sep}(n)$. In this paper we improve
it significantly, showing that $\operatorname{sep}(n)=O(n\log^{\star}n)$. Here
$\log^{\star}n$ is the iterated logarithm, namely the minimum number of times
the base-$2$ logarithm has to be applied, iteratively, to yield a result which
is smaller than $1$.

######  Theorem 1.4.

Every $n$-vertex graph has a strongly-separating path system of size
$O(n\log^{\star}n)$. That is, $\operatorname{sep}(n)=O(n\log^{\star}n)$.

A key component in this paper is the use of sublinear expanders. These were
introduced by Komlós–Szemerédi [26, 27] and recently various variants of them
were used to prove some interesting results [13, 14, 15, 29, 20, 21, 22, 25,
30, 31, 32, 7]. Specifically, we will use many ideas from a very recent paper
by Bucić–Montgomery [7], who proved that every $n$-vertex graph can be
decomposed into $O(n\log^{\star}n)$ cycles and edges. This is significant
progress on the Erdős–Gallai conjecture [10], asserting that every $n$-vertex
graph can be decomposed into $O(n)$ cycles and edges. We will also use a tool
from [31], where Liu and Montgomery solved the so-called odd cycle problem,
due to Erdős–Hajnal [11].

In the following section, Section 2, we give an overview of the proof and an
outline of the structure of the paper. We remark that, as our focus throughout
the paper is on strong separation, from now on we will refer to it simply as
_separation_.

##  2 Proof overview

The main purpose of this section is to give an overview of the proof of
Theorem 1.4. We will first describe a general strategy for finding small
separating path systems (see Section 2.1), we then show how sublinear
expanders come into play (Section 2.2), and we give a more detailed proof
overview in Section 2.3. At the end of the section we outline the structure of
the paper (see Section 2.4) and define some notation (in Section 2.5).

###  2.1 A general strategy

We start by describing a general strategy for finding a separating path system
for a graph $G$ on $n$ vertices, which was used in [12]. By Theorem 1.2, there
is a collection $\mathcal{P}$ of at most $n$ paths that decomposes $G$; for an
edge $e$, denote by $P(e)$ the unique path in $\mathcal{P}$ that contains $e$.
We claim that there is a collection $\mathcal{M}$ of at most $3n$ matchings
that decomposes $G$, such that $\mathcal{P}\cup\mathcal{M}$ separates the
edges of $G$.

Indeed, take $\mathcal{M}$ to be a collection of $3n$ pairwise edge-disjoint
matchings, whose matchings intersect each path in $\mathcal{P}$ in at most one
edge, and that covers a maximum number of edges under these conditions.
Suppose that $e$ is an edge in $G$ which is not covered by any of the
matchings in $\mathcal{M}$. Notice that there are at most $n-1$ matchings in
$\mathcal{M}$ that contain edges of $P(e)$, and at most $2(n-1)$ matchings in
$\mathcal{M}$ that contain an edge that intersects $e$. Hence, there is a
matching $M\in\mathcal{M}$ that contains neither edges of $P(e)$ nor edges
that intersect $e$. Replacing $M$ by $M\cup\\{e\\}$, we reach a contradiction
to the maximality of $\mathcal{M}$, thus showing that $\mathcal{M}$ covers all
edges in $G$. Observe that $\mathcal{P}\cup\mathcal{M}$ separates the edges of
$G$. Indeed, defining $M(e)$ to be the unique matching in $\mathcal{M}$ that
contains the edge $e$, we see that for any two edges $e$ and $f$, one of
$P(e)$ and $M(e)$ contains $e$ but not $f$.

Thus, if we could find a path $P_{M}$, for each $M\in\mathcal{M}$, that
contains $M$ but avoids all other edges of $\bigcup_{e\in M}P(e)$, then we
would obtain a separating path system for $G$ whose size is
$|\mathcal{P}|+|\mathcal{M}|\leq 4n$.

Of course, this strategy does not always work; otherwise we would have been
able to improve on our main result, Theorem 1.4. Nevertheless, if $G$ is has
expansion properties and we impose additional restrictions on the matchings in
$\mathcal{M}$, then this strategy often succeeds. Indeed, in [12] it was used
to show that, with high probability, the random graph $G(n,p)$ has a weakly-
separating path system of size $O(n)$ for every $p=p(n)$ (similar ideas appear
in [3], where the authors found much smaller strongly-separating path systems
when $p\geq\frac{1000n}{\log n}$). In this paper we apply it to a more general
class of expanders.

###  2.2 Expanders

The exact notions of expansion that we shall use will be introduced later (see
Sections 4 and 5). We mention that they are variants of the ‘sublinear
expanders’, which were introduced by Komlós and Szemrédi [26, 27], and have
since been modified in various ways to prove many interesting results [13, 14,
15, 29, 20, 21, 22, 25, 30, 31, 32, 7]. As their name suggests, such expanders
have a fairly weak expansion property. Their strength is in their
omnipresence: every graph with a sufficiently large (but possibly still
constant) average degree contains a sublinear expander. In fact, Bucić and
Montgomery [7] recently showed that every graph can be decomposed (or almost
decomposed, if we want the expanders to be ‘robust’) into sublinear expanders
that, on average, cover each vertex a constant number of times. This is very
useful for us; it shows that, essentially, it suffices to be able to find
separating path systems of linear size in expanders.

With this decomposition-into-expanders result at hand, a rough plan would be
to apply it to decompose a given graph into expanders, and then find a linear
separating path system for each expander using the strategy above. If this
plan could be realised as stated, then we would end up with a linear
separating path system for the original graph. However, depending on the
density of the expanders we find, we sometimes require them to be ‘robust’ (or
‘somewhat robust’), and then some edges might remain uncovered. Moreover, in
some situations, our methods separate almost all, but not all, edges of a
given expander. Instead, we perform $O(\log^{\star}n)$ steps, each time
significantly decreasing the number of unseparated edges, until remaining with
$O(n)$ edges that we can separate trivially by individual edges.

###  2.3 Proof sketch

We now give a more concrete outline of our proof. Our main task is to prove
that, given a graph $G$ on $n$ vertices and with average degree $d$, there is
a subgraph $G_{1}$ on $O(n\operatorname{polylog}d)$ edges and a collection of
$O(n)$ paths in $G$ that separates the edges of $G-G_{1}$. Iterating this
yields a separating path system for $G$ of size $O(n\log^{\star}n)$. We
complete this task in three steps.

#### Step 1: dense expanders.

We show (in Lemma 3.1) that given a graph $J$ on $m$ vertices, it has a
subgraph $J_{1}$ of size $O(m\operatorname{polylog}m)$ such that $J-J_{1}$ can
be separated using $O(m)$ paths. To do so, we decompose $J$ into ‘robust’
expanders (with total order $O(m)$) and a remainder of size
$O(m\operatorname{polylog}m)$ and show that such expanders can be separated
using a linear number of paths (in Corollary 6.4).

To separate a robust expander $K$, we show that if $V$ is a set of vertices in
$K$ that includes each vertex with probability $1/3$, then, with high
probability, the edges of $K-V$ can be separated by a linear number of paths.
To find these paths, we apply the strategy given in Section 2.1 to $K-V$, to
obtain small collections $\mathcal{P}$ of paths and $\mathcal{M}$ of matchings
that together separate the edges of $G$, while imposing a certain degree
condition on the matchings in $\mathcal{M}$. We then partially connect the
edges of each $M\in\mathcal{M}$ using a subset $V_{1}$ of $V$, chosen
uniformly at random, thereby forming a path forest whose ends ‘expand well’
into $V-V_{1}$. Now, we adapt a result from [7] (which in turn uses ideas from
a paper of Tomon [39]) that allows for connecting pairs of vertices,
disjointly, via a random set of vertices.

#### Step 2: separating edges touching large degrees in sparse expanders.

We again start by decomposing a graph $G$ on $n$ vertices and with averaged
degree $d$ into expanders (here the expanders are not required to be robust,
and so we have no uncovered edges), whose sum of orders is $O(n)$. For each
such expander $H$, we show (in Lemma 8.1) that its edges touching high degree
vertices can be separated using $O(n+\frac{e(H)}{d})$ paths.

Denoting by $L$ the set of large degree vertices in $H$, let us explain how to
separate the edges in $H[L]$. Writing $k:=n+\frac{e(H)}{d}$, we apply the
strategy in Section 2.1, while additionally requiring that the paths in
$\mathcal{P}$ and matchings in $\mathcal{M}$ have size at most $d$; it is
straightforward to show that there exist appropriate $\mathcal{P}$ and
$\mathcal{M}$ of size $O(k)$. Now, given a matching $M\in\mathcal{M}$, let $F$
be a path forest that extends $M$, avoids vertices in $X:=\bigcup_{e\in
M}V(P(e))-V(M)$, and under these conditions has as few components as possible,
and as few edges as possible (prioritising the former). Suppose, towards a
contradiction, that there are at least two components, and let $u$ and $v$ be
leaves of distinct components of $F$. The minimality assumption allows us to
show that, roughly speaking, balls around $u$ in $H-X$ have few neighbours in
$F$. Adapting a lemma from Liu–Montgomery [31], it follows that more than
$|H|/2$ vertices in $H$ can be reached from $u$ in $H-(X\cup V(F)-\\{u\\})$,
exploiting the fact that $u$ has a large degree. Since the same holds for $v$,
it follows that $F$ can be extended by a path from $u$ to $v$, a
contradiction. Thus $F=F_{M}$ is a path that extends $M$ and avoids other
edges from $\bigcup_{e\in M}P(e)$, and
$\\{F_{M}:M\in\mathcal{M}\\}\cup\mathcal{P}$ is a collection of $O(k)$ paths
separating $G[L]$.

In fact, similar reasoning can be applied to separate edges $xy$ where $x\in
L$ and $y$ has at least four neighbours in $L$, by allowing the members of
$\mathcal{M}$ to contain paths of length $2$ whose ends are in $L$.

#### Step 3: separating almost all remaining edges in $H$.

For each $H$ as in the previous step, let $F$ be its subgraph of ‘unseparated
edges’; so $F$ has small maximum degree. We now decompose $F$ into ‘somewhat
robust’ expanders (with total order $O(|H|)$) and a remainder of
$O(\operatorname{polylog}d\cdot|H|)$ edges. Consider one of these expanders
$J$. If $|J|$ is fairly large with respect to $d$ (namely, if $|J|\geq
2^{(\log d)^{7})}$) then we show (in Lemma 8.4) that its edges can be
separated using $O(|J|)$ edges.

The proof is similar to the one outlined in Step 2. Here, in addition to
requiring the paths and matchings in $\mathcal{P}$ and $\mathcal{M}$ to have
size at most $d$, we also require the edges in $\mathcal{M}$ to be far from
each other (the assumption that $|J|$ is large with respect to $d$ is used to
prove that appropriate $\mathcal{M}$ exists). Defining $M$, $X$ and $F$ as
above, it suffices to show that $F$ has just one component. To this end,
taking $u$ to be a leaf in $F$, we first show that the ball of radius $(\log
d)^{5}$ around $u$ in $J^{\prime}:=J-(X\cup V(F)-\\{u\\})$ is large,
exploiting the expansion property being ‘somewhat robust’ and the fact that
the other edges of $M$ are far from $u$. We then proceed like in the previous
step to expand $u$ further, and reach a contradiction if $F$ has at least two
components. As before, this implies the existence of a separating path system
for $J$ of size $O(|J|+\frac{e(J)}{d})$.

If instead $|J|\leq 2^{(\log d)^{7}}$, we apply the first step to show that
all but $O(|J|\operatorname{polylog}|J|)$ edges of $J$ can be separated using
$O(|J|)$ paths.

Altogether, we get a collection of $O(n)$ paths that separate all but
$O(n\operatorname{polylog}d)$ edges of the graph $G$ that we started with at
the beginning of the second step, concluding the iterative step.

###  2.4 Organisation of the paper

In the next section (Section 3) we state two key lemmas — Lemma 3.1, which
covers Step 1 above, and Lemma 3.2, which covers Steps 2 and 3 — and show how
our main theorem (Theorem 1.4) follows from these lemmas. In Section 4 we
state and prove the decomposition-into-expanders lemma, Lemma 4.1, which will
be used in the proofs of both key lemmas. Section 5 contains the proof of
Lemma 5.10, which allows for connecting pairs of vertices in an expander
disjointly through a random set of vertices, and is a variant of a lemma from
[7]. The first key lemma (Lemma 3.1) is then proved in Section 6. In Section 7
we prove a variant of a lemma from [31] regarding expansion with forbidden
sets. Finally, in Section 8 we prove the second key lemma (Lemma 3.2).

###  2.5 Notation

Our notation is mostly standard. Given a graph $G$, a set of vertices $X$, and
integer $i\geq 0$, we write $N_{G}(X)$ to be the set of vertices outside of
$X$ that send at least one edge into $X$, and write $B^{i}_{G}(X)$ to be the
set of vertices at distance at most $i$ from $X$ in $G$. Given a vertex $x$
and a set of vertices $X$ in a graph $G$, we denote the number of neighbours
of $x$ in $X$ by $d_{G}(x,X)$. As is customary, we omit the subscript $G$ when
it is clear from the context. Given vertices $x,y$, an _$(x,y)$ -path_ is a
path from $x$ to $y$. We denote the length of a path $P$ by $\ell(P)$. We say
that a sequence of events $(E_{n})_{n\geq 1}$ holds _with high probability_ if
it holds with probability tending to $1$ as $n$ tends to infinity. All
logarithms will be in base $2$, and $\log^{\star}n$ is _iterated logarithm_ ,
namely the least number of times the base-$2$ logarithms has to be applied,
iteratively and starting with $n$, to yield a number which is smaller than
$1$. When dealing with large numbers we often omit floor and ceiling signs
when they are not crucial.

##  3 Main lemmas

In this section we state two key lemmas and then show how to use them to prove
our main result (Theorem 1.4).

The first key lemma shows that given any graph on $n$ vertices there is a
linear collection of paths separating all but $O(n\operatorname{polylog}n)$ of
its edges.

######  Lemma 3.1.

Suppose that $G$ is a graph on $n$ vertices. Then there is a subgraph
$G_{1}\subseteq G$, with $e(G_{1})\leq n(\log n)^{55}$, and a collection
$\mathcal{P}$ of at most $1300n$ paths in $G$ that separates the edges of
$G-G_{1}$.

The second key lemma has a more complicated statement; essentially, it shows
that for every graph $G$ there is a linear collection of paths that separates
a subgraph of $G$ whose complement in $G$ can be decomposed into dense
subgraphs and a small remainder.

######  Lemma 3.2.

There exists $d_{0}$ such that the following holds. Suppose that $G$ is a
graph on $n$ vertices with average degree $d$, where $d\geq d_{0}$. Then there
is a subgraph $G_{1}\subseteq G$, a collection $\mathcal{H}$ of subgraphs of
$G$ and a collection $\mathcal{P}$ of paths in $G$ with the following
properties.

  1. (1)

The graphs in $\mathcal{H}$ are mutually edge-disjoint; $|H|\leq 2^{(\log
d)^{7}}$ for every $H\in\mathcal{H}$; and $\sum_{H\in\mathcal{H}}|H|\leq 4n$.

  2. (2)

The collection $\mathcal{P}$ separates the edges of
$G-G_{1}-\bigcup_{H\in\mathcal{H}}H$, and satisfies $|\mathcal{P}|\leq 80n$.

  3. (3)

The graph $G_{1}$ has average degree at most $(\log d)^{3}$.

The following corollary combines the two key lemmas to show that given a graph
with average degree $d$, there is a linear collection of paths that separates
all edges but a remainder whose average degree is
$O(\operatorname{polylog}d)$.

######  Corollary 3.3.

Suppose that $G$ is a graph on $n$ vertices with average degree $d$. Then
there is a subgraph $G_{1}\subseteq G$ with average degree at most $O((\log
d)^{420})$ and a collection $\mathcal{P}$ of $O(n)$ paths in $G$ that
separates $G-G_{1}$.

###### Proof.

We may assume that $d$ is large, because otherwise we could take $G_{1}$ to be
the empty graph and $\mathcal{P}=E(G)$. Apply Lemma 3.2 to obtain
$\mathcal{H}$ and $\mathcal{P}$ that satisfy the conditions of the lemma.
Namely, the graphs in $\mathcal{H}$ are mutually edge-disjoint and consist of
at most $2^{(\log d)^{7}}$ vertices, $\sum_{H\in\mathcal{H}}|H|\leq 4n$,
$|\mathcal{P}|\leq 68n$, and the paths in $\mathcal{P}$ separate the edges in
$G^{\prime}$, where
$G^{\prime}:=G-G^{\prime\prime}-\bigcup_{H\in\mathcal{H}}H$ and
$G^{\prime\prime}$ is a subgraph of $G^{\prime}$ with average degree $O((\log
n)^{3})$. Let $\mathcal{P}^{\prime}$ be a collection of at most $n$ paths in
$G^{\prime}$ that decomposes the edges of $G^{\prime}$; such a collection
exists by Theorem 1.2.

Apply Lemma 3.1 to each graph $H$ in $\mathcal{H}$; denote the resulting
subgraph and collection of paths by $G_{H}$ and $\mathcal{P}_{H}$. So
$e(G_{H})\leq|H|(\log|H|)^{60}$, $|\mathcal{P}_{H}|=O(|H|)$, and
$\mathcal{P}_{H}$ is a collection of paths in $H$ that separates the edges of
$H-G_{H}$. Write $G_{1}:=\bigcup_{H\in\mathcal{H}}G_{H}\cup G^{\prime\prime}$.
Then

$\displaystyle\sum_{H\in\mathcal{H}}e(G_{H})\leq\sum_{H\in\mathcal{H}}|H|(\log|H|)^{60}\leq\left(\sum_{H\in\mathcal{H}}|H|\right)\cdot(\log
d)^{420}=O(n(\log d)^{420}).$

It follows that $e(G_{1})=O(n(\log n)^{420})$, or, equivalently, $G_{1}$ has
average degree $O((\log d)^{420})$. Let $\mathcal{P}^{\prime}_{H}$ be a
collection of at most $|H|$ paths in $H$ that decomposes $E(H)$, and write
$\mathcal{Q}:=\mathcal{P}\cup\mathcal{P}^{\prime}\cup\bigcup_{H\in\mathcal{H}}(\mathcal{P}_{H}\cup\mathcal{P}^{\prime}_{H})$.
Then $|Q|=O(n)$, using $\sum_{H\in\mathcal{H}}|H|=O(n)$.

We claim that $\mathcal{Q}$ separates the edges of $G-G_{1}$. To see this,
consider two edges $e$ and $f$ in $G-G_{1}$. We consider four cases.

  * •

There is $H\in\mathcal{H}$ such that $e,f\in E(H)$. Then, there is
$P\in\mathcal{P}_{H}$ such that $e\in E(P)$ and $f\notin E(P)$.

  * •

There is $H\in\mathcal{H}$ such that $e\in E(H)$ and $f\notin E(H)$. Then,
there is a path $P\in\mathcal{P}_{H}^{\prime}$ in $H$ that contains $e$, and
so $f\notin E(P)$.

  * •

Both $e$ and $f$ are in $G^{\prime}$. Then, there is $P\in\mathcal{P}$ such
that $e\in E(P)$ and $f\notin E(P)$.

  * •

The edge $e$ is in $G^{\prime}$ and $f$ is not in $G^{\prime}$. Then, there is
$P\in\mathcal{P}^{\prime}$ such that $e\in E(P)$ and $f\notin E(P)$.

The subgraph $G_{1}$ and collection $\mathcal{Q}$ of paths satisfy the
requirements of the corollary. ∎

The next corollary, applies the previous one twice, to prove a very similar
statement, with the average degree of the remainder now being at most $\log
d$. We could have omitted this corollary and proved Theorem 1.4 directly from
Corollary 3.3, but the counting is slightly simpler with Corollary 3.4.

######  Corollary 3.4.

Let $G$ be a graph on $n$ vertices with average degree $d$, where $d$ is
large. Then there is a subgraph $G_{1}\subseteq G$ with average degree at most
$\log d$ and a collection $\mathcal{P}$ of $O(n)$ paths in $G$ that separates
$G-G_{1}$.

###### Proof.

We apply Corollary 3.3 twice. Denote by $G_{1}$ and $\mathcal{P}_{1}$ the
subgraph and collection of paths resulting from the first application, and let
$G_{2}$ and $\mathcal{P}_{2}$ be the subgraph and collection of paths
resulting from a second application with the graph $G_{1}$. Apply Theorem 1.2
to get a collection $\mathcal{P}_{1}^{\prime}$ of at most $n$ paths that
decomposes $G-G_{1}$, and define $\mathcal{P}_{2}^{\prime}$ similarly with
respect to $G_{1}-G_{2}$. Write
$\mathcal{Q}=\mathcal{P}_{1}\cup\mathcal{P}_{2}\cup\mathcal{P}_{1}^{\prime}\cup\mathcal{P}_{2}^{\prime}$.
Then $|Q|=O(n)$ and $Q$ separates the edges of $G-G_{2}$ (this is easy to
verify using a similar analysis to the proof of Corollary 3.3).

By the properties of $G_{1}$ and $G_{2}$ given by Corollary 3.3 we have
$d(G_{1})=O((\log d)^{420})$ and $d(G_{2})=O((\log
d(G_{1}))^{420})=O((\log\log d)^{420})$. Since $d$ is large, it follows that
$d(G_{2})\leq\log d$. The subgraph $G_{2}$ and collection $Q$ satisfy the
requirements of the corollary. ∎

Finally, we deduce our main result (Theorem 1.4) from Corollary 3.4.

###### Proof of Theorem 1.4.

Write $G_{0}:=G$ and $d:=d(G)$. We define sequences $(G_{i})_{i\geq 1}$ and
collections of paths $(\mathcal{P}_{i})_{i\geq 1}$ as follows. As long as
$d(G_{i})$ is large enough to apply Corollary 3.3, let $G_{i+1}$ and
$\mathcal{P}_{i+1}$ be the graph and collection of paths resulting from an
application of Corollary 3.4 to $G_{i}$. Then $d(G_{i+1})\leq\log d(G_{i})$,
$|\mathcal{P}_{i+1}|=O(n)$ and $\mathcal{P}$ separates the edges of
$G_{i}-G_{i+1}$. Suppose that the last graph we defined was $G_{k}$. Then
$k\leq\log^{\star}n$ and $e(G_{k})=O(n)$. For $i<k$ apply Theorem 1.2 to
obtain a collection of paths $\mathcal{P}_{i}^{\prime}$ that decomposes
$G_{i}-G_{i+1}$ and let $\mathcal{P}_{k}^{\prime}:=E(G_{k})$.

Let $\mathcal{Q}:=\bigcup_{0\leq i<k}\mathcal{P}_{i}\cup\bigcup_{0\leq i\leq
k}\mathcal{P}_{i}^{\prime}$. Then $|\mathcal{Q}|=O(nk)=O(n\log^{\star}n)$. We
claim that $\mathcal{Q}$ separates $E(G)$. To see this, let $e$ and $f$ be two
edges in $G$, let $i$ be such that $e\in G_{i}-G_{i+1}$ (with $i=k$ if $e\in
G_{k}$), and define $j$ similarly with respect to $f$. If $i\neq j$ then there
is a path $P\in\mathcal{P}_{i}^{\prime}$ that contains $e$ but not $f$. If
$i=j\neq k$ then there is a path $P\in\mathcal{P}_{i}$ that contains $e$ but
not $f$. Finally, if $i=j=k$, then $e$ is a path in $\mathcal{P}_{k}^{\prime}$
which contains $e$ but not $f$. Thus $\mathcal{Q}$ is a collection of
$O(n\log^{\star}n)$ paths that separates the edges of $G$. ∎

##  4 Decomposition into expanders

We say that a graph $G$ on $n$ vertices is an _$(\varepsilon,s,t)$ -expander_
if $|N_{G-F}(X)|\geq\frac{\varepsilon|X|}{(\log|X|+1)^{2}}$ for every
$X\subseteq V(G)$ and $F\subseteq E(G)$ satisfying $1\leq|X|\leq 2n/3$ and
$|F|\leq s\cdot\min\\{|X|,t\\}$. An _$(\varepsilon,s)$ -expander_ is an
$(\varepsilon,s,2n/3)$-expander (namely, $F$ is not restricted by $t$). An
_$\varepsilon$ -expander_ is an $(\varepsilon,0)$-expander (namely, $F$ is
always empty). This definition builds on previously defined notions of
expansion: Komlós and Szemerédi [27, 26] introduced a notion of sublinear
expanders, which are (up to a slight change in parameters)
$\varepsilon$-expanders in our notation. Haslegrave, Kim and Liu [22]
introduced a notion of robust sublinear expanders, which are
$(\varepsilon,s)$-expanders in our notation. We add the parameter $t$, which
provides a cut-off in the robustness: vertex sets of size at most $t$ expand
robustly, whereas larger vertex sets expand less robustly.

The following lemma shows that every graph $G$ can be decomposed into
expanders, or almost decomposed into robust expanders. This is a variant of
Lemma 14 in [7] and the proof is similar but more technical. The main
difference is the introduction of the parameter $t$, which allows us to obtain
expanders where small sets of vertices expand robustly, while not leaving too
many edges uncovered. As a sanity check, note that as $s$ and $t$ increase,
the expansion property becomes stronger, and the potential number of uncovered
edges grows.

We will apply this lemma with several regimes for $s$ and $t$: in Section 6 we
take $s$ to be polylogarithmic in $n$ (and take $t=2n/3$). In Section 8 we
apply this lemma twice, once with $s=0$ (in which case the choice of $t$ does
not matter), and once with $s$ a large constant and $t$ being the average
degree of the ground graph.

######  Lemma 4.1.

Let $s\geq 0$, $t\geq 1$ and let $0<\varepsilon\leq 1/48$. Let $G$ be a graph
on $n$ vertices. Then there is a collection $\mathcal{H}$ of pairwise edge-
disjoint $(\varepsilon,s,t)$-expanders that covers all but at most $24sn(\log
t+1)^{2}$ edges of $G$ and satisfies $\sum_{H\in\mathcal{H}}|H|\leq 2n$.

###### Proof.

We leave a few simple calculus claims (see Claims 4.3, 4.4 and 4.5) until
after this proof. Notice that we may assume $t\leq\frac{2n}{3}$.

We prove the statement by induction on $n$, with the following slightly
stronger upper bounds: $24sn\cdot(\log t+1)^{2}(2-\frac{1}{\log n+1})$ on the
number of edges removed, and $n\cdot(2-\frac{1}{\log n+1})$ on the sum of
orders. If $G$ is itself an $(\varepsilon,s,t)$-expander then we may take
$\mathcal{H}=\\{G\\}$, noting that $n\cdot(2-\frac{1}{\log n+1})\geq n$.

Suppose then that $G$ is not an $(\varepsilon,s,t)$-expander. In particular,
$n\geq 2$ because the singleton graph is an $(\varepsilon,s,t)$-expander. This
means that there are subsets $X\subseteq V(G)$ and $F\subseteq E(G)$ such that
$1\leq|X|\leq 2n/3$, $|F|\leq s\cdot\min\\{|X|,t\\}$, and
$|N_{G-F}(X)|\leq\frac{\varepsilon|X|}{(\log|X|+1)^{2}}$. Let $G_{1}:=G[X\cup
N_{G-F}(X)]$ and let $G_{2}$ be the subgraph obtained from $G-X$ by removing
the edges with both ends in $N_{G-F}(X)$. Then $G_{1}$ and $G_{2}$ are edge-
disjoint, together they cover all edges in $G-F$, and they satisfy

$\displaystyle\begin{split}n\leq|G_{1}|+|G_{2}|=n+|N_{G-F}(X)|&\leq
n+\frac{\varepsilon|X|}{(\log|X|+1)^{2}}\\\ &\leq
n+\frac{3\varepsilon|G_{1}|}{(\log|G_{1}|+1)^{2}}\leq
n+\frac{|G_{1}|}{16(\log|G_{1}|+1)^{2}},\end{split}$ (1)

where the penultimate inequality follows from Claim 4.3 stated below.

The bulk of the calculations needed for this lemma will be performed in the
following claim.

######  Claim 4.2.

$\displaystyle\,|G_{1}|\left(2-\frac{1}{\log|G_{1}|+1}\right)+|G_{2}|\left(2-\frac{1}{\log|G_{2}|+1}\right)+\frac{\min\\{|G_{1}|,t\\}}{24(\log
t+1)^{2}}\leq n\left(2-\frac{1}{\log n+1}\right).$

###### Proof.

Write $D$ for the difference between the left-hand side and the right-hand
side.

$\displaystyle D$
$\displaystyle=|G_{1}|\left(2-\frac{1}{\log|G_{1}|+1}\right)+|G_{2}|\left(2-\frac{1}{\log|G_{2}|+1}\right)-n\left(2-\frac{1}{\log
n+1}\right)+\frac{\min\\{|G_{1}|,t\\}}{24(\log t+1)^{2}}$
$\displaystyle=2\left(|G_{1}|+|G_{2}|-n\right)-\frac{|G_{1}|}{\log|G_{1}|+1}-\frac{|G_{2}|}{\log|G_{2}|+1}+\frac{n}{\log
n+1}+\frac{\min\\{|G_{1}|,t\\}}{24(\log t+1)^{2}}$
$\displaystyle\leq\,\frac{|G_{1}|}{8(\log|G_{1}|+1)^{2}}-\frac{|G_{1}|}{\log|G_{1}|+1}-\frac{|G_{2}|}{\log
n+1}+\frac{n}{\log n+1}+\frac{\min\\{|G_{1}|,t\\}}{24(\log t+1)^{2}}$
$\displaystyle\leq\,|G_{1}|\left(\frac{1}{8(\log|G_{1}|+1)^{2}}-\frac{1}{\log|G_{1}|+1}+\frac{1}{\log
n+1}+\frac{\min\\{1,t/|G_{1}|\\}}{24(\log t+1)^{2}}\right),$

where for the first inequality we used (1). We consider two cases:
$|G_{1}|\geq t$ and $|G_{1}|<t$. In the first case, using Claim 4.3, we have

$\frac{\min\\{1,t/|G_{1}|\\}}{24(\log t+1)^{2}}=\frac{t}{24|G_{1}|(\log
t+1)^{2}}\leq\frac{3|G_{1}|}{24|G_{1}|(\log|G_{1}|+1)^{2}}=\frac{1}{8(\log|G_{1}|+1)^{2}}.$

Thus, using Claim 4.5,

$\displaystyle D$
$\displaystyle\leq\,|G_{1}|\left(\frac{1}{4(\log|G_{1}|+1)^{2}}-\frac{1}{\log|G_{1}|+1}+\frac{1}{\log
n+1}\right)\leq 0.$

In the second case, by Claim 4.4, we have
$\frac{1}{8(\log|G_{1}|+1)^{2}}-\frac{1}{\log|G_{1}|+1}\leq\frac{1}{8(\log
t+1)^{2}}-\frac{1}{\log t+1}$. Thus,

$\displaystyle D$ $\displaystyle\leq|G_{1}|\left(\frac{1/8+1/24}{(\log
t+1)^{2}}-\frac{1}{\log t+1}+\frac{1}{\log n+1}\right)$
$\displaystyle\leq|G_{1}|\left(\frac{1}{4(\log t+1)^{2}}-\frac{1}{\log
t+1}+\frac{1}{\log n+1}\right)\leq 0,$

where the last inequality follows from Claim 4.5, using $1\leq t\leq 2n/3$.
Either way, $D\leq 0$, as required. ∎

For $i\in[2]$, apply the induction hypothesis to $G_{i}$ to obtain a family
$\mathcal{H}_{i}$ of pairwise edge-disjoint subgraphs of $G_{i}$ that cover
all but at most $24s(\log t+1)^{2}|G_{i}|(2-\frac{1}{\log|G_{i}|+1})$ edges of
$G_{i}$ and satisfy
$\sum_{H\in\mathcal{H}_{i}}|H|\leq|G_{i}|\left(2-\frac{1}{\log|G_{i}|+1}\right)$.
Take $\mathcal{H}=\mathcal{H}_{1}\cup\mathcal{H}_{2}$. By Claim 4.2, the
graphs in $\mathcal{H}$ cover all but at most the following number of edges in
$G$:

$\displaystyle 24s(\log
t+1)^{2}\left(|G_{1}|\left(2-\frac{1}{\log|G_{1}|+1}\right)+|G_{2}|\left(2-\frac{1}{\log|G_{2}|+1}\right)+\frac{\min\\{|G_{1}|,t\\}}{24(\log
t+1)^{2}}\right)\leq$ $\displaystyle 24sn(\log t+1)^{2}\left(2-\frac{1}{\log
n+1}\right).$

Similarly,

$\displaystyle\sum_{H\in\mathcal{H}}|H|\leq\sum_{H\in\mathcal{H}_{1}}|H|+\sum_{H\in\mathcal{H}_{2}}|H|$
$\displaystyle\leq|G_{1}|\left(2-\frac{1}{\log|G_{1}|+1}\right)+|G_{2}|\left(2-\frac{1}{\log|G_{2}|+1}\right)$
$\displaystyle\leq n\left(2-\frac{1}{\log n+1}\right).$

So $\mathcal{H}$ satisfies the requirements, proving the induction hypothesis.
∎

We now state and prove the calculus claims used in the proof of Lemma 4.1.

######  Claim 4.3.

$\frac{x}{(\log x+1)^{2}}\leq\frac{3y}{(\log y+1)^{2}}$ for integers $x,y$
with $1\leq x\leq y$.

###### Proof.

Consider the function $f(x)=\frac{x}{(\log x+1)^{2}}$. Then

$f^{\prime}(x)=\frac{(\log_{e}(2))^{2}\log_{e}(2x/e^{2})}{(\log_{e}(x)+1)^{3}}.$

In particular, $f^{\prime}(x)\geq 0$ for $x\geq 4$, showing $f(x)\leq f(y)\leq
3f(y)$ when $4\leq x\leq y$ (using $f(y)\geq 0$ for $y\geq 4$). A calculation
shows $1/3\leq f(x)\leq 1$ for $x\in[4]$. It follows that $f(x)\leq 3f(y)$ for
$x\in[3]$ and any integer $y\geq 1$. ∎

######  Claim 4.4.

$\frac{1}{8(\log x+1)^{2}}-\frac{1}{\log x+1}\leq\frac{1}{8(\log
y+1)^{2}}-\frac{1}{\log y+1}$ when $1\leq x\leq y$.

###### Proof.

Write $f(x)=\frac{1}{8(\log x+1)^{2}}-\frac{1}{\log x+1}$. Then the derivative
$f^{\prime}(x)$ satisfies the following for $x\geq 1$.

$f^{\prime}(x)=\frac{\log_{e}(2)(4\log_{e}x+\log_{e}8)}{4x(\log_{e}(2x))^{3}}\geq
0.$

In particular, $f$ is increasing in the range $x\geq 1$, as required. ∎

######  Claim 4.5.

The following holds for $1\leq x\leq\log(2n/3)+1$ and $n\geq 2$.

$\frac{1}{4x^{2}}-\frac{1}{x}+\frac{1}{\log n+1}\leq 0.$

###### Proof.

Write $f(x)=\log n+1-4x(\log n+1)+4x^{2}$, and notice that it suffices to
prove $f(x)\leq 0$ for $1\leq x\leq\log(2n/3)+1$.

Since the set of reals $x$ for which $f(x)\leq 0$ is an interval, it suffices
to show that $f(x)\leq 0$ for $x=1$ and $x=\log(2n/3)+1$.

$\displaystyle f(1)$ $\displaystyle=\log n+1-4(\log n+1)+4=1-3\log n\leq 0.$
$\displaystyle f(\log(2n/3)+1)$ $\displaystyle=\log n+1-4(\log(2n/3)+1)(\log
n+1)+4(\log(2n/3)+1)^{2}$ $\displaystyle=\log n+1-4(\log n+\log(4/3))(\log
n+1)+4(\log n+\log(4/3))^{2}$ $\displaystyle=\log
n\cdot(1-4-4\log(4/3)+8\log(4/3))+1-4\log(4/3)+4(\log(4/3))^{2}$
$\displaystyle\leq-\log n+1\leq 0.$

This completes the proof of the claim. ∎

##  5 Finding vertex-disjoint paths through a random vertex set

In this section we prove Lemma 5.10, which allows for connecting pairs of
vertices $(x_{1},y_{1}),\ldots,(x_{r},y_{r})$ in a robust expander through a
random set of vertices via vertex-disjoint paths, provided that any subset of
the vertices $x_{1},\ldots,x_{r},y_{1},\ldots,y_{r}$ expands well. This is a
variant of Theorem 10 in [7], which does something very similar, but avoids
the expansion assumption on $x_{1},\ldots,x_{r},y_{1},\ldots,y_{r}$ and only
requires the paths to be edge-disjoint. Our proof follows [7] very closely. We
note that, as mentioned also in [7], some of the ideas that appear in the
proof are due to Tomon [39].

We will introduce the relevant preliminaries (including a different notion of
expansion) in Section 5.1, we then prove Lemma 5.10 in three steps, given in
Sections 5.2, 5.3 and 5.4.

###  5.1 Preliminaries

Say that a graph $G$ on $n$ vertices is a _weak $(\varepsilon,s)$-expander_ if
$|N_{G-F}(U)|\geq\frac{\varepsilon|U|}{(\log n)^{2}}$ for every $U\subseteq
V(G)$ and $F\subseteq E(G)$ with $1\leq|U|\leq 2n/3$ and $|F|\leq s|U|$. In
[7] such a graph is called simply an $(\varepsilon,s)$-expander; we add ‘weak’
to its name to distinguish it from $(\varepsilon,s)$-expanders, which have
stronger expansion properties for smaller sets of vertices. Note that an
$(\varepsilon,s)$-expander on at least two vertices is a weak
$(\frac{\varepsilon}{2},s)$-expander.

We will use the following two propositions from [7], both of which show that
every not-too-large vertex set $U$ in an expander either ‘expands well’ (i.e.
has a large neighbourhood) or ‘expands robustly’ (i.e. there are many vertices
in $N(U)$ with many neighbours in $U$). We state a slightly simplified version
of the propositions, where there is no set of forbidden edges, because we will
not use this feature.

######  Proposition 5.1 (Proposition 12 in [7]).

Let $\varepsilon>0$, let $0<d\leq s$. Suppose that $G$ is an $n$-vertex
$(\varepsilon,s)$-weak expander. Then one of the following holds, for every
set $U\subseteq V(G)$ with $|U|\leq\frac{2n}{3}$.

  * •

$|N(U)|\geq\frac{s|U|}{2d}$, or

  * •

$\left|\\{u\in V(G):|N(u)\cap U|\geq
d\\}\right|\geq\frac{\varepsilon|U|}{(\log n)^{2}}$.

######  Proposition 5.2 (Proposition 13 in [7]).

Let $\varepsilon\geq 2^{-9}$, $s\geq 8(\log n)^{13}$, and let $n$ be large.
Suppose that $G$ is an $(\varepsilon,s)$-weak expander, and let $W\subseteq
V(G)$ satisfy $|W|\leq 2n/3$. Then $G$ contains one of the following

  * •

a collection of at least $\frac{|W|}{(\log n)^{7}}$ pairwise vertex-disjoint
stars of size at least $(\log n)^{9}$, whose centre is in $W$ and its leaves
are in $V(G)-W$,

  * •

a bipartite graph $H$ with parts $W$ and $X\subseteq V(G)-W$, such that

    * –

$|X|\geq\frac{\varepsilon|W|}{2(\log n)^{2}}$,

    * –

every vertex in $X$ has degree at least $(\log n)^{4}$ and every vertex in $W$
has degree at most $2(\log n)^{9}$ in $H$.

As in [7], we also need the following hypergraph version of Hall’s theorem,
due to Aharoni and Haxell.

######  Theorem 5.3 (Aharoni–Haxell [1]).

Let $s,r\geq 1$ be integers, and let $\mathcal{H}_{1},\ldots,\mathcal{H}_{r}$
be hypergraphs on the same vertex set whose edges have at most $s$ vertices.
Suppose that, for every $I\subseteq[r]$, there is a matching in $\bigcup_{i\in
I}\mathcal{H}_{i}$ of size at least $s(|I|-1)$. Then there is a matching of
size $r$ in $\bigcup_{i\in[r]}\mathcal{H}_{i}$ whose $i^{\text{th}}$ edge is
in $\mathcal{H}_{i}$.

Additionally, we use the following martingale concentration result (see
Chapter 7 in [2]).

######  Lemma 5.4.

Suppose that $X:\prod_{i=1}^{n}\Omega_{i}\to\mathbb{R}$ is $k$-Lipschitz.
Then,

$\mathbb{P}\left(|X-\mathbb{E}X|>t\right)\leq
2\exp\left(\frac{-2t^{2}}{k^{2}n}\right).$

###  5.2 Expansion into a random vertex set

The following lemma shows that, given a sufficiently robust weak expander $G$
and a random set of vertices $V$, obtained by including each vertex
independently with probability $1/6$, any set $U$ expands well in $V$, while
avoiding a given small set of vertices $Z$, with quite large probability. This
lemma is a variant of Lemma 17 in [7], where instead of a forbidden set of
edges we have a forbidden set of vertices, and the proof is essentially the
same.

######  Lemma 5.5.

Let $2^{-9}\leq\varepsilon<1$, $s\geq 8(\log n)^{13}$ and let $n$ be large.
Suppose that $G$ is an $n$-vertex weak $(\varepsilon,s)$-expander and let
$U,Z\subseteq V(G)$ be sets satisfying $|U|\geq(\log n)^{23}$ and
$|Z|\leq\frac{|U|}{(\log n)^{3}}$. Let $V$ be a random subset of $V(G)$,
obtained by including each vertex independently with probability $1/6$. Then,
with probability at least $1-\exp\left(-\Omega\left(\frac{|U|}{(\log
n)^{22}}\right)\right)$,

$\left|B^{(\log n)^{4}}_{G[V^{\prime}]}(U\cap
V^{\prime})\right|>\frac{|V|}{2},$

where $V^{\prime}:=V-Z$.

###### Proof.

Take $\ell:=(\log n)^{4}$, and let $p$ satisfy $1-(1-p)^{\ell}=\frac{1}{24}$.
Let $V_{1},\ldots,V_{\ell},V^{\prime}$ be random sets, where $V_{i}$ is
obtained by including each vertex with probability $p$, independently, and
$V^{\prime}$ is obtained by including each vertex with probability
$\frac{3}{23}$, independently. Notice that each vertex is in
$V_{1}\cup\ldots\cup V_{\ell}\cup V^{\prime}$ with probability $1/6$, and so
we may think of $V$ as the union $V_{1}\cup\ldots\cup V_{\ell}\cup
V^{\prime}$. Notice also that $p\geq\frac{1}{31(\log n)^{4}}$.

Define $B_{0}:=U$ and, for $i\geq 1$, let $B_{i}$ be the set of vertices in
$G$ that can be reached by a path in $G-Z$ that starts in $U$, has length at
most $i$, and its interior is in $V_{1}\cup\ldots\cup V_{i}$. We emphasise
that $B_{i}$ is only required to be disjoint of $Z$, and need not be a subset
of $V_{i}$. Notice that the $B_{i}\subseteq B_{i+1}$ for every $i\geq 0$,
implying that $|B_{i}|\geq|U-Z|\geq\frac{1}{2}|U|$ for $i\geq 0$.

######  Claim 5.6.

If $|B_{i}|\leq\frac{2}{3}n$, then, with probability at least
$1-\exp\left(-\Omega\left(\frac{|U|}{(\log n)^{22}}\right)\right)$,

$\left|B_{i+1}-B_{i}\right|\geq\frac{\varepsilon|B_{i}|}{2^{17}(\log n)^{2}}.$

###### Proof.

Notice that a vertex in $N(B_{i})-Z$ is in $B_{i+1}-B_{i}$ if at least one of
its neighbours in $B_{i}$ is sampled into $V_{i+1}$. We consider the two
possible outcomes of Proposition 5.2 for $B_{i}$.

Suppose that the first outcome holds, so there are $\frac{|B_{i}|}{(\log
n)^{7}}$ pairwise vertex-disjoint stars of size $(\log n)^{9}$ with centres in
$B_{i}$ and leaves in $N(B_{i})$. By a Chernoff bound, with probability at
least $1-\exp\left(-\Omega\left(\frac{p|B_{i}|}{(\log
n)^{7}}\right)\right)=1-\exp\left(-\Omega\left(\frac{|U|}{(\log
n)^{11}}\right)\right)$, at least $\frac{p|B_{i}|}{2(\log n)^{7}}$ centres are
added to $V_{i+1}$, implying that

$\left|B_{i+1}-B_{i}\right|\geq(\log n)^{9}\cdot\frac{p|B_{i}|}{2(\log
n)^{7}}-|Z|\geq\frac{|B_{i}|}{62(\log n)^{2}}-\frac{|U|}{(\log
n)^{3}}\geq\frac{|B_{i}|}{64(\log n)^{2}}.$

Now suppose that the second outcome holds, so there is a bipartite subgraph
$H\subseteq G$ with parts $B_{i}$ and $X\subseteq V(G)-B_{i}$, with
$|X|\geq\frac{\varepsilon|B_{i}|}{4(\log n)^{2}}$, such that vertices in $X$
have degree at least $d:=(\log n)^{4}$ in $H$ while vertices in $B_{i}$ have
degree at most $D:=2(\log n)^{9}$ in $H$. Let $Y$ be the set of vertices in
$X$ that do not have an $H$-neighbour in $V_{i+1}$. Note that
$\mathbb{E}|Y|\leq|X|(1-p)^{d}\leq|X|e^{-pd}\leq\frac{31}{32}|X|$. Note also
that $|Y|$ is $D$-Lipschitz, since the outcome of the sampling of any single
vertex in $B_{i}$ affects the outcome of at most $D$ vertices in $X$. Thus, by
Lemma 5.4,

$\mathbb{P}\left(|Y|>\frac{63}{64}|X|\right)\leq\mathbb{P}\left(|Y|>\mathbb{E}|Y|+\frac{|X|}{64}\right)\leq
2\exp\left(-\frac{|X|^{2}}{2^{11}D^{2}|B_{i}|}\right)=\exp\left(-\Omega\left(\frac{|U|}{(\log
n)^{22}}\right)\right).$

So, with probability at least $1-\exp\left(-\Omega\left(\frac{|U|}{(\log
n)^{22}}\right)\right)$, we have
$|B_{i+1}-B_{i}|\geq\frac{|X|}{64}-|Z|\geq\frac{\varepsilon|B_{i}|}{2^{17}(\log
n)^{2}}$. ∎

Iterating the claim, with probability at least

$1-(\log n)^{4}\cdot\exp\left(-\Omega\left(\frac{|U|}{(\log
n)^{22}}\right)\right)\geq 1-\exp\left(-\Omega\left(\frac{|U|}{(\log
n)^{22}}\right)\right),$

if $|B_{i}|\leq\frac{2}{3}n$ and $i\leq(\log n)^{4}$, then,

$|B_{i}|\geq\left(1+\frac{\varepsilon}{2^{17}(\log n)^{2}}\right)^{i}|U|,$

which implies $|B_{\ell}|\geq\frac{2}{3}n$.

To complete the proof, note that any vertex in $B_{\ell}$ that gets sampled
into $V^{\prime}$ (or that is already in $V_{1}\cup\ldots\cup V_{\ell}$) is in
the set $B^{\prime}:=B_{G[V^{\prime}]}^{(\log n)^{4}}(U\cap V)$. By Chernoff,
with probability at least $1-e^{-\Omega(n)}$, at least
$\frac{9}{70}\cdot\frac{2}{3}n$ vertices of $B_{\ell}$ are in $V$, and
$|V|\leq\frac{6}{35}n$. If all this holds, then $|B^{\prime}|>\frac{1}{2}|V|$,
as required. ∎

The next corollary, which is a variant of Lemma 19 in [7], boosts the
probability of expansion of $U$ into $V$, so as to be amenable to an
application of the union bound, with the expense of a slightly smaller upper
bound on $|Z|$.

######  Corollary 5.7.

Let $2^{-9}\leq\varepsilon<1$, $s\geq 2^{11}(\log n)^{50}$, and let $n$ be
large. Suppose that $G$ is an $n$-vertex weak $(\varepsilon,s)$-expander, and
let $V$ be a random subset of $V(G)$, obtained by including each vertex
independently with probability at least $1/6$. Then, with high probability, if
$U,Z\subseteq V(G)$ are sets with $|Z|\leq\frac{|U|}{(\log n)^{30}}$, then

$\left|B^{(\log n)^{4}}_{G[V^{\prime}]}\left(N(U)\cap
V^{\prime}\right)\right|>\frac{|V|}{2},$ (2)

where $V^{\prime}:=V-Z$.

###### Proof.

Say that a set $U\subseteq V(G)$ _expands well_ if $|N(U)|\geq|U|(\log
n)^{24}$. Given a (non-empty) set $U$ which expands well, and a set $Z$ with
$|Z|\leq|U|$, Lemma 5.5 (applied with $U_{\ref{lem:expansion-random}}=N(U)$)
tells us that (2) holds, with probability at least
$1-\exp\left(-\Omega\left(|U|(\log n)^{2}\right)\right)$.

By a union bound, we conclude that the probability that (2) fails for $(U,Z)$,
with $U$ well-expanding and $|Z|\leq|U|$, is at most

$\displaystyle\sum_{u=1}^{n}\binom{n}{u}^{2}\exp\left(-\Omega\left(u(\log
n)^{2}\right)\right)$ $\displaystyle\leq\sum_{u=1}^{n}\exp\left(2u\log
n-\Omega\left(u(\log n)^{2}\right)\right)$
$\displaystyle=\sum_{u=1}^{n}\exp\left(-\Omega\left(u(\log
n)^{2}\right)\right)=o(1/n).$

For the rest of the proof we assume that (2) holds for all such pairs $(U,Z)$.
To complete the proof, we will deduce that (2) holds for all pairs $(U,Z)$,
where $U$ need not expand well, $|U|\leq\frac{2}{3}n$, and
$|Z|\leq\frac{|U|}{(\log n)^{30}}$. Fix such $U,Z$.

Write $d:=\frac{2}{\varepsilon}(\log n)^{26}$. By Proposition 5.1, either
$|N(U)|\geq\frac{s|U|}{2d}$, or $\left|\\{u:|N(u)\cap U|\geq
d\\}\right|\geq\frac{\varepsilon|U|}{(\log n)^{2}}$. Notice that the first
outcome implies that $U$ expands well and so we already know that (2) holds.
We thus assume that the second one holds, and write $W:=\\{u:|N(u)\cap U|\geq
d\\}$. Let $U^{\prime}$ be a subset of $U$ of size $\frac{|U|}{d}$, chosen
uniformly at random. For a fixed $w\in W$, the probability that $w$ has no
neighbours in $U^{\prime}$ is at most

$\frac{\binom{|U|-d}{|U|/d}}{\binom{|U|}{|U|/d}}\leq\left(\frac{|U|-d}{|U|}\right)^{|U|/d}\leq
e^{-1}.$

It follows that $\mathbb{E}[|W\cap
N(U^{\prime})|]\geq(1-e^{-1})|W|\geq\frac{\varepsilon|U|}{2(\log
n)^{2}}=|U^{\prime}|(\log n)^{24}$. In particular, there is a subset
$U^{\prime}\subseteq U$ of size $\frac{|U|}{d}$ with
$|N(U^{\prime})|\geq|U^{\prime}|(\log n)^{24}$. Since such $U^{\prime}$
expands well, and $|Z|\leq\frac{|U|}{(\log n)^{30}}\leq|U^{\prime}|$, Equation
(2) holds for $(U^{\prime},Z)$ and thus for $(U,Z)$. ∎

###  5.3 A path connection through a random set

Our end goal is to be able to join (disjointly) $r$ pairs of vertices through
a random set $V$, provided that they expand well. Here we show how to join one
pair of vertices (while avoiding a small set of forbidden vertices). This is a
variant of Proposition 8 in [7], where in addition to forbidding vertices
instead of edges, we also impose the expansion property on the vertices we
wish to connect. The proof is essentially the same.

######  Lemma 5.8.

Let $2^{-9}\leq\varepsilon<1$, $s\geq 2^{11}(\log n)^{50}$, and let $n$ be
large. Suppose that $G$ is an $n$-vertex weak $(\varepsilon,s)$-expander, and
let $V$ be a random subset of $V(G)$, obtained by including each vertex
independently with probability $1/6$. Then, with high probability, the
following holds for every $r$: if $x_{1},\ldots,x_{r},y_{1},\ldots,y_{r}$ are
distinct vertices, satisfying $|N(X)|\geq|X|(\log n)^{50}$ for every subset
$X\subseteq\\{x_{1},\ldots,x_{r},y_{1},\ldots,y_{r}\\}$, and $Z$ is a set of
size at most $2r(\log n)^{12}$ which is disjoint of
$\\{x_{1},\ldots,x_{r},y_{1},\ldots,y_{r}\\}$, then for some $i\in[r]$ there
is an $(x_{i},y_{i})$-path in $G$ whose interior is in $V-Z$ and whose length
is at most $(\log n)^{6}$.

###### Proof.

Fix an outcome of $V$ such that Equation (2) holds for every disjoint
$U,Z\subseteq V(G)$ with $|Z|\leq\frac{|U|}{(\log n)^{30}}$ (here
$V^{\prime}:=V-Z$), and moreover $|V|\geq\frac{n}{8}$. By Corollary 5.7 and a
Chernoff bound, both these assumptions hold with high probability, and so we
are justified in making them. Write $\ell:=(\log n)^{4}+1$. For a set of
vertices $X$ and integer $d\geq 1$, define
$R^{d}(X):=B^{d}_{G[V^{\prime}]}(N(X)\cap V^{\prime})$.

Let $X_{1}$ be the set of vertices $x$ in $\\{x_{1},\ldots,x_{r}\\}$
satisfying $|R^{\ell\log n}(x)|\leq\frac{|V|}{2}$.

######  Claim 5.9.

$|X_{1}|<\frac{r}{2}$.

###### Proof.

Suppose $|X_{1}|\geq\frac{r}{2}$. We will show that there is a sequence
$(X_{i})_{i\geq 1}$, such that $X_{i}\supseteq X_{i+1}$,
$|X_{i+1}|\leq\max\\{1,\frac{|X_{i}|}{2}\\}$, and

$\left|R^{i\ell}(X_{i})\right|>\frac{|V|}{2},$ (3)

for $i\geq 1$.

Notice that $|N(X_{1})|\geq\frac{r}{2}(\log n)^{50}$, using
$|X_{1}|\geq\frac{r}{2}$ and the assumption on the $x_{i}$’s. Thus
$|N(X_{1})|\geq|Z|(\log n)^{30}$, and, by (2), $|R^{(\log n)^{4}}(N(X_{1})\cap
V^{\prime})|>\frac{|V|}{2}$. It follows that $|R^{\ell}(X_{1})|\geq|R^{(\log
n)^{4}}(X_{1})|>\frac{|V|}{2}$, proving (3) for $i=1$.

Now suppose that $X_{1}\supseteq\ldots\supseteq X_{j}$ and (3) holds for
$i\in[j]$. If $|X_{i}|=1$ we take $X_{i+1}=X_{i}$ (which clearly satisfies the
requirements). Otherwise, by dividing $X_{i}$ into at most three sets of size
at most $\frac{|X_{i}|}{2}$, there is a subset $X_{i+1}\subseteq X_{i}$ of
size at most $\frac{|X_{i}|}{2}$ satisfying
$|R^{i\ell}(X_{i+1})|\geq\frac{|V|}{6}$. Consider the set
$U:=R^{i\ell}(X_{i+1})$. It satisfies
$|U|\geq\frac{|V|}{6}\geq\frac{n}{48}\geq\frac{r}{48}(\log n)^{50}\geq|Z|(\log
n)^{30}$, where the third inequality follows implicitly from the assumption
that $|N(\\{x_{1},\ldots,x_{r}\\})|\geq r(\log n)^{50}$. Thus, by (2),

$\left|B_{G[V^{\prime}]}^{(\log n)^{4}}\left(N(U)\cap
V^{\prime}\right)\right|>\frac{|V|}{2}.$

Notice that

$B^{(\log n)^{4}}_{G[V^{\prime}]}\left(N(U)\cap
V^{\prime}\right)=B_{G[V^{\prime}]}^{\ell}(U)=R^{(i+1)\ell}(X_{i+1}),$

so $X_{i+1}$ has the required properties. This completes the proof of the
existence of a sequence $(X_{i})_{i\geq 1}$ with the above properties.

Fix such a sequence, and take $i:=\log n$. Then $|X_{i}|\leq\max\\{1,2^{-\log
n}|X_{1}|\\}=1$. This means $|R^{\ell\log n}(x)|>\frac{|V|}{2}$ for the single
vertex $x$ in $X_{i}$, contradicting the choice of $X_{1}$. ∎

Take $Y_{1}$ to be the set of vertices $y\in\\{y_{1},\ldots,y_{r}\\}$ with
$|R^{\ell\log n}(y)|\leq\frac{|V|}{2}$. Then, analogously to the above claim,
$|Y_{1}|<\frac{r}{2}$. Hence, there exists $i\in[r]$ such that $|R^{\ell\log
n}(x_{i})|,|R^{\ell\log n}(y_{i})|>\frac{|V|}{2}$, showing that there is an
$(x,y)$-path of length at most $2\ell\log n+2$, with interior in $V^{\prime}$,
as required. ∎

###  5.4 Many disjoint path connections through a random set

Finally, we prove that given a sufficiently robust weak expander and pairs
$(x_{1},y_{1}),\ldots,(x_{r},y_{r})$, such that the set
$\\{x_{1},\ldots,x_{r},y_{1},\ldots,y_{r}\\}$ expands well, the pairs can be
connected via vertex-disjoint paths through a random set $V$. This is a
variant of Lemma 10 in [7] (though their statement looks quite different).

######  Lemma 5.10.

Let $2^{-9}\leq\varepsilon<1$, $s\geq 2^{11}(\log n)^{50}$, and let $n$ be
large. Suppose that $G$ is an $n$-vertex weak $(\varepsilon,s)$-expander, and
let $V$ be a random subset of $V(G)$, that includes each vertex independently
with probability $\frac{1}{6}$. Then, with high probability, for every
sequence of vertices $x_{1},\ldots,x_{r},y_{1},\ldots,y_{r}$ satisfying
$|N(X)|\geq|X|(\log n)^{50}$ for every
$X\subseteq\\{x_{1},\ldots,x_{r},y_{1},\ldots,y_{r}\\}$, there is a sequence
of paths $P_{1},\ldots,P_{r}$, whose interiors are pairwise vertex-disjoint
and in $V$, such that $P_{i}$ is a path from $x_{i}$ to $y_{i}$.

###### Proof.

We assume that the conclusion of Lemma 5.8 holds (it holds with high
probability, so we are justified in making this assumption). Let
$\mathcal{H}_{i}$ be the hypergraph on vertex set $V$ with edges the interiors
of $P$, for all $(x_{i},y_{i})$-paths $P$ of length at most $\ell:=(\log
n)^{6}$ with interior in $V$.

We will use Theorem 5.3. Fix a subset $I\subseteq[r]$. We wish to show that
there is a matching of size $\ell(|I|-1)+1$ in
$\mathcal{H}^{\prime}:=\bigcup_{i\in I}\mathcal{H}_{i}$. Suppose no such
matching exist, and let $\mathcal{M}^{\prime}$ be a maximal matching in
$\mathcal{H}^{\prime}$. Then $|\mathcal{M}^{\prime}|\leq\ell(|I|-1)$ and every
edge in $\mathcal{H}^{\prime}$ intersects $Z:=V(\mathcal{M}^{\prime})$, a set
of size at most $\ell^{2}(|I|-1)\leq|I|(\log n)^{12}$. The conclusion of Lemma
5.8 tells us that for some $i\in I$ there is an $(x_{i},y_{i})$-path $P$ of
length at most $\ell$ whose interior is in $V-Z$. But this means that
$V(P)-\\{x_{i},y_{i}\\}$ is an edge in $\mathcal{H}^{\prime}$ that does not
intersect $Z$, a contradiction.

So, the assumptions in Theorem 5.3 are satisfied, showing that there is a
matching $\mathcal{M}$ of size $r$ in $\bigcup_{i\in[r]}\mathcal{H}_{i}$,
whose $i$-th edge is in $\mathcal{H}_{i}$. Let $P_{i}$ be the path
corresponding to the $i$-th edge in $\mathcal{M}$. Then $P_{i}$ is an
$(x_{i},y_{i})$-path with interior in $V$, and the interiors of the $P_{i}$’s
are pairwise vertex-disjoint, proving the lemma. ∎

##  6 Proof of Lemma 3.1: separating dense expanders

In this section we prove the first key lemma, Lemma 3.1, which shows that for
any graph $G$, there is a linear path system that separates a subgraph of $G$,
whose complement in $G$ has polylogarithmic average degree. This will follow
quite easily from Lemma 4.1, that decomposes graphs into expanders, and
Corollary 6.4 that shows that robust weak expanders can be separated by a
linear path system.

To prove the latter corollary, given a robust weak expander $G$, we will take
a random partition $\\{V_{1},V_{2},V_{3}\\}$ of $V(G)$ and show that, with
high probability, $G-V_{i}$ can be separated using a linear path system, for
$i\in[3]$. Taking the union of these collections of paths, as well as a
decomposition of $G-V_{i}$ into a linear number of paths, we obtain the
desired linear separating paths system for $G$.

It thus suffices to prove that, with high probability, if $V$ is a random set,
obtained by including each vertex independently with probability $1/3$, then
$G-V$ has a linear separating path system. This is done in the following
lemma, whose proof proceeds as follows. First, we decompose $G-V$ into at most
$n$ paths $\mathcal{P}$ (using Theorem 1.2), and then we show that $G-V$ can
be further decomposed into $O(n)$ matchings $M$, each of which intersects each
path in $\mathcal{P}$ in at most one edge, and moreover each matching
satisfies a certain degree condition. Next, we take a random partition
$\\{V_{1},V_{2}\\}$ of $V$, taken uniformly at random. We first extend each
$M$ through $V_{1}$ to a path forest $F$, in such a way that any set of leaves
of $F$ expands in $G$, and thus in $V$. This is exactly the property needed
for an application of Lemma 5.10, so we can use it to connect the leaves of
$F$ via paths through $V$, vertex-disjointly. We thus get a path $P_{M}$ that
extends $M$ and contains no other edges from $G-V$, and so
$\mathcal{P}\cup\\{P_{M}:M\in\mathcal{M}\\}$ is a linear collection of paths
separating $G-V$.

######  Lemma 6.1.

Let $2^{-9}\leq\varepsilon<1$, $s\geq 2^{11}(\log n)^{51}$, and let $n$ be
large. Suppose that $G$ is a weak $(\varepsilon,s)$-expander, and let $V$ be a
random subset of $V(G)$, that includes each vertex independently with
probability $\frac{1}{3}$. Then, with high probability, there is a collection
of $211n$ paths that separates $G-V$.

###### Proof.

Let $\\{V_{1},V_{2}\\}$ be a partition of $V$, chosen uniformly at random. We
will make the following assumptions.

  1. (a)

if $|N(U)|\geq|U|(\log n)^{2}$ then $|N(U)\cap V_{1}|\geq\frac{1}{10}|N(U)|$,
for every set of vertices $U$,

  2. (b)

the conclusion of Lemma 5.10 holds for $V_{2}$.

Noting that each vertex is included in $V_{i}$ with probability at
$\frac{1}{6}$, a Chernoff bound and Lemma 5.10 allow us to make these
assumptions.

Write $G^{\prime}:=G-V$. Let $\mathcal{P}$ be a collection of at most $n$
paths that decomposes $G^{\prime}$. For an edge $e=xy$ in $G^{\prime}$, let
$P(e)$ be the unique path in $\mathcal{P}$ that contains $e$, and define
$\bar{d}(e):=\min\\{d_{G}(x),d_{G}(y)\\}$. Notice that, by expansion,
$\delta(G)\geq s\geq(\log n)^{51}$ and so $\bar{d}(e)\geq(\log n)^{51}$ for
every edge $e$ in $G$.

######  Claim 6.2.

There is a collection $\mathcal{M}$ of $210n$ pairwise edge-disjoint matchings
in $G^{\prime}$ that covers all edges in $G^{\prime}$ and every
$M\in\mathcal{M}$ satisfies: every path in $\mathcal{P}$ intersects at most
one edge in $M$; and for every $d$ there are at most $\frac{d}{50}$ edges $e$
in $M$ with $\bar{d}(e)\leq d$.

###### Proof.

Let $\mathcal{M}$ be a collection of $210n$ pairwise edge-disjoint matchings
such that every $M\in\mathcal{M}$ satisfies the following properties,

  * •

every path in $\mathcal{P}$ contains at most one edge from $M$,

  * •

for every integer $r\geq 1$, there are at most $\frac{1}{200}2^{r}$ edges $e$
in $M$ with $\bar{d}(e)\in[2^{r-1},2^{r})$,

and $\mathcal{M}$ covers a maximum number of edges in $G^{\prime}$ under these
conditions. We will show that the matchings in $\mathcal{M}$ together cover
all edges of $G^{\prime}$. Suppose not, and take $e$ to be an edge in
$G^{\prime}$ such that $e\notin\bigcup\mathcal{M}$. Let $r$ be the integer for
which $\bar{d}(e)\in[2^{r-1},2^{r})$.

There are at most $n$ matchings in $\mathcal{M}$ containing an edge of $P(e)$,
and at most $2n$ matchings containing an edge that intersects $e$. Notice that
$G^{\prime}$ has at most $2^{r}n$ edges $f$ with
$\bar{d}(f)\in[2^{r-1},2^{r})$, so the number of matchings $M\in\mathcal{M}$
that contain at least $\frac{1}{200}2^{r}-1$ such edges is at most

$\frac{2^{r}n}{\frac{1}{200}2^{r}-1}=200n+\frac{40000n}{2^{r}-200}\leq 201n,$

using that $r\geq\log(\bar{d}(e))-1\geq 51\log\log n-1$ and that $n$ is large.
Hence, there exists $M\in\mathcal{M}$ that has no edges in $P(e)$ or edges
that intersect $e$, and has at most $\frac{1}{200}2^{r}-1$ edges $f$ with
$\bar{d}(f)\in[2^{r-1},2^{r})$. Replacing $M$ with $M\cup\\{e\\}$, we reach a
contradiction to the maximality of $\mathcal{M}$, showing that $\mathcal{M}$
covers all edges in $G^{\prime}$.

It remains to show that there are at most $\frac{d}{100}$ edges $e$ in $M$
with $\bar{d}(e)\leq d$, for every $d\geq 1$ and $M\in\mathcal{M}$. To see
this, fix $M$ and $d$, and let $r$ be the integer such that
$d\in[2^{r-1},2^{r})$. Then, there are at most
$\frac{1}{200}(1+2+\ldots+2^{r})\leq\frac{1}{100}2^{r}\leq\frac{d}{50}$ edges
$e$ in $M$ with $\bar{d}(e)\leq 2^{r}$, as required. ∎

Let $\mathcal{M}$ be as in the above claim. For an edge $e$ in $G^{\prime}$,
denote by $M(e)$ the unique matching in $\mathcal{M}$ containing $e$. Fix
$M\in\mathcal{M}$. We will show that there is a path $P_{M}$ that contains
$E(M)$ and its edges which are not in $M$ have at least one end in
$V=V_{1}\cup V_{2}$. Write $M=\\{e_{1},\ldots,e_{|M|}\\}$, where
$\bar{d}(e_{1})\leq\ldots\leq\bar{d}(e_{|M|})$. We will define a sequence
$F_{0},\ldots,F_{|M|}$ of path forests, as follows. Take $F_{0}:=M$. Having
defined $F_{i-1}$, if a vertex $v$ in $e_{i}$ is a leaf in $F_{i-1}$ and has a
common neighbour $u$ in $V_{2}$ with a leaf $v^{\prime}$ of another component
in $F_{i-1}$, add the edges $uv,uv^{\prime}$ to $F_{i-1}$ (thereby obtaining a
new path forest which has one component fewer). Repeat this with the other
vertex in $e_{i}$, and denote the resulting graph by $F_{i}$. Write
$F:=F_{|M|}$, denote the components of $F$ by $P_{1},\ldots,p_{k}$, and let
$x_{i},y_{i}$ be the ends of $P_{i}$.

######  Claim 6.3.

Every $X\subseteq\\{x_{1},\ldots,x_{r}\\}$ satisfies $|N(X)|\geq 2|X|(\log
n)^{50}$.

###### Proof.

Let $i_{j}$ be such that $x_{i}\in e_{i_{j}}$, for $j\in[r]$, and suppose that
$i_{1}<\ldots<i_{r}$. We claim that
$\left|N(x_{j})\cap(N(x_{j+1})\cup\ldots\cup N(x_{r}))\cap V_{1}\right|\leq
2i_{j}$, for $j\in[r]$. Indeed, the forest $F_{i_{j}}$ uses at most $2i_{j}$
vertices from $V_{1}$. Because $x_{j}$ remains a leaf in $F_{i_{j}}$, the
vertices $x_{j}$ and $x_{\ell}$, for $\ell\in[j+1,r]$, have no common
neighbours in $V_{1}-V(F_{i_{j}})$, showing that $x_{j}$ has at most $2i_{j}$
neighbours in $V_{1}$ that are also neighbours of a vertex in
$\\{x_{j+1},\ldots,x_{r}\\}$, as claimed.

We additionally claim that, if $v$ is a leaf of $F$ and a vertex in $e_{i}$,
then $|N(v)\cap V_{1}|\geq 2i+2(\log n)^{50}$. Recall that $M$ has at most
$\frac{d}{50}$ edges $e$ with $\bar{d}(e)\leq d$, for every $d$. Since there
are at least $i$ edges $e$ in $M$ with $\bar{d}(e)\leq\bar{d}(e_{i})$, it
follows that $\bar{d}(e_{i})\geq 50i$. Recalling Assumption (a) and that
$\bar{d}(e_{i})\geq(\log n)^{51}$, we find that $|N(v)\cap
V_{1}|\geq\frac{1}{10}\bar{d}(v)\geq\max\\{5i,(\log n)^{51}\\}\geq 2i+2(\log
n)^{50}$.

Writing $X=\\{x_{i_{1}},\ldots,x_{i_{\rho}}\\}$, where
$i_{1}<\ldots<i_{\rho}$, we have

$\displaystyle|N(X)|\geq\left|N(X)\cap V_{1}\right|$
$\displaystyle\geq\sum_{j\in[\rho]}\left(|N(x_{i_{j}})\cap
V_{1}|-\left|N(x_{i_{j}})\cap\left(N(x_{i_{j+1}})\cup\ldots\cup
N(x_{i_{\rho}})\right)\cap V_{1}\right|\right)$
$\displaystyle\geq\sum_{j\in[\rho]}\left(2i_{j}+2(\log
n)^{50}-2i_{j}\right)=\rho\cdot 2(\log n)^{50}=2|X|(\log n)^{50},$

proving the claim. ∎

An analogous argument shows that $|N(Y)|\geq 2|Y|(\log n)^{50}$ for every
$Y\subseteq\\{y_{1},\ldots,y_{r}\\}$. Thus, if
$X\subseteq\\{x_{1},\ldots,x_{r},y_{1},\ldots,y_{r}\\}$, without loss of
generality the set $X^{\prime}:=X\cap\\{x_{1},\ldots,x_{r}\\}$ has size at
least $\frac{1}{2}|X|$, and then by the claim $|N(X)|\geq|N(X^{\prime})|\geq
2|X^{\prime}|(\log n)^{50}\geq|X|(\log n)^{50}$. Assumption (b) thus shows
that there exist paths $P_{1},\ldots,P_{r-1}$, where $P_{i}$ has ends
$y_{i},x_{i+1}$, and the interiors of the $P_{i}$’s are pairwise vertex-
disjoint and contained in $V_{2}$. Because $F$ was chosen so as not to contain
vertices from $V_{2}$, the union $P_{1}\cup\ldots\cup P_{r-1}\cup F$ is a path
$P_{M}$ that contains $M$ and no other edges from $G^{\prime}$.

Take $\mathcal{Q}:=\\{P_{M}:M\in\mathcal{M}\\}$. We claim that
$\mathcal{P}\cup\mathcal{Q}$ separate the edges of $G^{\prime}$. Indeed, given
edges $e,f$ in $G^{\prime}$, it is easy to see that one of $P(e)$ and
$P_{M(e)}$ contains $e$ but not $f$.

To summarise $\mathcal{P}\cup\mathcal{Q}$ is a collection of at most $211n$
paths that separates the edges $e$ of $G^{\prime}$, as required. ∎

The following easy corollary of Lemma 6.1 shows that weak robust expanders
have linear separating path systems.

######  Corollary 6.4.

Let $2^{-9}\leq\varepsilon<1$ and $s\geq(\log n)^{51}$. Suppose that $G$ is a
weak $(\varepsilon,s)$-expander. Then there is a collection $\mathcal{P}$ of
at most $636n$ paths that separates the edges in $G$.

###### Proof.

Note that we may assume that $n$ is large (otherwise take $G_{1}=G$ and
$\mathcal{P}=\emptyset$). Let $\\{V_{1},V_{2},V_{3}\\}$ be a random partition
of $V(G)$, chosen uniformly at random. By Lemma 6.1, with high probability,
there is a collection of paths $\mathcal{P}_{i}$ of size at most $211n$ that
separates $G[V_{i+1}\cup V_{i+2}]$ (indices taken modulo $3$); fix an outcome
of $V_{1},V_{2},V_{3}$ that has these properties. Let $\mathcal{Q}_{i}$ be a
collection of at most $n$ paths that decomposes $G[V_{i+1}\cup V_{i+2}]$, for
$i\in[3]$.

We claim that
$\mathcal{P}:=\mathcal{P}_{1}\cup\mathcal{P}_{2}\cup\mathcal{P}_{3}\cup\mathcal{Q}_{1}\cup\mathcal{Q}_{2}\cup\mathcal{Q}_{3}$
separates the edges of $G$. Indeed, consider two edges $e,f$ in $G$, and pick
$i\in[3]$ so that $e\in G[V_{i+1}\cup V_{i+2}]$ (notice that such $i$ exists
but need not be unique). If $f\in G[V_{i+1}\cup V_{i+2}]$ then there is a path
in $\mathcal{P}_{i}$ that contains $e$ but not $f$, and otherwise there is a
path in $\mathcal{Q}_{i}$ that contains $e$ but not $f$.

To complete the proof it suffices to observe that $|\mathcal{P}|\leq 3\cdot
211n+3n\leq 636n$. ∎

Finally, we prove the first key lemma (Lemma 3.1), restated here. See 3.1

###### Proof of Lemma 3.1.

We assume that $n$ is large (otherwise, we can take $G_{1}=G$ and
$\mathcal{P}=\emptyset$). Take $s=(\log n)^{51}$, $\varepsilon=2^{-8}$ and
$t=\frac{2n}{3}$. Apply Lemma 4.1 to obtain a collection $\mathcal{H}$ of
pairwise edge-disjoint $(\varepsilon,s)$-expanders that covers all but at most
$24sn(\log n)^{3}$ edges of $G$ and satisfies $\sum_{H\in\mathcal{H}}|H|\leq
2n$. Let $G_{1}$ be the subgraph of $G$ spanned by edges not covered by
$\mathcal{H}$. Then $e(G_{1})\leq n(\log n)^{55}$ and the graphs in
$\mathcal{H}$ are weak $(\frac{\varepsilon}{2},s)$-expanders.

Apply Corollary 6.4 (with $\frac{\varepsilon}{2}$ and $s$) to each
$H\in\mathcal{H}$ to obtain a collection $\mathcal{P}_{H}$ of at most $636|H|$
paths that separates $H$. Let $\mathcal{Q}_{H}$ be a collection of at most
$|H|$ paths that decomposes $H$ (which exists by Theorem 1.2). Take
$\mathcal{P}:=\bigcup_{H\in\mathcal{H}}(\mathcal{P}_{H}\cup\mathcal{Q}_{H})$.

We claim that $\mathcal{P}$ separates $G-G_{1}$. To see this, consider two
edges $e,f$ in $G-G_{1}$ and let $H\in\mathcal{H}$ be a graph containing $e$.
If $f\in H$ then $\mathcal{P}_{H}$ has a path containing $e$ but not $f$, and
otherwise $\mathcal{Q}_{H}$ has such a path.

To finish, note the following bound.

$\displaystyle|\mathcal{P}|$
$\displaystyle\leq\sum_{H\in\mathcal{H}}(|\mathcal{P}_{H}|+|\mathcal{Q}_{H}|)\leq\sum_{H\in\mathcal{H}}637|H|\leq
1300n.$

So the graph $G_{1}$ and the collection of paths $\mathcal{P}$ satisfy the
requirements of the lemma. ∎

##  7 Expanding with forbidden sets

As a preparation for the proof of the second key lemma, in this section we
prove a variant of Lemma 3.2 from [31], which allows one to expand a set of
vertices $A$ while avoiding another set $X$, provided that $X$ has a small
intersection with each ball around $A$ (in [31] the authors list two other
properties of $X$ that guarantee the expansion of $A$ while avoiding $X$, but
we shall not use them). In both cases, the conclusion is that the radius-$i$
ball around $A$ in $G-X$ is large. In [31] this was only shown for specific,
fairly large values of $i$, whereas here we give a general lower bound that
can be applied for any $i$, as per our needs later on.

Following [31], say that a vertex set $A$ has _$k$ -limited contact_ with a
vertex set $X$ in a graph $G$ if $\left|N_{G}(B_{H-X}^{i-1}(A))\cap
X\right|\leq ki$ for every integer $i\geq 1$. The following lemma is similar
to Lemma 3.2 in [31], but tailored to our needs.

######  Lemma 7.1.

For every $\varepsilon>0$ there exists $k_{0}=k_{0}(\varepsilon)$ such that
the following holds for $k\geq k_{0}(\varepsilon)$. Suppose that $G$ is an
$n$-vertex $\varepsilon$-expander, and let $A$ and $X$ be disjoint subsets of
$V(G)$ where $|A|\geq k^{3}$ and $A$ has $k$-limited contact with $X$. Then
$\left|B_{G-X}^{i}(A)\right|>\min\\{2^{i^{1/4}},n/2\\}$, for every integer
$i\geq 1$.

###### Proof.

Write $H:=G-X$ and $B_{i}:=B_{H}^{i}(A)$ for $i\geq 0$. Our task is thus to
show $|B_{i}|>\min\\{2^{i^{1/4}},n/2\\}$ for $i\geq 1$.

######  Claim 7.2.

For every integer $i\geq 0$, either $|B_{i}|>n/2$ or
$|N_{H}(B_{i})|\geq\frac{\varepsilon|B_{i}|}{2(\log|B_{i}|)^{2}}$.

###### Proof.

We prove the claim by induction on $i$. Let $i\geq 0$ be such that
$|B_{i}|\leq n/2$ and suppose that the statement holds for $j$ with $0\leq
j<i$. (We will prove the induction base and step simultaneously.)

Since $B_{j}$ is the disjoint union of $B_{j-1}$ and $N_{H}(B_{j-1})$, we have

$\displaystyle|B_{j}|\geq\left(1+\frac{\varepsilon}{2(\log|B_{j-1}|)^{2}}\right)|B_{j-1}|\geq\left(1+\frac{\varepsilon}{2(\log|B_{i}|)^{2}}\right)|B_{j-1}|,$

for $j\in[i]$, using that $B_{j-1}\subseteq B_{i}$. Iterating this, we get

$|B_{i}|\geq\left(1+\frac{\varepsilon}{2(\log|B_{i}|)^{2}}\right)^{i}|A|.$ (4)

(Notice that this inequality holds for $i=0$, as $B_{0}=A$, allowing us to
treat the induction base and step simultaneously.)

We conclude that $|B_{i}|\geq\max\\{k^{3},i^{3}\\}$. Indeed, if $i\leq k$ this
holds because $|B_{i}|\geq|A|\geq k^{3}$. So suppose that $i>k$ and
$|B_{i}|<i^{3}$. Then (4) implies

$|B_{i}|\geq\left(1+\frac{\varepsilon}{2(\log
i^{3})^{2}}\right)^{i}|A|\geq\exp\left(\frac{\varepsilon i}{36(\log
i)^{2}}\right)\geq i^{3},$

using that $i$ is large (which follows from $k$ being large and the assumption
$i>k$). This is a contradiction, proving that
$|B_{i}|\geq\max\\{k^{3},i^{3}\\}$. Write $m:=\max\\{k,i\\}$. Then

$\frac{\varepsilon|B_{i}|}{(\log|B_{i}|)^{2}}\geq\frac{\varepsilon
m^{3}}{(\log m)^{2}}\geq 4m^{2}\geq 2k(i+1),$ (5)

using that $m$ is large.

Recall that $|X\cap N_{G}(B_{i})|\leq k(i+1)$ (this is what it means for $A$
to have $k$-limited contact with $X$) and notice that $N_{G}(B_{i})-X\subseteq
N_{H}(B_{i})$. Thus,

$\displaystyle|N_{H}(B_{i})|\geq|N_{G}(B_{i})|-k(i+1)\geq\frac{\varepsilon|B_{i}|}{(\log|B_{i}|)^{2}}-k(i+1)\geq\frac{\varepsilon|B_{i}|}{2(\log|B_{i}|)^{2}},$

where the second inequality follows from expansion (using $|B_{i}|\leq n/2$),
and the third inequality follows from (5). This proves the induction
hypothesis for $i$. ∎

Suppose that $i\geq 1$ satisfies $|B_{i}|\leq\min\\{2^{i^{1/4}},n/2\\}$. Since
$|B_{i}|\geq|A|\geq k^{3}$, it follows that $2^{i^{1/4}}\geq k^{3}$. In
particular, $i$ is large. By Claim 7.2, every $j\in[i]$ satisfies

$\displaystyle|B_{j}|=|B_{j-1}|+|N_{H}(B_{j-1})|\geq\left(1+\frac{\varepsilon}{2(\log|B_{j-1}|)^{2}}\right)|B_{j-1}|\geq\left(1+\frac{\varepsilon}{2\sqrt{i}}\right)|B_{j-1}|,$

using that $B_{j-1}\subseteq B_{i}$ and the assumption
$|B_{i}|\leq\min\\{2^{i^{1/4}},n/2\\}$. Iterating this, we get

$\displaystyle|B_{i}|\geq\left(1+\frac{\varepsilon}{2\sqrt{i}}\right)^{i}\geq\exp\left(\frac{\varepsilon
i}{4\sqrt{i}}\right)>2^{i^{1/4}},$

using that $i$ is large, and yielding a contradiction. ∎

##  8 Proof of Lemma 3.2: separating sparse expanders

In this section we prove the second key lemma, Lemma 3.2. The proof will be
split into two parts: Lemma 8.1, proved in Section 8.1, and Lemma 8.4, proved
in Section 8.2. In both parts, we are presented with an expander $G$ on $n$
vertices and number $d$, and we wish to separate edges of $G$ by $O(n+e(G)/d)$
paths. In the first part, we separate edges that touch large degree vertices,
and in the second part we consider expanders with small maximum degree and
many vertices. Lemma 3.2 itself is proved in Section 8.3.

###  8.1 Dealing with large degree vertices

The following lemma shows that given an expander $G$ on $n$ vertices and a
number $d$, there is a collection of $O(n+e(G)/d)$ paths that separate all
edges of $G$ except for a remainder with maximum degree at most $d^{7}$. Take
$L_{1}$ to be the set of vertices of degree at least $d^{7}$ and $L_{2}$ to be
the set of vertices outside of $L_{1}$ that send at least four edges into
$L_{1}$. Note that we can separate the edges of $G[L_{1},V(G)-(L_{1}\cup
L_{2})]$ by $O(n)$ single edges, so it suffices to separate the edges in
$G^{\prime}:=G[L_{1}]\cup G[L_{1},L_{2}]$.

To do so, as usual we first decompose $G^{\prime}$ into $O(n+e(G)/d)$ paths
$\mathcal{P}$ of length at most $d$. Then, for each $v\in L_{2}$ we pick a
family of $d(v,L_{1})$ paths of length $2$ with the central vertex being $v$
and the other two vertices in $L_{1}$ such that each edge between $v$ and
$L_{1}$ is covered twice, and each such $2$-path intersects each path in
$\mathcal{P}$ in at most one edge. Then, we find a collection $\mathcal{M}$ of
$O(n+e(G)/d)$ graphs $M$, which are disjoint unions of at most $d$ edges and
$2$-paths, such that $\mathcal{P}\cup\mathcal{M}$ separates $G^{\prime}$. Now
it suffices to show that each $M\in\mathcal{M}$ can be extended to a path that
avoids using other edges in $E:=\bigcup_{e\in E(M)}P(e)$ (where $P(e)$ is the
unique path in $\mathcal{P}$ that contains $e$). Take $F$ to be a linear
forest that extends $M$, avoids the edges in $E$, and minimises the number of
components and then edges under these assumptions. We show that $F$ must be a
path, using Lemma 7.1 and that all leaves in $F$ have degree at least $d^{7}$
in $G$, and are thus easy to expand.

######  Lemma 8.1.

Let $\varepsilon>0$ and let $d$ be sufficiently large. Suppose that $G$ is an
$n$-vertex $\varepsilon$-expander. Then there is a subgraph $G_{1}\subseteq G$
with maximum degree at most $d^{7}$ and a collection $\mathcal{P}$ of at most
$17\max\\{n,e(G)/d\\}$ paths in $G$ that separates the edges of $G-G_{1}$.

###### Proof.

Write $m:=e(G)$ and $k:=\max(m/d,n)$.

Let $L_{1}$ be the set of vertices in $G$ with degree at least $d^{7}$ and let
$L_{2}$ be the set of vertices outside of $L_{1}$ that have at least four
neighbours in $L_{1}$. Write $H_{1}:=G[L_{1}]\cup G[L_{1},L_{2}]$ and
$H_{2}:=G[L_{1},V(G)-(L_{1}\cup L_{2})]$. Let $\mathcal{P}_{1}$ be a
collection of at most $n+m/d\leq 2k$ paths of length at most $d$ that
decomposes $H_{1}$; such a collection exists by Corollary 1.3. For an edge $e$
in $H_{1}$, let $P(e)$ be the unique path in $\mathcal{P}_{1}$ that contains
$e$.

For each $u\in L_{2}$, let $v_{1},\ldots,v_{d_{u}}$, where
$d_{u}:=d(u,L_{1})$, be an ordering of the neighbours of $u$ in $L_{1}$ such
that $uv_{i}$ and $uv_{i+1}$ are not in the same path in $\mathcal{P}_{1}$,
for $i\in[d_{u}]$ (indices taken modulo $d_{u}$). Notice that such an ordering
exists because $d_{u}\geq 4$ and the paths in $\mathcal{P}_{1}$ are pairwise
edge-disjoint. Define $\mathcal{A}_{u}:=\\{v_{i}uv_{i+1}:i\in[d_{u}]\\}$ for
$u\in L_{2}$ and $\mathcal{A}:=\left(\bigcup_{u\in
L_{2}}\mathcal{A}_{u}\right)\cup E(G[L_{1}])$, so $\mathcal{A}$ is a
collection of edges and $2$-paths.

######  Claim 8.2.

There is a collection $\mathcal{M}$ of at most $12k$ graphs which are disjoint
unions of at most $d$ edges and $2$-paths from $\mathcal{A}$, such that each
path in $\mathcal{A}$ is a component in exactly one graph $M\in\mathcal{M}$;
and every path in $\mathcal{P}_{1}$ shares at most one edge with any
$M\in\mathcal{M}$.

###### Proof.

Let $\mathcal{M}$ be a collection of $12k$ graphs that are disjoint unions of
at most $d$ paths from $\mathcal{A}$, such that: each $A\in\mathcal{A}$ is a
component in at most one $M\in\mathcal{M}$; every path in $\mathcal{P}_{1}$
shares at most one edge with any $M\in\mathcal{M}$; and a maximum number of
paths in $\mathcal{A}$ are components in some graph in $\mathcal{M}$. We claim
that every edge and $2$-path in $\mathcal{A}$ is a component in some
$M\in\mathcal{M}$. Indeed, suppose not, and let $A\in\mathcal{A}$ be an edge
or $2$-path which is not a component in any $M\in\mathcal{M}$.

Notice that $|\mathcal{A}|\leq m$, so there are at most $m/d$ graphs
$M\in\mathcal{M}$ with $d$ components.

We claim that every vertex $v\in L_{1}\cup L_{2}$ is in at most $2n$ paths in
$\mathcal{A}$. Indeed, if $v\in L_{1}$ then there are at most $|L_{1}|$ edges
in $\mathcal{A}$ that contain $v$ and at most $2|L_{2}|$ paths of length $2$
in $\mathcal{A}$ that contain $v$, because each edge in $G[L_{1},L_{2}]$ is
used by exactly two such $2$-paths. If $v\in L_{2}$ then $v$ is in at most
$2|L_{1}|$ paths of length $2$ in $\mathcal{A}$ (and in no edges in
$\mathcal{A}$). Either way, there are at most $2|L_{1}|+2|L_{2}|\leq 2n$ paths
in $\mathcal{A}$ that contain $v$. As $|V(A)|\leq 3$, it follows that $A$
shares a vertex with at most $6n$ paths in $\mathcal{A}$. In particular, there
are most $6n$ graphs $M\in\mathcal{M}$ such that $A$ and $M$ share a vertex.

Notice also that each path in $\mathcal{P}_{1}$ has at most $n$ edges and thus
intersects the edges of at most $2n$ paths in $\mathcal{A}$. Thus, there are
at most $4n$ graphs $M\in\mathcal{M}$ for which there is a path
$P\in\mathcal{P}_{1}$ that shares an edge with both $A$ and $M$.

In summary, since $m/d+6n+4n\leq 11k<12k$, there is $M\in\mathcal{M}$ such
that $M$ has fewer than $d$ components, $A$ and $M$ do not share a vertex, and
there is no path $P\in\mathcal{P}_{1}$ that shares an edge with $A$ and $M$.
Thus we can replace $M$ by $M\cup A$, contradicting the maximality of
$\mathcal{M}$. ∎

Let $\mathcal{M}$ be a collection as guaranteed by the above claim. For a
graph $M\in\mathcal{M}$, write $E_{M}=\bigcup_{e\in E(M)}E(P(e))$ and
$X_{M}:=V(E_{M})-V(M)$ (so $E_{M}$ is the set of edges that appear on paths
from $\mathcal{P}_{1}$ that share edges with $M$, and $X_{M}$ is the set of
vertices on such paths, minus the vertices of $M$). Note that $|X_{M}|\leq
2d^{2}$ (there are at most $2d$ edges in $M$, each of which causes the
insertion of at most $d$ vertices into $X_{M}$).

######  Claim 8.3.

There is a path in $G$ that contains $M$ and avoids the edges in $E_{M}-E(M)$,
for $M\in\mathcal{M}$.

###### Proof.

Fix $M\in\mathcal{M}$. For convenience, write $E:=E_{M}$ and $X:=X_{M}$. Let
$\mathcal{Q}$ be a collection of pairwise vertex-disjoint paths of length at
least $2$ in $G-X$ with the following properties.

  1. (a)

The union of $M$ and the paths in $\mathcal{Q}$ is a path forest whose
components alternate between components of $M$ and paths in $\mathcal{Q}$,
starting and ending with a path in $M$. In particular, $|\mathcal{Q}|\leq d$.

  2. (b)

Subject to (a), $|\mathcal{Q}|$ is maximal.

  3. (c)

Subject to (a) and (b), $\sum_{Q\in\mathcal{Q}}\ell(Q)$ is minimal.

Denote the path forest, which is the union of $M$ and paths in $\mathcal{Q}$,
by $F$.

Let $R$ be a component in $F$, let $u$ be an end of $R$, and let
$X_{u}:=(X\cup V(F))-\\{u\\}$. We claim that the following holds for $r\geq
1$.

$\left|N_{G}\\!\left(B_{G-X_{u}}^{r-1}(u)\right)\cap V(F)\right|\leq(r+4)d.$
(6)

Suppose this is not the case. Because $|V(M)|\leq 3d$ vertices and
$|\mathcal{Q}|\leq d$, there is a path $Q\in\mathcal{Q}$ such that

$\left|N_{G}\\!\left(B_{G-X_{u}}^{r-1}(u)\right)\cap
V(Q^{\circ})\right|\geq\frac{(r+4)d-3d}{d}\geq r+1,$ (7)

where $Q^{\circ}$ is the interior of $Q$. Let $R^{\prime}$ be the component of
$F$ that contains $Q$. Let $v$ be one of the ends of $Q$; if $R^{\prime}=R$
take $v$ to be the further end of $Q$ from $u$ in $R$ (see Figures 1 and 2).
Let $w$ be the first vertex in $Q$ (starting from $v$) in
$N_{G}(B_{G-X_{u}}^{r-1}(u))\cap V(Q^{\circ})$, and let $Q_{1}$ be the subpath
of $Q$ that starts at $v$ and ends at $w$. Take $Q_{2}$ to be a shortest path
in $G$ from $u$ to $w$ whose interior vertices are not in $V(F)\cup X$. By
choice of $w$ we have $\ell(Q_{2})\leq r$. Finally, let $Q^{\prime}$ be the
concatenation of $Q_{1}$ and $Q_{2}$ and define
$\mathcal{Q}^{\prime}:=(\mathcal{Q}-\\{Q\\})\cup\\{Q^{\prime}\\}$.

Figure 1: The case $R^{\prime}\neq R$. The crosses signify the vertices in
$N_{G}\\!\left(B_{G-X_{u}}^{r-1}(u)\right)\cap V(Q^{\circ})$, and the blue
paths replace $R$ and $R^{\prime}$ in the path forest
$\mathcal{E}\cup\mathcal{Q}^{\prime}$. Figure 2: The case $R^{\prime}=R$. The
crosses are as above, and the blue path replaces $R$ in
$\mathcal{E}\cup\mathcal{Q}^{\prime}$.

Notice that the paths in $\mathcal{Q}^{\prime}$ are pairwise vertex-disjoint
paths of length at least $2$ in $G-X$ (in particular, $Q^{\prime}$ was indeed
chosen to have length at least $2$ and be in $G-X$). Notice also that
$\mathcal{Q}^{\prime}$ satisfies (a). Indeed, if $R^{\prime}=R$ then by choice
of $v$ we have that $(R-Q)\cup Q^{\prime}$ is a path, and if $R^{\prime}\neq
R$ then $((R\cup R^{\prime})-Q)\cup Q^{\prime}$ is a vertex-disjoint union of
two paths. Other components of $F$ are not affected by the switch from
$\mathcal{Q}$ to $\mathcal{Q}^{\prime}$. Clearly,
$|\mathcal{Q}^{\prime}|=|\mathcal{Q}|$. Finally, notice that
$\ell(Q^{\prime})=\ell(Q_{1})+\ell(Q_{2})\leq\ell(Q_{1})+r<\ell(Q_{1})+\ell(Q-Q_{1})$,
where the last inequality holds because $Q-Q_{1}$ is a path with at least $r$
interior vertices, due to (7). This implies that
$\sum_{Q\in\mathcal{Q}^{\prime}}\ell(Q)<\sum_{Q\in\mathcal{Q}}\ell(Q)$,
contradicting (c), and thus proving (6).

We now conclude that $F$ is a path, namely it has exactly one component.
Suppose not, and let $R_{1}$ and $R_{2}$ be two components in $F$. Let $u_{j}$
be an end of $R_{j}$, for $j\in[2]$. By (a), both $u_{1}$ and $u_{2}$ are ends
of paths in $M$, and thus have degree at least $d^{7}$ in $G$. Let
$A_{j}:=N_{G}(u_{j})-(X\cup V(F))$. Then

$|A_{j}|\geq|N_{G}(u_{j})|-|X|-|N_{G}(u_{j})\cap V(F)|\geq
d^{7}-d(d+1)-5d\geq(9d^{2})^{3},$

using (6) (with $r=1$), $|X|\leq 2d^{2}$ and that $d$ is large. Also,

$\left|N_{G}\Big{(}B_{G-V(F)-X}^{r-1}(A_{j})\Big{)}\cap\big{(}V(F)\cup
X\big{)}\right|\leq(r+5)d+2d^{2}+1\leq 9rd^{2},$

using (6) (with $r+1$), where the $2d^{2}+1$ term accounts for $X\cup\\{u\\}$.
In particular, $A_{j}$ has $9d^{2}$-limited contact with $V(F)$ in
$G^{\prime}$ (the notion of limited contact was defined at the beginning of
Section 7). Take $r=(\log n)^{4}$. Then, by Lemma 7.1,
$|B^{r}_{G-V(F)-X}(A_{j})|>n/2$ for $j\in[2]$. Hence, there is a path $Q$ in
$G-V(F)-X$ joining $A_{1}$ and $A_{2}$. Let $Q^{\prime}$ be the extension of
$Q$ by edges from $u_{j}$ to $A_{j}$, for $j\in[2]$. Take
$\mathcal{Q}^{\prime}:=\mathcal{Q}\cup\\{Q^{\prime}\\}$. Then
$\mathcal{Q}^{\prime}$ is a collection of pairwise vertex-disjoint paths of
length at least $2$ in $G-X$ that satisfy (a) and
$|\mathcal{Q}^{\prime}|>|\mathcal{Q}|$, contradicting (b). This proves that
$F$ consists of a single component.

We claim that $F$ satisfies the requirements of the claim. Clearly, $F$
contains $M$. Moreover, any edge in $F$ which is not in $E(M)$ is incident
with at least one vertex which is not in $X_{M}\cup V(M)=V(E_{M})$ and thus it
is not in $E_{M}$. ∎

For $M\in\mathcal{M}$, denote by $P_{M}$ the paths whose existence is
guaranteed by Claim 8.3. To prove the theorem, take $\mathcal{P}$ to be the
union of $\mathcal{P}_{1}$, $\mathcal{P}_{2}$ and the edges of
$H_{2}=G[L_{1},V(G)-(L_{1}\cup L_{2})]$ (each edge in $H_{2}$ is considered as
a separate path in $\mathcal{P}$). Notice that
$|\mathcal{P}|=|\mathcal{P}_{1}|+|\mathcal{P}_{2}|+e(H_{2})\leq 2k+12k+3n\leq
17k=17\max\\{n,e(G)/d\\}$.

We claim that $\mathcal{P}$ separates all edges in $G$ that touch $L_{1}$. To
see this, consider two distinct edges, $e$ and $f$, that touch $L_{1}$. If
$e\in E(H_{1})$ then $e$ itself is a path in $\mathcal{P}$ (which obviously
does not contain $f$). Otherwise, either the path $P(e)$ contains $e$ but not
$f$, or there exists $M\in\mathcal{M}$ that contains $e$ but not $f$ and then
$P_{M}$ contains $e$ but not $f$.

Take $G_{1}:=G-L_{1}$. Then $G_{1}$ has maximum degree at most $d^{7}$, and
the previous paragraph shows that $\mathcal{P}$ separates the edges of
$G-G_{1}$. This proves Lemma 8.1. ∎

###  8.2 Sparse expanders with small maximum degree

The next lemma shows that given a ‘somewhat robust’ expander $G$ on $n$
vertices with maximum degree at most $d^{7}$, where $n$ is large in terms of
$d$, the edges of $G$ can be separated by $O(n+e(G)/d)$ paths. The proof is
very similar in structure to the proof of Lemma 8.1. We first decompose $G$
into paths $\mathcal{P}$ and find matchings $\mathcal{M}$, such that
$|\mathcal{P}|,|\mathcal{M}|=O(n+e(G)/d)$, the union
$\mathcal{P}\cup\mathcal{M}$ separates $G$, the paths in $\mathcal{P}$ and
matchings in $\mathcal{M}$ have size at most $d$, and for any two edges $e,f$
in the same matching, the paths $P(e)$ and $P(f)$ are far apart in $G$ (we
need $n$ to be large with respect to $d$ to be able to satisfy the latter
property).

Now it remains to show that for each $M\in\mathcal{M}$ there is a path that
contains $M$ and avoids $E:=\bigcup_{e\in M}P(e)-E(M)$. As before, we take $F$
to be a path forest that extends $M$, avoids edges in $E$, and minimises the
number of components and then edges. We again use Lemma 7.1 to deduce that $F$
is a path. This time we do so by first showing that small-radius balls around
any leaf of $F$ expand well, using that such balls have few edges of $E$ (by
assumption on $M$) and the moderate robustness property. We can then expand
such balls further similarly to the proof of Lemma 8.1, using that we now
start from sizeable sets.

######  Lemma 8.4.

Let $\varepsilon>0$, let $d$ be sufficiently large, let $n\geq 2^{(\log
d)^{7}}$, and let $s\geq(k_{0}(\varepsilon)_{\ref{lem:expand-limited-
contact}}+3)^{3}$. Suppose that $G$ is an $n$-vertex
$(\varepsilon,s,d)$-expander with maximum degree at most $d^{7}$. Then there
is a collection $\mathcal{P}$ of at most $5\max\\{n,e(G)/d\\}$ paths in $G$
that separates the edges of $G$.

###### Proof.

As before, write $m:=e(G)$ and $k:=\max\\{n,m/d\\}$. Let $\mathcal{P}_{1}$ be
a collection of at most $n+m/d\leq 2k$ paths of length at most $d$ that
decompose the edges in $G$; it exists by Corollary 1.3. For an edge $e$ denote
by $P(e)$ the unique path in $\mathcal{P}_{1}$ that contains $e$. Write
$r_{0}=(\log d)^{5}$.

######  Claim 8.5.

There is a decomposition $\mathcal{M}$ of $G$ of size $3k$ such that every
$M\in\mathcal{M}$ satisfies: $M$ is a matching of size at most $d$; and the
paths $P(e)$ and $P(f)$ are a distance at least $2r_{0}$ apart for every
distinct $e,f\in M$.

###### Proof.

Let $\mathcal{M}$ be a collection of $3k$ pairwise edge-disjoint matchings
that satisfy the conditions of the claim, and together cover a maximum number
of edges in $G$. We claim that $\mathcal{M}$ covers all edges of $G$. Suppose
not, and let $e\in E(G)-\bigcup\mathcal{M}$.

As $e(G)=m$, there are at most $m/d$ matchings $M\in\mathcal{M}$ of size $d$.

We have the following upper bound on the ball of radius $2r_{0}$ around
$P(e)$.

$\big{|}B_{G}^{2r_{0}}(P(e))\big{|}\leq|P(e)|\cdot(1+d^{7}+\ldots+(d^{7})^{2r_{0}})\leq
d^{14r_{0}+2},$

using the maximum degree assumption, that $|P(e)|\leq d+1$, and that $d$ is
large. Notice that every $P\in\mathcal{P}_{1}$ intersects the edges of at most
$d$ matchings $M\in\mathcal{M}$, implying that each edge $f$ is in
$\bigcup_{h\in M}P(h)$ for at most $d$ matchings $M\in\mathcal{M}$. It follows
from the maximum degree assumption that every vertex $u$ is in $\bigcup_{h\in
M}P(h)$ for at most $d^{8}$ matchings $M\in\mathcal{M}$. Hence, the sets
$B_{G}^{2r_{0}}(P(e))$ and $\bigcup_{h\in M}P(h)$ share a vertex, for at most
$d^{8}\cdot d^{14r_{0}+2}\leq d^{14r_{0}+10}\leq 2^{(\log d)^{7}}\leq n$
matchings $M$, where for the last inequality we used the assumption on $n$ and
$d$. In other words, $P(e)$ is at distance at least $2r_{0}$ from
$\bigcup_{h\in M}P(h)$, for all but at most $n$ matchings $M\in\mathcal{M}$.

To summarise, since $m/d+n<3k$, there is a matching $M\in\mathcal{M}$ such
that $|M|<d$ and $P(e)$ and $\bigcup_{h\in M}P(h)$ are a distance at least
$2r_{0}$ apart. We can thus replace $M$ by $M\cup\\{e\\}$, a contradiction to
the maximality of $\mathcal{M}$. ∎

Let $\mathcal{M}$ be a decomposition of $G$ into matchings, as guaranteed by
the above claim. For an edge $e$, denote by $M(e)$ the unique matching in
$\mathcal{M}$ that contains $e$.

######  Claim 8.6.

There is a path in $G$ that contains all edges in $M$ and avoids the edges in
$\bigcup_{e\in M}(P(e)-\\{e\\})$, for $M\in\mathcal{M}$.

###### Proof.

Fix $M\in\mathcal{M}$, and write $E:=\bigcup_{e\in M}P(e)$ and
$G^{\prime}:=G-E$. Let $\mathcal{Q}$ be a collection of pairwise vertex-
disjoint paths in $G^{\prime}$ with the following properties.

  1. (a)

The union of $M$ with the paths in $\mathcal{Q}$ is a path forest whose paths
alternate between $M$ and $\mathcal{Q}$, starting and ending with an edge from
$M$.

  2. (b)

Subject to (a), $|\mathcal{Q}|$ is maximal.

  3. (c)

Subject to (a) and (b), $\sum_{Q\in\mathcal{Q}}\ell(Q)$ is minimal.

Denote the path forest which is the union of $M$ and $\mathcal{Q}$ by $F$.

Let $u$ be an end of a path in $F$, let $v$ be the neighbour of $u$ in $F$ (so
$uv\in M$), let $R$ be the component in $F$ that contains $u$, and write
$X_{u}:=V(F)-\\{u\\}$. We claim the following, for $r<r_{0}$,

$\left|N_{G}\left(B_{G^{\prime}-X_{u}}^{r-1}(u)\right)\cap V(F)\right|\leq
r+1.$ (8)

Suppose this is violated for some $r\leq r_{0}$. As edges in $M$ are a
distance at least $2r_{0}$ apart in $G$, the set
$N_{G}(B_{G^{\prime}-X_{u}}^{r-1}(u))\cap V(M)$ is contained in $\\{v\\}$, so
it has size at most $1$. Hence there is a path $Q\in\mathcal{Q}$ such that
either $v$ is not an end of $Q$ and $N_{G}(B_{G^{\prime}-X_{u}}^{r-1}(u))\cap
V(Q^{\circ})\neq\emptyset$ or $v$ is an end of $Q$ and
$\big{|}N_{G}(B_{G^{\prime}-X_{u}}^{r-1}(u))\cap V(Q^{\circ})\big{|}\geq r+1$.

Suppose that the former holds, and let $Q\in\mathcal{Q}$ be a path, none of
whose ends is $v$, that satisfies $N_{G}(B_{G^{\prime}-X_{u}}^{r-1}(u))\cap
V(Q^{\circ})\neq\emptyset$. Let $w_{0}$ be a vertex in this intersection, let
$Q_{0}$ be a shortest path in $G^{\prime}$ from $u$ to $w_{0}$ whose interior
avoids $X_{u}$; so $\ell(Q_{0})\leq r<r_{0}$. Denote the ends of $Q$ by
$w_{1}$ and $w_{2}$, where if $Q$ is in $R$ then $w_{1}$ is further away from
$u$ in $R$. Let $Q_{i}$ be the subpath of $Q$ from $w_{0}$ to $w_{i}$, for
$i\in[2]$. Notice that $\ell(Q_{i})\geq r_{0}$, because of the assumption that
edges in $M$ are a distance at least $2r_{0}$ apart in $G$; indeed, otherwise
the concatenation $Q_{0}Q_{i}$ of $Q_{0}$ and $Q_{i}$ is a path of length
shorter than $2r_{0}$ between two distinct edge in $M$. Write
$\mathcal{Q}^{\prime}:=\mathcal{Q}-\\{Q\\}\cup\\{Q_{0}Q_{1}\\}$. It is easy to
check that $\mathcal{Q}^{\prime}$ is a collection of vertex-disjoint paths in
$G^{\prime}$ that satisfies (a), $|\mathcal{Q}^{\prime}|=|\mathcal{Q}|$, and
$\sum_{Q\in\mathcal{Q}^{\prime}}\ell(Q)<\sum_{Q\in\mathcal{Q}}\ell(Q)$,
contradicting (c).

It remains to consider the second case, namely that $Q\in\mathcal{Q}$ has ends
$w_{1}$ and $w_{2}$, where $w_{2}=v$, and
$\big{|}N_{G}(B^{r-1}_{G^{\prime}-X_{u}}(u))\cap
V(\mathcal{Q}^{\circ})\big{|}\geq r+1$. Let $w_{0}$ be the vertex in the
intersection which is furthest away from $w_{2}$ in $Q$ and let $Q_{0}$ be a
shortest path from $u$ to $w_{0}$ in $G^{\prime}$ whose interior avoids
$X_{u}$; so $\ell(Q_{0})\leq r$. Let $Q_{i}$ be the subpath of $Q$ from
$w_{0}$ to $w_{i}$, for $i\in[2]$. Then $\ell(Q_{2})\geq r+1$ by assumption on
the intersection size $\big{|}N_{G}(B^{r-1}_{G^{\prime}-X_{u}}(u)\cap
V(\mathcal{Q}^{\circ})\big{|}$. Defining
$\mathcal{Q}^{\prime}:=\mathcal{Q}-\\{Q\\}\cup\\{Q_{0}w_{0}Q_{1}\\}$, we reach
a contradiction as in the previous paragraph. Thus (8) is proved.

We now conclude the following.

$\left|B_{G^{\prime}-X_{u}}^{r_{0}}(u)\right|\geq 2^{(\log d)^{2}}\geq d^{8}.$
(9)

Write $G^{\prime\prime}:=G-P(uv)$. We claim that
$B_{G^{\prime}-X_{u}}^{r}(u)=B_{G^{\prime\prime}-X_{u}}^{r}(u)$ for every
$r\leq r_{0}$. Indeed, this holds because
$G^{\prime\prime}=G^{\prime}-\bigcup_{f\in M-\\{uv\\}}P(f)$, and $P(f)$ is a
distance at least $2r_{0}$ away from $uv$ in $G$ for every $f\in M-\\{uv\\}$.
In particular, (8) implies

$\left|N_{G^{\prime\prime}}\left(B^{r-1}_{G^{\prime\prime}-X_{u}}(u)\right)\cap
X_{u}\right|\leq r+1,$ (10)

for $r<r_{0}$. We claim further that $G^{\prime\prime}$ is an
$\varepsilon$-expander. To see this, let $X\subseteq V(G^{\prime\prime})$
satisfy $1\leq|X|\leq 2n/3$. Let $E^{\prime\prime}$ be the set of edges from
$P(uv)$ that touch $X$. Then $|E^{\prime\prime}|\leq\min\\{2|X|,d\\}$ and
$N_{G^{\prime\prime}}(X)=N_{G-E^{\prime\prime}}(X)$. Thus, as $G$ is an
$(\varepsilon,s,d)$-expander and $s\geq 2$,
$|N_{G^{\prime\prime}}(X)|=|N_{G-E^{\prime\prime}}(X)|\geq\frac{\varepsilon|X|}{(\log|X|+1)^{2}}$,
as required for $\varepsilon$-expansion. Note also that $G$ has minimum degree
at least $s+1$, by $(\varepsilon,s,d)$-expansion, implying that
$G^{\prime\prime}$ has minimum degree at least $s-1$. Write
$A_{u}:=N_{G^{\prime\prime}-X_{u}}(u)\cup\\{u\\}$. Then (10) implies
$|A_{u}|\geq|N_{G^{\prime\prime}}(u)|-2\geq s-3$ and
$\big{|}N_{G^{\prime\prime}}(B^{r-1}_{G^{\prime\prime}-X_{u}}(A_{u}))\cap
X_{u}\big{|}\leq r+2\leq 3r$ for $r\leq r_{0}-2$. Write
$X_{u}^{\prime}:=X_{u}\cap
N_{G^{\prime\prime}}(B^{r_{0}-3}_{G^{\prime\prime}-X_{u}}(u))$. Then $A_{u}$
has $3$-limited contact with $X_{u}^{\prime}$. Using that $s$ is large, Lemma
7.1 shows $|B_{G^{\prime\prime}-X_{u}^{\prime}}^{r_{0}-2}(A_{u})|\geq
2^{(r_{0}-2)^{1/4}}\geq 2^{(\log d)^{2}}\geq d^{8}$. This proves (9), as
$B_{G^{\prime\prime}-X_{u}}^{r_{0}-1}(u)=B_{G^{\prime\prime}-X_{u}^{\prime}}^{r_{0}-2}(A_{u})$.

Next, we follow the proof of Claim 8.3 quite closely to show that the set
$B_{G^{\prime}-X_{u}}^{r_{0}}(u)$ expands. Define $V:=\bigcup_{e\in
M}V(P(e))$, $B_{u}:=B_{G^{\prime}-X_{u}}^{r_{0}}(u)-V$ and $Y:=V\cup V(F)$.
Notice that $|B_{u}|\geq d^{8}-d(d+1)\geq d^{7}$ by (9) and since $|V|\leq
d(d+1)$. We claim the following for $r\geq 1$.

$\left|N_{G}\\!\left(B^{r-1}_{G-Y}(B_{u})\right)\cap V(F)\right|\leq
d(r+r_{0}+1).$ (11)

The proof of this is very similar to that of (6) in Claim 8.3. Suppose this
does not hold for some $r\geq 1$. Because $|V(M)|\leq 2d$ and
$|\mathcal{Q}|\leq d$, there is a path $Q\in\mathcal{Q}$ such that

$\big{|}N_{G}(B^{r-1}_{G-Y}(B_{u}))\cap
V(Q^{\circ})\big{|}\geq\frac{d(r+r_{0}+3)-2d}{d}\geq r+r_{0}+1.$

Let $R^{\prime}$ be the component in $F$ that contains $Q$. Denote the ends of
$Q$ by $w_{1}$ and $w_{2}$, where $w_{1}$ is further from $u$ in $R$ if
$R^{\prime}=R$. Let $w_{0}$ be the vertex in $N_{G}(B^{r-1}_{G-Y}(B_{u}))\cap
V(Q^{\circ})$ which is closest to $w_{1}$ in $Q$, and let $Q_{0}$ be a
shortest path in $G^{\prime}$ from $u$ to $w_{0}$ whose interior avoids $Y$;
so $\ell(Q_{0})\leq r+r_{0}$. Let $Q_{i}$ be the subpath of $Q$ from $w_{0}$
to $w_{i}$, for $i\in[2]$; then $\ell(Q_{2})\geq r+r_{0}+1$. Taking
$\mathcal{Q}^{\prime}:=\mathcal{Q}-\\{Q\\}\cup\\{Q_{0}w_{0}Q_{1}\\}$ yields
the desired contradiction to (c). Thus (11) is proved.

Next, we deduce the following.

$\big{|}B_{G-Y}^{(\log n)^{4}}(B_{u})\big{|}>n/2.$ (12)

Notice that (11) implies $\big{|}N_{G}(B_{G-Y}^{r-1}(B_{u}))\cap Y\big{|}\leq
d(r+r_{0}+d+2)\leq 3d^{2}r$ for $r\geq r_{0}$ (using that $d$ is large), i.e.
$B_{u}$ has $3d^{2}$-limited contact with $Y$ in $G$. As $|B_{u}|\geq
d^{7}\geq(3d^{2})^{3}$, Lemma 7.1 proves (12).

Finally, we conclude that $F$ consists of a single component; namely, it is a
path. Suppose not, and let $u_{1}$ and $u_{2}$ be ends of distinct components
in $F$. By (12), the sets $B^{(\log n)^{4}}_{G-Y}(B_{u_{1}})$ and $B^{(\log
n)^{4}}_{G-Y}(B_{u_{2}})$ intersect, showing that there is a path $Q$ in
$G^{\prime}$ from $u_{1}$ to $u_{2}$ whose interior avoids $V(F)$. Taking
$\mathcal{Q}^{\prime}:=\mathcal{Q}\cup\\{Q^{\prime}\\}$, we reach a
contradiction to (b). We have thus proved that $F$ is a path. As it contains
$M$ and has no other edges in $\bigcup_{e\in M}P(e)$, it satisfies the
requirements of Claim 8.6. ∎

For $M\in\mathcal{M}$, let $P_{M}$ be a path as guaranteed by Claim 8.6. Write
$\mathcal{P}_{2}:=\\{P_{M}:M\in\mathcal{M}\\}$, and take
$\mathcal{P}:=\mathcal{P}_{1}\cup\mathcal{P}_{2}$. Then
$|\mathcal{P}|\leq|\mathcal{P}_{1}|+|\mathcal{P}_{2}|\leq 5k$. Notice that
$\mathcal{P}$ separates the edges of $G$. Indeed, given $e,f\in E(G)$, then
one of $P(e)$ and $M(e)$ contains $e$ but not $f$. Thus Lemma 8.4 is proved. ∎

###  8.3 Proof of Lemma 3.2

Finally, we put everything together to prove Lemma 3.2, restated here. The
proof follows quite straightforwardly from Lemmas 8.1 and 8.4.

See 3.2

###### Proof of Lemma 3.2.

Let $G$ be a graph on $n$ vertices with average degree $d$, where $d$ is
large. Take $\varepsilon:=1/48$ and apply Lemma 4.1 with $\varepsilon$, $s=0$
and $t=2n/3$ (the last choice does not matter as $t$ does not play a role when
$s=0$) to obtain a collection $\mathcal{H}$ of $\varepsilon$-expanders that
decomposes $G$ and satisfies $\sum_{H\in\mathcal{H}}|H|\leq 2n$.

Apply Lemma 8.1 to each $H\in\mathcal{H}$, to obtain a subgraph
$F_{H}\subseteq H$ and a collection $\mathcal{P}_{H}$ of paths in $H$ such
that: $F_{H}$ has maximum degree at most $d^{7}$; $|\mathcal{P}_{H}|\leq
17\max\\{|H|,e(H)/d\\}$; and $\mathcal{P}_{H}$ separates the edges of
$H-F_{H}$. Let $\mathcal{P}^{\prime}_{H}$ be collection of at most $|H|$ paths
decomposing $H-F_{H}$ (which exists by Theorem 1.2).

Now, for each $H\in\mathcal{H}$, apply Lemma 4.1 to $F_{H}$ with
$\varepsilon$, $s_{\ref{lem:decompose-
expanders}}=\left((k_{0}(\varepsilon))_{\ref{lem:expand-limited-
contact}}+3\right)^{3}$ and $t_{\ref{lem:decompose-expanders}}=d$, to obtain a
collection $\mathcal{F}_{H}$ of pairwise edge-disjoint subgraphs of $F_{H}$
that cover all but at most $24s|F_{H}|(\log d+1)^{2}$ edges of $F_{H}$ and
satisfy $\sum_{F\in\mathcal{F}_{H}}|F|\leq 2|F_{H}|$. Denote by $E_{H}$ the
set of edges in $H$ uncovered by $\mathcal{F}_{H}$.

Let $\mathcal{F}_{1}$ be the collection of graphs
$F\in\bigcup_{H\in\mathcal{H}}\mathcal{F}_{H}$ that satisfy $|F|\geq 2^{(\log
d)^{7}}$ and let
$\mathcal{F}_{2}:=(\bigcup_{H\in\mathcal{H}}F_{H})-\mathcal{F}_{1}$. Apply
Lemma 8.4 to each $F\in\mathcal{F}_{1}$ to obtain a collection
$\mathcal{Q}_{F}$ of paths in $F$ such that $|\mathcal{Q}_{F}|\leq
5\max\\{|F|,e(F)/d\\}$ and $\mathcal{Q}_{F}$ separates the edges of $F$.

Take $\mathcal{P}$ to be the union of the collections
$\mathcal{P}_{H},\mathcal{P}^{\prime}_{H}$, for $H\in\mathcal{H}$, and
$\mathcal{Q}_{F}$, for $F\in\mathcal{F}_{1}$. Define $G_{1}$ to be the graph
on vertices $V(G)$ and edges $\bigcup_{H\in\mathcal{H}}E_{H}$. We show that
the statement of Lemma 3.2 holds (with $\mathcal{H}_{\ref{lem:reduce-small-
deg}}=\mathcal{F}_{2}$). Notice that the graphs in $\mathcal{F}_{2}$ indeed
are pairwise edge-disjoint, because the graphs in $\mathcal{H}$ are pairwise
edge-disjoint and so are the graphs in $\mathcal{F}_{H}$ for every
$H\in\mathcal{H}$. Moreover, $|F|\leq 2^{(\log d)^{7}}$ for every
$F\in\mathcal{F}_{2}$, by choice of $\mathcal{F}_{2}$. Finally,

$\displaystyle\sum_{F\in\mathcal{F}_{1}\cup\mathcal{F}_{2}}|F|=\sum_{H\in\mathcal{H}}\sum_{F\in\mathcal{F}_{H}}|F|\leq\sum_{H\in\mathcal{H}}2|F_{H}|\leq\sum_{H\in\mathcal{H}}2|H|\leq
4n,$

using the choice of $\mathcal{H}$ and $\mathcal{F}_{H}$. In particular,
$\sum_{F\in\mathcal{F}_{2}}|F|\leq 4n$. Thus (1) is proved.

Next, notice that

$\displaystyle|\mathcal{P}|$
$\displaystyle\leq\sum_{H\in\mathcal{H}}\left(|\mathcal{P}_{H}|+|\mathcal{P}^{\prime}_{H}|\right)+\sum_{F\in\mathcal{F}_{1}}|Q_{F}|$
$\displaystyle\leq\sum_{H\in\mathcal{H}}18(|H|+e(H)/d)+\sum_{F\in\mathcal{F}_{1}}5(|F|+e(F)/d)$
$\displaystyle\leq 36n+18e(G)/d+20n+5e(G)/d\leq 80n.$

For the second inequality we used that the graphs in $\mathcal{H}$ are
pairwise edge-disjoint and similarly for $\mathcal{F}_{1}$, and for the last
inequality we used that $G$ has average degree $d$.

We claim that $\mathcal{P}$ separates the edges of
$G^{\prime}:=G-G_{1}-\bigcup_{F\in\mathcal{F}_{2}}F$. Indeed, let $e$ and $f$
be distinct edges in $G^{\prime}$, and let $H\in\mathcal{H}$ satisfy $e\in H$.
If $e\in H-F_{H}$, then if $f\notin H-F_{H}$ there is a path in
$\mathcal{P}_{H}^{\prime}$ that contains $e$ but not $f$, and otherwise there
is such a path in $\mathcal{P}_{H}$. Now suppose $e\in F_{H}$ and let
$F\in\mathcal{F}_{H}$ be a graph that contains $e$. Then $\mathcal{Q}_{F}$ has
a path that contains $e$ but not $f$. This proves (2).

Finally, we have

$\displaystyle 2e(G_{1})\leq
2\sum_{H\in\mathcal{H}}|E_{H}|\leq\sum_{H\in\mathcal{H}}48s|F_{H}|(\log
d+1)^{2}\leq\frac{1}{2}\sum_{H\in\mathcal{H}}|H|(\log d)^{3}\leq n(\log
d)^{3},$

using that $d$ is large and $s$ is a constant (it depends only on
$\varepsilon$, which itself is a constant). This completes the proof of (3)
and Lemma 3.2. ∎

##  9 Conclusion

Recall that $\operatorname{sep}^{*}(G)$ is the size of a smallest weakly-
separating path system for $G$, and $\operatorname{sep}^{*}(n)$ is the maximum
of $\operatorname{sep}^{*}(G)$ over all $n$-vertex graphs $G$;
$\operatorname{sep}(G)$ and $\operatorname{sep}(n)$ are defined analogously
for strong separation.

In this paper we proved that $\operatorname{sep}(n)=O(n\log^{\star}n)$. This
is significant progress from the essentially trivial bound of $O(n\log n)$,
towards a conjecture of, independently, Falgas-
Ravry–Kittipassorn–Korándi–Narayanan and the author [12], and
Balogh–Csaba–Martin–Pluhár [3], that $\operatorname{sep}(n)=O(n)$.

It is plausible that our methods could be used to fully settle this
conjecture. For example, one could try to prove a statement like the
following, by induction on $n$. Suppose that $G$ is an $\varepsilon$-expander
and let $H$ be a subgraph of $G$ on $n$ vertices. Then the edges of $H$ can be
separated using $O(n)$ paths in $G$. To accomplish this, it would suffice to
find $O(n)$ paths in $G$ that separated all edges of $H$ touching a set $V$ of
$\Omega(n)$ vertices in $H$. An obstruction to achieving this is a graph $H$
as follows: $H$ has average degree $d$, but almost all vertices in $H$ have
degree much lower that $d$ (say, at most $\log\log d$), and, moreover, there
are relatively small sets of low degree vertices in $H$ with few low degree
neighbours.

In fact, the authors of [12] suggest that, perhaps,
$\operatorname{sep}^{*}(n)=(1+o(1))n$; it is easy to see that this bound would
be tight by considering complete graphs. If true, this is likely to be very
hard to prove. Indeed, even the restriction to complete graph seems hard.
Wickes [41] proved that
$\operatorname{sep}^{*}(K_{n})\leq(\frac{21}{16}+o(1))n$ for any integer $n$,
and that $\operatorname{sep}^{*}(K_{n})$ when $n=p\text{ or }p+1$ for some
prime $p$. It would be nice, and perhaps not completely out of reach, to prove
that $\operatorname{sep}^{*}(K_{n})=(1+o(1))n$. It also makes sense to study
$\operatorname{sep}(K_{n})$.

### Acknowledgements

I would like to thank António Girão for reminding me of this problem and
making the connection to sublinear expansion. I am grateful to Matija Bucić
and Richard Montgomery for insightful discussions regarding their very nice
paper [7] and for giving me a copy of an early draft. Some of the research
leading up to this paper was done while the author attended the MFO workshop
Combinatorics, Probability and Computing, held in Oberwolfach in April 2022,
and the BIRS workshop Cross Community Collaborations in Combinatorics, held in
Banff in June 2022. I am thankful to the organisers of both workshops for
inviting me, and to MFO and BIRS for providing great infrastructure for
research.

## References

  * [1] R. Aharoni and P. Haxell, _Hall’s theorem for hypergraphs_ , J. Graph Theory 35 (2000), 83–88.
  * [2] N. Alon and J. H. Spencer, _The probabilistic method_ , John Wiley & Sons, 2016\.
  * [3] J. Balogh, B. Csaba, R. R. Martin, and A. Pluhár, _On the path separation number of graphs_ , Discr. Appl. Math. 213 (2016), 26–33.
  * [4] A. Blanché, M. Bonamy, and N. Bonichon, _Gallai’s path decomposition in planar graphs_ , arXiv:2110.08870 (2021).
  * [5] B. Bollobás and A. Scott, _On separating systems_ , Europ. J. Combin. 28 (2007), 1068–1071.
  * [6] B. Bollobás and A. Scott, _Separating systems and oriented graphs of diameter two_ , J. Combin. Theory Ser. B 97 (2007), 193–203.
  * [7] M. Bucić and R. Montgomery, _Towards the Erdős-Gallai Cycle Decomposition Conjecture_ , (2022), preprint.
  * [8] M.-C. Cai, _On separating systems of graphs_ , Discr. Math. 49 (1984), 15–20.
  * [9] N. Dean and M. Kouider, _Gallai’s conjecture for disconnected graphs_ , Discr. Math. 213 (2000), 43–54.
  * [10] P. Erdős, A. W. Goodman, and L. Pósa, _The representation of a graph by set intersections_ , Can. J. Math. 18 (1966), 106–112.
  * [11] P. Erdős and A. Hajnal, _On chromatic number of graphs and set-systems_ , Acta Math. Acad. Sci. Hungar 17 (1966), 61–99.
  * [12] V. Falgas-Ravry, T. Kittipassorn, D. Korándi, S. Letzter, and B. Narayanan, _Separating path systems_ , J. Combin. 5 (2014), 335–354.
  * [13] I. G. Fernández, J. Hyde, H. Liu, O. Pikhurko, and Z. Wu, _Disjoint isomorphic balanced clique subdivisions_ , arXiv:2204.12465 (2022).
  * [14] I. G. Fernández, J. Kim, Y. Kim, and H. Liu, _Nested cycles with no geometric crossings_ , Proc. Am. Math. Soc. Ser. B 9 (2022), 22–32.
  * [15] I. G. Fernández and H. Liu, _How to build a pillar: a proof of Thomassen’s conjecture_ , arXiv:2201.07777 (2022).
  * [16] F. Foucaud, S. Gravier, R. Naserasr, A. Parreau, and P. Valicov, _Identifying codes in line graphs_ , J. Graph Theory 73 (2013), no. 4, 425–448.
  * [17] F. Foucaud and M. Kovše, _Identifying path covers in graphs_ , J. Discrete Algorithms 23 (2013), 21–34.
  * [18] G. Hansel, _Nombre minimal de contacts de fermeture nécessaires pour réaliser une fonction booléenne symétrique de n variables_ , C. R. Acad. Sci. Paris 258 (1964), 6037–6040.
  * [19] N. J. A. Harvey, M. Patrascu, Y. Wen, S. Yekhanin, and V. W. S. Chan, _Non-adaptive fault diagnosis for all-optical networks via combinatorial group testing on graphs_ , IEEE INFOCOM 2007-26th IEEE International Conference on Computer Communications, IEEE, 2007, pp. 697–705.
  * [20] J. Haslegrave, J. Hu, J. Kim, H. Liu, B. Luan, and G. Wang, _Crux and long cycles in graphs_ , arXiv:2107.02061 (2021).
  * [21] J. Haslegrave, J. Hyde, J. Kim, and H. Liu, _Ramsey numbers of cycles versus general graphs_ , arXiv:2112.03893 (2021).
  * [22] J. Haslegrave, J. Kim, and H. Liu, _Extremal density for sparse minors and subdivisions_ , Int. Math. Res. Not. (2021), 15505–15548.
  * [23] I. Honkala, M. G. Karpovsky, and S. Litsyn, _Cycles identifying vertices and edges in binary hypercubes and 2-dimensional tori_ , Discrete Appl. Math. 129 (2003), 409–419.
  * [24] G. Katona, _On separating systems of a finite set_ , J. Combin. Theory 1 (1966), 174–194.
  * [25] J. Kim, H. Liu, M. Sharifzadeh, and K. Staden, _Proof of Komlós’s conjecture on Hamiltonian subsets_ , Proc. Lond. Math. Soc. 115 (2017), 974–1013.
  * [26] J. Komlós and E. Szemerédi, _Topological cliques in graphs_ , Combin. Probab. Comput. 3 (1994), 247–256.
  * [27] , _Topological cliques in graphs II_ , Combin. Probab. Comput. 5 (1996), 79–90.
  * [28] A. Kündgen, D. Mubayi, and P. Tetali, _Minimal completely separating systems of k-sets_ , J. Combin. Theory Ser. A 93 (2001), 192–198.
  * [29] S. Letzter and A. Girão, _Immersion of complete digraphs in Eulerian digraphs_ , Israel J. Math., to appear.
  * [30] H. Liu and R. Montgomery, _A proof of Mader’s conjecture on large clique subdivisions in C 4-free graphs_ , J. Lond. Math. Soc. 95 (2017), 203–222.
  * [31] , _A solution to Erdős and Hajnal’s odd cycle problem_ , arXiv:2010.15802 (2020).
  * [32] H. Liu, G. Wang, and D. Yang, _Clique immersion in graphs without a fixed bipartite graph_ , J. Combin. Theory Ser. B 157 (2022), 346–365.
  * [33] L. Lovász, _On covering of graphs_ , Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 231–236.
  * [34] C. Ramsay and Roberts I. T., _Minimal completely separating systems of sets_ , Australas. J. Combin. 13 (1996), 129–150.
  * [35] A Rényi, _On random generating elements of a finite Boolean algebra_ , Acta Sci. Math. Szeged 22 (1961), 75–81.
  * [36] J. Spencer, _Minimal completely separating systems_ , J. Combin. Theory 8 (1970), 446–447.
  * [37] J. Tapolcai, L. Rónyai, and P.-H. Ho, _Link fault localization using bi-directional m-trails in all-optical mesh networks_ , IEEE Transactions on Communications 61 (2012), 291–300.
  * [38] J. Tapolcai, B. Wu, and P.-H. Ho, _On monitoring and failure localization in mesh all-optical networks_ , IEEE INFOCOM 2009, IEEE, 2009, pp. 1008–1016.
  * [39] I. Tomon, _Robust (rainbow) subdivisions and simplicial cycles_ , arXiv:2201.12309 (2022).
  * [40] I. Wegener, _On separating systems whose elements are sets of at most k elements_ , Discr. Math. 28 (1979), 219–222.
  * [41] B. Wickes, _Separating path systems for the complete graph_ , arXiv:2209.04302 (2022).
  * [42] L. Yan, _On path decompositions of graphs_ , Ph.D. thesis, Arizona State University, 1998.