# A counterexample to the coarse Menger conjecture

Tung Nguyen
Princeton University,
Princeton, NJ 08544, USA Supported by AFOSR grants A9550-19-1-0187 and
FA9550-22-1-0234, and by NSF grants DMS-1800053 and DMS-2154169. Alex Scott
University of Oxford,
Oxford, UK Supported by EPSRC grant EP/X013642/1 Paul Seymour
Princeton University,
Princeton, NJ 08544, USA Supported by AFOSR grants A9550-19-1-0187 and
FA9550-22-1-0234, and by NSF grants DMS-1800053 and DMS-2154169.

(November 19, 2023; revised )

###### Abstract

It was conjectured, independently by two sets of authors, that for all
integers $k,d\geq 1$ there exists $\ell>0$, such that if $S,T$ are subsets of
vertices of a graph $G$, then either there are $k$ paths between $S,T$,
pairwise at distance at least $d$, or there is a set $X\subseteq V(G)$ with
$|X|\leq k-1$ such that every path between $S,T$ contains a vertex with
distance at most $\ell$ from some member of $X$. The result is known for
$k\leq 2$, but we will show that it is false for all $k\geq 3$, even if $G$ is
constrained to have maximum degree at most three. We also give a proof of the
result when $k=2$ that is simpler than the previous proofs.

##  1 Introduction

If $X$ is a subset of the vertex set of a graph $G$, or a subgraph of $G$, and
the same for $Y$, then $d(X,Y)$ denotes the distance between $X,Y$, that is,
the number of edges in the shortest path of $G$ with one end in $X$ and the
other in $Y$. We are interested in when there are $k$ paths in $G$ between two
given sets that are pairwise at distance at least $d$. The following
conjecture was proposed by Albrechtsen, Huynh, Jacobs, Knappe, and Wollan [1],
and independently by Georgakopoulos and Papasoglu [3]:

###### 1.1

False conjecture: For all integers $k,d\geq 1$ there exists $\ell>0$ with the
following property. Let $G$ be a graph and let $S,T\subseteq V(G)$; then
either

  * •

there are $k$ paths between $S,T$, pairwise at distance at least $d$; or

  * •

there is a set $X\subseteq V(G)$ with $|X|\leq k-1$ such that every path
between $S,T$ contains a vertex with distance at most $\ell$ from some member
of $X$.

Both sets of authors proved the result for $k=2$, but the $k\geq 3$ case
remained open. Here we give a counterexample with $d=k=3$, and with maximum
degree at most three. We also give a simpler proof of the $k=2$ case.

The case $k=3$ was of special interest, because it is easy to see that if the
result is true when $d=3$ then it is true for general $k$ (apply the result
when $d=3$ to the $d$th power of $G$).

The case $d=2$ and general $k$ is still open. Another related conjecture,
still open, is 1.1 with the bound on $|X|$ relaxed:

###### 1.2

Conjecture: For all $k,d$ there exist $\ell,n$ such that, with $G,S,T$ as
before, either the first bullet of 1.1 holds, or there is a set $X\subseteq
V(G)$ with $|X|\leq n$ such that every path between $S,T$ contains a vertex
with distance at most $\ell$ from some member of $X$.

When $d=2$, this last conjecture was shown to be true for graphs of bounded
maximum degree by Hendrey, Norin, Steiner and Turcotte [4], and independently
by Gartland, Koorhonen and Lokshtanov [2].

Agelos Georgakopoulos brought to our attention the following variant of 1.1,
which also remains open:

###### 1.3

Conjecture: For all integers $k,d\geq 1$ there exists $\ell>0$ with the
following property. Let $G$ be a graph and let $S,T\subseteq V(G)$; then
either

  * •

there are $k$ paths between $S,T$, pairwise at distance at least $d$; or

  * •

there is a vertex $x$ of $G$ such that there do not exist $k-1$ paths between
$S$ and $T$, pairwise at distance at least $\ell$ and each with distance at
least $\ell$ from $x$.

##  2 The counterexample

In this section, for each value of $\ell>0$, we give an example of a graph
$G$, and two subsets $S,T$ of $V(G)$, such that there do not exist three paths
between $S,T$, pairwise at distance at least $3$, and for every $X\subseteq
V(G)$ with $|X|\leq 2$, there is a path $P$ between $S,T$ such that its
distance from $X$ is more than $\ell$. It is illustrated in figure 1. The two
sets $S,T$ both have size three, and there is a vertex in $S\cap T$.

$S$$T$$S$$S$$T$$T$ Figure 1: The dotted curves represent long paths.

To show that this is a counterexample, we need to check that for every
$X\subseteq V(G)$ with $|X|\leq 2$, there is a path $P$ between $S,T$ such
that its distance from $X$ is more than $\ell$; and that there do not exist
three paths between $S,T$, pairwise at distance at least $3$. The first is
easy, so let us do it now.

###### 2.1

Let $\ell\geq 1$ be an integer, and let $G$ be as in figure 1, where the
binary tree has depth more than $2\ell+2$, and each of the dotted curves
represents a path of length more than $2\ell$. Let $S,T$ be as shown in the
figure. If $X\subseteq V(G)$ with $|X|\leq 2$, then there is a path $P$
between $S,T$ such that $d(X,P)>\ell$.

Proof. Let $r$ be the root of the binary tree (the vertex at the top of the
figure). Since $r\in S\cap T$, we may assume there exists $x_{1}\in X$ such
that its distance from $r$ is at most $\ell$; and since all of the paths
represented by the dotted curves (let us call them “dotted paths”) have
distance at least $2\ell+1$ from $r$ (because the binary tree has depth more
than $2\ell+2$), they all have distance more than $\ell$ from $x_{1}$. Since
the path ($M$ say) at the bottom of the figure is between $S,T$, we may assume
that there exists $x_{2}\in X$ with distance at most $\ell$ from $M$. The set
of vertices of $G$ with distance at most $\ell$ from $x_{2}$ is either a
subset of the vertex set of one of the dotted paths in $M$, or it contains
exactly one end $v$ of a dotted path of $M$, and consists of $v$ together with
subsets of the interiors of the (at most three) dotted paths incident with
$v$. In either case, there is an end $v$ of one of the dotted paths in $M$,
such that the set of vertices of $G$ with distance at most $\ell$ from $x_{2}$
is a subset of the set consisting of $v$ together with the interiors of the
dotted paths incident with $v$. But for every choice of $v$, there is a path
between $S,T$ made by a union of dotted paths, none of them incident with $v$;
and consequently this path has distance more than $\ell$ from $X$. This proves
2.1.

To prove the second statement, that there do not exist three paths between
$S,T$, pairwise at distance at least $d$, we will prove something stronger, by
induction on the depth of the binary tree; and for that we need to allow the
binary tree to have small depth, and we need to set up some notation, so let
us define the graph more carefully.

Let $k\geq 2$ be an integer. Take a uniform binary tree $B$ with depth $k$.
Thus, $B$ has $2^{k}-1$ vertices, and a root, and every path from the root to
one of the leaves has exactly $k-1$ edges. Now add two more vertices, and let
$Z$ consist of the set of leaves of $B$ together with the two new vertices;
and add a path $M$ with vertex set $Z$, as shown in figure 2. We call the
resulting graph $G_{k}$. (To get the graph of the counterexample, we need to
replace the edges of $G_{2\ell+3}$ incident with vertices in $Z$ by long
paths, but let us not do that yet.) For each vertex $v$ of $B$ that is not a
leaf, there is a copy of some $G_{h}$ with root $v$, formed by $v$ and its
descendents in $B$, and two extra vertices; we will apply the inductive
hypothesis to these smaller graphs. Let $M$ have ends $s_{1},t_{2}$, and let
$s_{2},t_{1}$ be the neighbours in $M$ of $s_{1},t_{2}$ respectively.

$r$$s_{1}$$s_{2}$$t_{1}$$t_{2}$$q_{1}$$q_{2}$$a_{1}$$a_{2}$$b$$c$ Figure 2:
The graph $G_{k}$. (In this figure, $k=6$.) The vertex $b$ is some vertex on
the path between $a_{1}$ and $s_{1}$; it need not be adjacent to $a_{1}$, and
it might equal $a_{1}$. Its child on that path is $c$.

We will show:

###### 2.2

For each integer $k\geq 2$, if $P,Q$ are vertex-disjoint paths of $G_{k}$
between $\\{s_{1},s_{2}\\}$ and $\\{t_{1},t_{2}\\}$, then either

  * •

there is a path of length at most two between $V(P)$ and $V(Q)$ such that none
of its edges have ends in $Z$, or

  * •

one of $P,Q$ is the path of $B$ between $s_{1},t_{2}$.

Proof. We proceed by induction on $k$. If $k=1$ the result is clear, so we
assume that $k\geq 2$ and the result holds for all smaller values of $k$.
Suppose that $P,Q$ are vertex-disjoint paths of $G_{k}$ between
$\\{s_{1},s_{2}\\}$ and $\\{t_{1},t_{2}\\}$, and the first bullet of the
theorem is false. Let $r$ be the root of $B$, let $a_{1}$ be the neighbour of
$r$ in the path of $B$ between $r,s_{1}$, and define $a_{2}$ similarly.
Suppose first that neither of $P,Q$ contains $r$. Then we may assume that $P$
contains $q_{1}$ and $Q$ contains $q_{2}$, where $q_{1},q_{2}$ are as shown in
the figure; and so from the inductive hypothesis applied to the two copies of
$G_{k-1}$ with roots $a_{1}$ and $a_{2}$, $P$ contains the path of $B$ between
$s_{1},q_{2}$, and $Q$ contains the path of $B$ between $q_{1},t_{2}$. So
$a-1\in V(P)$ and $a_{2}\in V(Q)$; but $r$ is adjacent to both $a_{1},a_{2}$,
a contradiction.

So $r$ belongs to one of $P,Q$, say to $P$. We need to show that $P$ contains
the two subpaths of $B$ between $r,s_{1}$ and between $r,t_{2}$. Suppose it
does not contain the first, say; and let us call this path $A_{1}$. Choose a
maximal common subpath of $P,A_{1}$, with ends $a_{1},b$ say. (Possibly
$b=a_{1}$.) We see that $b\neq s_{1}$, since $A\not\subseteq P$; and $b$ is
not adjacent to $s_{1}$, since one of $P,Q$ must use the edge of $B$ incident
with $s_{1}$. Thus the subpath of $A$ between $b,s_{1}$ has length $h$ say,
where $h\geq 2$. Let $c$ be the child of $b$ in $V(A)$. It follows that
neither of $P,Q$ contains $c$; and this contradicts the inductive hypothesis,
applied to the copy of $G_{h-1}$ with root $c$. This proves 2.2.

From 2.2, it follows easily that the graph of figure 1, with $S,T$ as shown,
has the property that there do not exist three paths between $S,T$, pairwise
at distance at least $3$. Because if $P,Q,R$ are three such paths, one of them
contains the root $r$, and so consists just of the vertex $r$; and so the
other two cannot use $r$, and so contradict 2.2.

##  3 A simpler proof

In this section we give a proof of 1.1 when $k=2$, that is simpler than the
proofs previously announced. We need some lemmas about intervals. An interval
is a pair $(a,b)$ of integers with $a\leq b$, and its length is $b-a$. If
$\mathcal{H}$ is a set of intervals that can be written
$\mathcal{H}=\\{(a_{i},b_{i}):1\leq i\leq t\\}$ for some $t\geq 1$, such that
$0\leq a_{1}<a_{2}<\cdots<a_{t}\leq n$, and $0\leq b_{1}<\cdots<b_{t}\leq n$,
we call this the standard form for $\mathcal{H}$. Thus $\mathcal{H}$ has a
standard form if and only there do not exist distinct
$(a,b),(c,d)\in\mathcal{H}$ with $a\leq c\leq d\leq b$. (See figure 3.)

$a_{1}$$a_{2}$$a_{3}$$a_{4}$$a_{5}$$a_{6}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{5}$$b_{6}$
Figure 3: Intervals in standard form (the curves join the ends of the
intervals).

If $(a,b),(c,d)$ are intervals, we say $(a,b)$ captures $(c,d)$ if $a\leq
c\leq d\leq b$; and a set $\mathcal{H}$ of intervals captures $(c,d)$ if there
exists $(a,b)\in\mathcal{H}$ that captures $(c,d)$. For integers $\ell,n$ with
$0<\ell\leq n$, we say a set $\mathcal{H}$ of intervals is $\ell$-powerful in
$(0,n)$ if

  * •

$0\leq a\leq b\leq n$ for all $(a,b)\in\mathcal{H}$; and

  * •

$\mathcal{H}$ captures every interval of length $\ell$ captured by $(0,n)$.

Our objective is, starting with an $\ell$-powerful set $\mathcal{H}$ of
intervals, to find a subset $\mathcal{H}^{\prime}$ of $\mathcal{H}$ which is
still $\ell^{\prime}$-powerful for some $\ell^{\prime}$ not much smaller than
$\ell$, such that all the ends of all the intervals in $\mathcal{H}^{\prime}$
are far apart. (Not exactly: in standard form, we cannot arrange that
$a_{i+2}-b_{i}$ is large for each $i$, and it might even be negative, and we
cannot arrange that $a_{2}-a_{1}$ and $b_{t}-b_{t-1}$ are large, but we will
make all the other differences large). We begin with:

###### 3.1

If $0<\ell\leq n$ and $\mathcal{H}$ is a set of intervals that is
$\ell$-powerful in $(0,n)$, and minimal with this property, then in standard
form $a_{j}\geq b_{i}-\ell+2$ for all $i,j\in\\{1,\ldots,t\\}$ with $j\geq
i+2$.

Proof. (See figure 4.)

$a_{i}$$a_{i+1}$$a_{j}$$b_{i}$$b_{i+1}$$b_{j}$ Figure 4: For the proof of 3.1.

Let $1\leq i,j\leq t$ with $j\geq i+2$. From the minimality, there exists
$h\in\\{0,n-\ell\\}$ such that $(a_{i+1},b_{i+1})$ captures $(h,h+\ell)$, and
no other member of $\mathcal{H}$ captures $(h,h+\ell)$. Since $(a_{i},b_{i})$
does not capture $(h,h+\ell)$, and $a_{i}<a_{i+1}\leq h$, it follows that
$b_{i}<h+\ell$; and since $(a_{j},b_{j})$ does not capture $(h,h+\ell)$, and
$b_{j}\geq b_{i+1}\geq h+\ell$, it follows that $a_{j}>h$. Hence $a_{j}\geq
b_{i}-\ell+2$. This proves 3.1.

If $\mathcal{H}$ can be written in standard form, and
$\mathcal{H}^{\prime}\subseteq\mathcal{H}$, then $\mathcal{H}^{\prime}$ can
also be written in standard form. Some inequalities about the corresponding
numbers $a_{i},b_{i}$ are hereditary; that is, if they hold for $\mathcal{H}$
then they also hold for all its subsets $\mathcal{H}^{\prime}$. For instance,
the inequalities of 3.1 are hereditary. Let
$\mathcal{H}^{\prime}\subseteq\mathcal{H}$, and
$\mathcal{H}=\\{(a_{i},b_{i}):1\leq i\leq t\\}$ and
$\mathcal{H}^{\prime}=\\{(a_{i}^{\prime},b_{i}^{\prime}):1\leq i\leq
t^{\prime}\\}$, in standard form. If we know that $a_{j}\geq b_{i}-\ell+2$ for
all $i,j\in\\{1,\ldots,t\\}$ with $j\geq i+2$, then it follows that
$a_{j}^{\prime}\geq b_{i}^{\prime}-\ell+2$ for all
$i,j\in\\{1,\ldots,t^{\prime}\\}$ with $j\geq i+2$. Most of the other
inequalities we will prove are hereditary, and we leave verifying this to the
reader.

###### 3.2

If $0<2\ell\leq n$ and $\mathcal{H}$ is a set of intervals that is
$2\ell$-powerful in $(0,n)$, then there exists
$\mathcal{H}^{\prime}\subseteq\mathcal{H}$, minimally $\ell$-powerful in
$(0,n)$, that can be written $\mathcal{H}^{\prime}=\\{(a_{i},b_{i}):1\leq
i\leq t\\}$ in standard form, such that

  * •

$a_{j}\geq b_{i}-\ell+2$ for $1\leq i,j\leq t$ with $j\geq i+2$; and

  * •

$b_{i}-b_{i-1}\geq\ell$ for $1<i<t$, and $b_{i-1}-a_{i}\geq\ell$ for $1<i\leq
t$.

Proof. Choose $\mathcal{H}_{1}\subseteq\mathcal{H}$, minimal such that it is
$2\ell$-powerful in $(0,n)$. Let us choose
$\mathcal{H}_{2}\subseteq\mathcal{H}_{1}$, such that

  * •

$\mathcal{H}_{2}$ captures the intervals $(0,2\ell)$ and $(n-2\ell,n)$;

  * •

if $(a,b)\in\mathcal{H}_{2}$ and $b+\ell<n$ then some member of
$\mathcal{H}_{2}$ captures the interval $(b-\ell,b+\ell)$;

  * •

$\mathcal{H}_{2}$ is minimal with these properties.

It follows that we can write $\mathcal{H}_{2}$ in standard form,
$\mathcal{H}_{2}=\\{(a_{i},b_{i}):1\leq i\leq t\\}$ for some $t\geq 1$; and
$a_{1}=0$ and $b_{t}=n$; and the first bullet of the theorem holds, by 3.1. We
claim that:

(1) For $1<i<t$, $b_{i-1}\leq n-\ell$ and $(a_{i},b_{i})$ captures
$(b_{i-1}-\ell,b_{i-1}+\ell)$, and there is no $j\in\\{1,\ldots,t\\}$ with
$j\neq i$ such that $(a_{j},b_{j})$ captures $(b_{i-1}-\ell,b_{i-1}+\ell)$.

We prove this by induction on $i$, so we may assume that either $i=2$, or the
claim holds for $i-1$. Since $a_{i}>a_{1}\geq 0$ and $b_{i}<b_{t}=n$,
$(a_{i},b_{i})$ captures neither of $(0,2\ell),(n-2\ell,n)$; and so from the
minimality of $\mathcal{H}_{2}$, there exists $h\in\\{1,\ldots,t\\}$ such that
$b_{h}\leq n-\ell$ and $(a_{i},b_{i})$ captures $(b_{h}-\ell,b_{h}+\ell)$, and
there is no $j\in\\{1,\ldots,t\\}$ with $j\neq i$ such that $(a_{j},b_{j})$
captures $(b_{h}-\ell,b_{h}+\ell)$. It follows that $h<i$, since
$b_{h}<b_{i}$; and $h>i-2$, since if $h\leq i-2$ then from the inductive
hypothesis, there is no $j\neq h+1$ such that $(a_{j},b_{j})$ captures
$(b_{h}-\ell,b_{h}+\ell)$. Hence $h=i-1$. This completes the induction, and so
proves (1).

Consequently $b_{i}-b_{i-1}\geq\ell$ and $b_{i-1}-a_{i}\geq\ell$ for $1<i<t$.
For the second bullet we still need to check that $b_{t-1}-a_{t}\geq\ell$.
This is true if $b_{t-1}\geq n-\ell$, since $(a_{t},b_{t})$ captures
$(n-2\ell,n)$. If $b_{t-1}<n-\ell$, then some $(a_{j},b_{j})$ captures
$(b_{t-1}-\ell,b_{t-1}+\ell)$; and $j=t$ since $b_{j}>b_{t-1}$. This proves
that $\mathcal{H}_{2}$ satisfies the second bullet.

We claim that $\mathcal{H}_{2}$ is $\ell$-powerful in $(0,n)$. To see this,
let $0\leq h\leq n-\ell$; we must show that some member of $\mathcal{H}_{2}$
captures $(h,h+\ell)$. We may assume that $h<n-2\ell$, since some member of
$\mathcal{H}_{2}$ captures $(n-2\ell,n)$. Choose $i\in\\{1,\ldots,t\\}$
maximal such that $a_{i}\leq h$. We may assume that $b_{i}<h+\ell$, since
otherwise $(a_{i},b_{i})$ captures $(h,h+\ell)$. Hence $b_{i}<n-\ell$, and so
$(a_{i+1},b_{i+1})$ captures $(b_{i}-\ell,b_{i}+\ell)$, by (1). From the
choice of $i$, $a_{i+1}>h$; but $a_{i+1}\leq b_{i}-\ell$, so $b_{i}\geq
a_{i+1}+\ell>h+\ell$, a contradiction. This proves that $\mathcal{H}_{2}$ is
$\ell$-powerful in $(0,n)$. Choose
$\mathcal{H}^{\prime}\subseteq\mathcal{H}_{2}$, minimal such that it is
$\ell$-powerful in $(0,n)$. Then by 3.1, the first bullet of the theorem
holds; and the second still holds, since it is hereditary. This proves 3.2.

$a_{1}$$a_{2}$$a_{3}\&b_{1}$$a_{4}\&b_{2}$$a_{t}\&b_{t-2}$$b_{t-1}$$b_{t}$
Figure 5: The output of 3.3. $a_{3},b_{1}$ have been drawn in the same place
because we do not know which is larger.

###### 3.3

If $0<4\ell\leq n$ and $\mathcal{H}$ is a set of intervals that is
$4\ell$-powerful in $(0,n)$, then there exists
$\mathcal{H}^{\prime}\subseteq\mathcal{H}$, $\ell$-powerful in $(0,n)$, which
can be written $\mathcal{H}^{\prime}=\\{(a_{i},b_{i}):1\leq i\leq t\\}$ in
standard form, such that the order of the numbers $a_{1},\ldots,a_{t}$ and
$b_{1},\ldots,b_{t}$ is:

$\displaystyle
0=a_{1}<a_{2}<\min(a_{3},b_{1})<\max(a_{3},b_{1})<\min(a_{4},b_{2})<\max(a_{4},b_{2})<\cdots$
$\displaystyle\cdots<\min(a_{t},b_{t-2})<\max(a_{t},b_{t-2})<b_{t-1}<b_{t}=n.$

(See figure 5.) Every two of $a_{1},\ldots,a_{t},b_{1},\ldots,b_{t}$ differ by
at least $\ell$, except possibly the pairs $(a_{1},a_{2})$, $(b_{t-1},b_{t})$,
and $(a_{i},b_{i-2})$ for $3\leq i\leq t$.

Proof. From 3.2 with $\ell$ replaced by $2\ell$, there exists
$\mathcal{H}_{1}\subseteq\mathcal{H}$, $2\ell$-powerful in $(0,n)$, that
satisfies the inequalities of 3.2. By 3.2 again, applied to $\mathcal{H}_{1}$,
with the order of $\\{0,\ldots,n\\}$ reversed, there exists
$\mathcal{H}_{2}\subseteq\mathcal{H}_{1}$, minimally $\ell$-powerful in
$(0,n)$, such that in standard form,

  * •

$b_{i}-b_{i-1}\geq 2\ell$ for $1<i<t$, and $b_{i-1}-a_{i}\geq 2\ell$ for
$1<i\leq t$ (since these inequalities are true for $\mathcal{H}_{1}$ and are
hereditary);

  * •

$a_{i+1}-a_{i}\geq\ell$ for $1<i<t$; and

  * •

$a_{j}\geq b_{i}-\ell+2$ for all $i,j\in\\{1,\ldots,t\\}$ with $j\geq i+2$.

It follows that $b_{j}-b_{i}\geq\ell$ for all $i,j\in\\{1,\ldots,t\\}$ with
$j>i$ and $(i,j)\neq(t-1,t)$; that $a_{j}-a_{i}\geq\ell$ for all
$i,j\in\\{1,\ldots,t\\}$ with $j>i$ and $(i,j)\neq(1,2)$. Now let
$i,j\in\\{1,\ldots,t\\}$; we want to show that $|a_{j}-b_{i}|\geq\ell$, unless
$i=j-2$. If $i>j$, then $b_{i}\geq b_{j}+\ell\geq a_{j}+\ell$ as required. If
$j=i$, the minimality of $\mathcal{H}_{2}$ implies that $b_{i}-a_{i}\geq\ell$,
as required. If $i=j-1$, we have $b_{i}-a_{j}\geq 2\ell$ from the first bullet
above, as required. Now suppose that $i\leq j-3$. Hence $b_{j-2}\leq
a_{j}+\ell-2$, and $b_{j-2}\geq b_{j-3}+2\ell$; so $a_{j}+\ell-2\geq
b_{j-3}+2\ell$, that is, $a_{j}\geq b_{j-3}+\ell+2\geq b_{i}+\ell$ as
required. This proves 3.3.

Now let us deduce 1.1 when $k=2$. As we said earlier, it suffices to handle
the case when $d=3$, so we will prove:

###### 3.4

Let $G$ be a non-null graph and let $S,T\subseteq V(G)$; then either

  * •

there are two paths between $S,T$ with distance at least $3$; or

  * •

there exists $x\in V(G)$ such that every path between $S,T$ contains a vertex
with distance at most $161$ from $x$.

Proof. We assume the second outcome is false. Let $c\geq 7$ and $\ell\geq
2c+5$ be integers: we will prove that the theorem holds with $161$ replaced by
$8\ell+c+2$. We may assume that $G$ is connected, and there is a path between
$S,T$; let $R$ be such a path with minimum length, and let its vertices be
$r_{1},\ldots,r_{n-1}$ in order, where $r_{1}\in S$ and $r_{n-1}\in T$. There
is a path $P$ between $S,T$ with $d(r_{1},P)>8\ell+c+2$, and we can assume
that $d(P,R)\leq 2$, so $n-2\geq 8\ell+c+1$. In particular, $S\cap
T=\emptyset$ and there are no edges between $S,T$.

Let $W$ be the set of all vertices with distance at most $c$ from $R$. We call
the set of all vertices $v$ with $d(v,R)=c$ the surface. For each $v\in V(G)$,
if $v\in S$ and $d(v,R)\geq c+4$, let $a(v)=0$, and otherwise let $a(v)$ be
the smallest $i\in\\{1,\ldots,n-1\\}$ such that there is a path between $v$
and $r_{i}$ of length $d(v,R)$. Similarly, if $v\in T$ and $d(v,R)\geq c+4$
let $b(v)=n$, and otherwise let $b(v)$ be the largest $i\in\\{1,\ldots,n-1\\}$
such that there is a path between $v$ and $r_{i}$ of length $d(v,R)$. For each
$w\in W$, it follows from the choice of $R$ that $0\leq b(w)-a(w)\leq
2d(w,R)\leq 2c$.

Let $\mathcal{C}$ be the set of components of $G\setminus W$, and for each
$C\in\mathcal{C}$, let $N(C)$ be the set of vertices in $W$ with a neighbour
in $V(C)$. Thus $N(C)\neq\emptyset$, and $N(C)$ is a subset of the surface.
Let $a(C)$ be the smallest value of $a(v)$ for $v\in V(C)$, and define $b(C)$
similarly. Thus $0\leq a(C)\leq b(C)\leq n$ for each $C\in\mathcal{C}$.

(1) The set of intervals $\\{(a(C),b(C)):C\in\mathcal{C}\\}$ is
$16\ell$-powerful in $(0,n)$.

Let $8\ell\leq m\leq n-8\ell$; we must show that there exists
$C\in\mathcal{C}$ such that $(a(C),b(C))$ captures $(m-8\ell,m+8\ell)$. Let
$B$ be the set of all vertices of $G$ with distance at most $8\ell+c+2$ from
$r_{m}$. Let $W_{1}$ be the set of all $w\in W\setminus B$ with $a(w)\leq m$,
and let $W_{2}$ be the set of all $w\in W\setminus B$ with $b(w)\geq m$. Thus
$W_{1}\cup W_{2}=W\setminus B$. If $w\in W_{1}$, then since
$d(w,r_{m})>8\ell+c+2$ and $d(w,r_{a(w)})\leq c$, it follows that
$d(r_{a(w)},r_{m})>8\ell+2$, and so $a(w)\leq m-8\ell-3$; and similarly if
$w\in W_{2}$ then $b(w)\geq m+8\ell+3$. Thus, if $w_{1}\in W_{1}$ and
$w_{2}\in W_{2}$, then

$b(w_{2})-a(w_{1})\geq(m+8\ell+3)-(m-8\ell-3)=16\ell+6.$

There is a path between $w_{1}$ and $S$ of length at most $a(w_{1})+c-1$, and
a path between $w_{2}$ and $T$ of length at most $|E(R)|-b(w_{2})+c-1$, and,
since there is no path between $S,T$ of length less than $|E(R)|$, it follows
that

$\displaystyle d(w_{1},w_{2})$
$\displaystyle\geq|E(R)|-(a(w_{1})+c-1)-(|E(R)|-b(w_{2})+c-1)$
$\displaystyle=b(w_{2})-a(w_{1})-2(c-1)\geq(16\ell+6)-2(c-1)\geq 2.$

Consequently $W_{1}\setminus B$ and $W_{2}\setminus B$ are disjoint, and there
are no edges between them. Moreover, if $w_{1}\in S$ and $w_{2}\in W_{2}$ then
$b(w_{2})\geq m+8\ell+3\geq 16\ell+3$, and similarly

$d(w_{1},w_{2})\geq|E(R)|-(|E(R)|-b(w_{2})+c-1)\\\
=b(w_{2})-(c-1)\geq(16\ell+3)-2(c-1)\geq 2.$

So $S\cap W_{2}=\emptyset$ and there are no edges between them, and the same
for $W_{1},T$. Thus $W_{1}\cup S$ is disjoint from $W_{2}\cup T$ and there are
no edges between them.

Since the second outcome of the theorem is false, there is an $S-T$ path $P$
in $G$ disjoint from $B$. Consequently, there is a subpath $P^{\prime}$ of $P$
with first vertex in $W_{1}\cup S$, last vertex in $W_{2}\cup T$, and with no
other vertex in $W\cup B$. Since $W_{1}\cup S$ is disjoint from $W_{2}\cup T$
and there are no edges between them, $P^{\prime}$ has an internal vertex,
which is therefore not in $W$. But the only vertices of $P^{\prime}$ in $W$
are ends of $P^{\prime}$, and so there exists $C\in\mathcal{C}$ such that
$V(P^{\prime})\subseteq V(C)\cup W$. We will show that $a(C)\leq m-8\ell$ and
$b(C)\geq m+8\ell$. Let $w_{1}\in W_{1}\cup S$ and $w_{2}\in W_{2}\cup T$ be
the ends of $P^{\prime}$. Either $w_{1}\in W_{1}$, or $w_{1}\in S\setminus W$
and $d(w_{1},R)\geq c+4$, or $w_{1}\in S\setminus W$ and $d(w_{1},R)\leq c+3$,
and we claim that $a(w_{1})\leq m-8\ell$ in each case. In the first case,
$w_{1}$ has a neighbour $v\in V(C)$; and since $d(v,R)=c+1=d(w_{1},R)+1$, it
follows that $a(C)\leq a(v)\leq a(w_{1})\leq m-8\ell-3\leq m-8\ell$ as
required. In the other two cases, $w_{1}\in V(C)$, and so $a(C)\leq a(w_{1})$.
In the second case, $a(w_{1})=0\leq m-8\ell$ as required. In the third case,
when $w_{1}\in S$ and $d(w_{1},R)\leq c+3$, it follows that
$d(w_{1},r_{a(w_{1})})\leq c+3$, and since $d(w_{1},r_{m})>8\ell+c+2$, this
implies that $a(w_{1})\leq m-8\ell$ as required. This proves that $a(C)\leq
m-8\ell$ in all three cases. Similarly $b(C)\geq m+8\ell$. This proves (1).

From 3.3, with $\ell$ replaced by $4\ell$, there exists
$\mathcal{D}\subseteq\mathcal{C}$ such that the set of intervals
$\\{(a(C),b(C)):C\in\mathcal{D}\\}$ is $4\ell$-powerful in $(0,n)$, and the
members of $\mathcal{D}$ can be numbered $D_{1},\ldots,D_{t}$ such that:

  * •

$0=a(D_{1})<a(D_{2})<\cdots<a(D_{t})\leq n$, and $0\leq
b(D_{1})<b(D_{2})<\cdots<b(D_{t})=n$; and

  * •

$a(D_{i})-b(D_{i-3})\geq 4\ell$ for $4\leq i\leq t$.

(We are not using the full strength of 3.3 here; that will come later.)

(2) For $1\leq i,j\leq t$, if $j\geq i+3$ then $d(D_{i},D_{j})\geq
4\ell-2c+2$.

Suppose not. Hence there exist $w\in N(D_{i})$ and $w^{\prime}\in N(D_{j})$
such that $d(w,w^{\prime})<4\ell-2c$; and there is a path between $w,V(R)$ of
length $c$, and its end in $R$ is some $r_{k}$ where $k\leq b(D_{i})$.
Similarly there is a path between $w^{\prime},V(R)$ of length $c$, and its end
in $R$ is some $r_{k^{\prime}}$ where $k\geq a(D_{j})$. Thus there exist
$k\leq b(D_{i})$ and $k^{\prime}\geq a(D_{j})$ such that there is a path
between $r_{k},r_{k^{\prime}}$ of length less than $4\ell$. Since $R$ is a
shortest path, it follows that $4\ell-1\geq k^{\prime}-k\geq
a(D_{j})-b(D_{i})\geq 4\ell$, a contradiction. This proves (2).

Let $\Delta$ be the union of the vertex sets of the members of $\mathcal{D}$.
If $X\subseteq V(G)$, let $\Delta(X)$ be the set of $D\in\mathcal{D}$ with
$X\cap N(D)\neq\emptyset$. Let us say a joint is a subset $X\subseteq V(G)$,
inducing a connected subgraph, such that

  * •

$|\Delta(X)|\geq 2$;

  * •

if $|\Delta(X)|=2$ then $|X|\leq 3$;

  * •

if $|\Delta(X)|\leq 3$ then $|X|\leq 8$;

  * •

$|X|\leq 29$; and

  * •

every vertex of $X\cap W$ belongs to a path of $G[X]$ with both ends in the
surface.

(3) For every joint $X$, $|\Delta(X)|\leq 3$, and hence $|X|\leq 8$; and
$d(X,R)\geq c-(|X|-1)/2$.

Suppose that $|\Delta(X)|\geq 4$; then we can choose $i,j$ with $1\leq i,j\leq
t$ and $j\geq i+3$ such that $D_{i},D_{j}\in\Delta(X)$. Since $G[X]$ is
connected, there is a path between $D_{i},D_{j}$ of length at most $|X|+1\leq
30$, contrary to (2), since $4\ell-2c+2>30$. Thus $|\Delta(X)|\leq 3$.
Moreover, if $v\in X\cap W$, then since $v$ belongs to a path of $G[X]$ with
both ends in the surface, there is a path from $v$ to the surface of length at
most $(|X|-1)/2$; and since every path from the surface to $R$ has length at
least $c$, it follows that $d(v,R)\geq c-(|X|-1)/2$. This proves (3).

Let $Z$ be the union of all the joints. Each component of $G[Z\cup\Delta]$ is
called a supercomponent. Each supercomponent includes at least one member of
$\mathcal{D}$, but may be composed of many joints and members of
$\mathcal{D}$.

(4) Let $F_{1},F_{2}$ be distinct supercomponents, and let $Q$ be a path with
ends $f_{1}\in V(F_{1})$ and $f_{2}\in V(F_{2})$. If both $f_{1},f_{2}$ belong
to joints then $|Q|\geq 16$; if exactly one of $f_{1},f_{2}$ belongs to a
joint $X$ then $|Q|\geq 8$, and $|Q|\geq 24$ if $|\Delta(X)|\geq 3$; and if
neither of $f_{1},f_{2}$ belong to joints then $|Q|\geq 6$. In any case,
$d(F_{1},F_{2})\geq 5$.

Let $Q^{*}$ be the set of vertices in the interior of $Q$. Suppose first that
$f_{i}$ belongs to a joint $X_{i}$ for $i=1,2$. Then $X_{1}\cup X_{2}\cup
Q^{*}$ is not a joint (since $F_{1},F_{2}$ are distinct supercomponents). But
$|\Delta(X_{1}\cup X_{2}\cup Q^{*})|\geq 4$ (since $|\Delta(X_{i})|\geq 2$ for
$i=1,2$, and $\Delta(X_{1})\cap\Delta(X_{2})=\emptyset$), and every vertex of
$(X_{1}\cup X_{2}\cup Q^{*})\cap W$ belongs to a path of $G[X_{1}\cup
X_{2}\cup Q^{*}]$ with both ends in the surface; and so $|X_{1}\cup X_{2}\cup
Q^{*}|\geq 30$. Since $|X_{1}|,|X_{2}|\leq 8$ by (3), it follows that
$|Q^{*}|\geq 14$, and so $|Q|\geq 16$ as claimed. Thus we may assume that
$f_{2}\in D^{\prime}$ for some $D^{\prime}\in\mathcal{D}$ included in $F_{2}$,
and so $V(Q)\cap N(D^{\prime})\neq\emptyset$, and hence
$D^{\prime}\in\Delta(Q^{*})$. Next, suppose that $f_{1}\in X_{1}$ for some
joint $X_{1}$. Then $|\Delta(X_{1}\cup Q^{*})|\geq 3$, and since $X_{1}\cup
Q^{*}$ is not a joint (because $F_{1},F_{2}$ are distinct supercomponents), it
follows that either $|\Delta(X_{1}\cup Q^{*})|=3$ and $|X_{1}\cup Q^{*}|\geq
9$, or $|X_{1}\cup Q^{*}|\geq 30$. In the first case, $|\Delta(X_{1})|=2$, so
$|X_{1}|\leq 3$, and therefore $|Q^{*}|\geq 6$ and $|Q|\geq 8$; and in the
second case, $|X_{1}|\leq 8$ by (3), and so $|Q^{*}|\geq 22$ and $|Q|\geq 24$,
as claimed. Finally, we may assume that $f_{1}\in D$ for some
$D\in\mathcal{D}$ included in $F_{1}$, and so $D,D^{\prime}\in\Delta(Q^{*})$,
and since $Q^{*}$ is not a joint, $|Q^{*}|\geq 4$ and so $|Q|\geq 6$. This
proves (4).

(5) If $F_{1},F_{2}$ are distinct supercomponents, and $A$ is a path of length
at most $c+1$ between $F_{2}$ and $R$, then $d(F_{1},A)\geq 3$.

Suppose that $f_{1}\in V(F_{1})$ and $v\in V(A)$ have distance at most two.
Let $f_{2}$ be the end of $A$ in $V(F_{2})$. Suppose first that
$f_{1}\in\Delta$. Consequently every path from $f_{1}$ to $V(R)$ has length
more than $c$, and so the subpath of $A$ between $v$ and $R$ has length at
least $c-1$; and therefore the subpath from $v$ to $f_{2}$ has length at most
two. Hence there is a path $Q$ of length at most four between $f_{1},f_{2}$;
so $|Q|\leq 5$, contrary to (4). This proves that $f_{1}\notin\Delta$, and so
$f_{1}\in X_{1}$ for some joint $X_{1}$ of $F_{1}$. By (3), $d(f_{1},R)\geq
c-(|X_{1}|-1)/2$, and so the subpath of $A$ between $v,R$ has length at least
$c-(2+(|X_{1}|-1)/2)$. Hence the subpath of $A$ between $v,f_{2}$ has length
at most $3+(|X_{1}|-1)/2$. Consequently there is a path $Q$ between
$f_{1},f_{2}$ of length at most $5+(|X_{1}|-1)/2$, and so $|Q|\leq
6+(|X_{1}|-1)/2$. Since $|X_{1}|\leq 8$, and so $|Q|\leq 9$, it follows from
(4) that $f_{2}$ is not in a joint and $|\Delta(X_{1})|=2$. But then
$|X_{1}|\leq 3$, so $|Q|\leq 7$, contrary to (4). This proves (5).

Let $\mathcal{F}$ be the set of all supercomponents. For each
$F\in\mathcal{F}$, let $a(F)$ be the minimum of $a(v)$ over all $v\in V(F)$,
and define $b(F)$ similarly. Since for every $D\in\mathcal{D}$, there exists
$F\in\mathcal{F}$ with $D\subseteq F$, and hence with $a(F)\leq a(D)\leq
b(D)\leq b(F)$, it follows that the set of intervals
$\\{(a(F),b(F)):F\in\mathcal{F}\\}$ is $4\ell$-powerful. By 3.3, there exists
$\mathcal{H}\subseteq\mathcal{F}$ such that
$\\{(a(F),b(F)):F\in\mathcal{H}\\}$ is $\ell$-powerful, and it can be numbered
as $\\{H_{1},\ldots,H_{s}\\}$, where, writing $a(H_{i})=a_{i}$ and
$b(H_{i})=b_{i}$ for each $i$:

(6) The order of the numbers $a_{1},\ldots,a_{s}$ and $b_{1},\ldots,b_{s}$ is:

$\displaystyle
0=a_{1}<a_{2}<\min(a_{3},b_{1})<\max(a_{3},b_{1})<\min(a_{4},b_{2})<\max(a_{4},b_{2})<\cdots$
$\displaystyle\cdots<\min(a_{s},b_{s-2})<\max(a_{s},b_{s-2})<b_{s-1}<b_{s}=n.$

Every two of $a_{1},\ldots,a_{s},b_{1},\ldots,b_{s}$ differ by at least
$\ell$, except possibly the pairs $(a_{1},a_{2})$, $(b_{s-1},b_{s})$, and
$(a_{i},b_{i-2})$ for $3\leq i\leq s$.

$r_{1}$$r_{a_{2}}$$r_{b_{1}}$$r_{a_{3}}$$r_{a_{4}}$$r_{b_{2}}$$r_{a_{5}}$$r_{b_{3}}$$r_{b_{4}}$$r_{a_{6}}$$r_{a_{7}}$$r_{b_{5}}$$A_{2}$$B_{1}$$A_{3}$$B_{2}$$A_{4}$$B_{3}$$A_{5}$$B_{4}$$A_{6}$$B_{5}$$A_{7}$$W$$A_{1}$$Q_{1}$$Q_{2}$$Q_{3}$$Q_{4}$$Q_{5}$$Q_{6}$
Figure 6: Various paths. The dotted line is the boundary of $W$. All the
dashed lines represent paths, and the one at the bottom is $R$. The thick
dashed lines are the paths we will use to construct a pair of $S-T$ paths with
distance three. The paths $Q_{i}$ have been drawn as though their interiors
are disjoint from $W$, but they might not be; each is a path of a
supercomponent, but the supercomponent might penetrate into $W$ a short
distance, via joints. In particular the ends of each $Q_{i}$ have been drawn
exactly on the surface, but they might be slightly deeper in $W$, or just
outside of $W$.

Now we are ready to construct a pair of $S-T$ paths that are distance three
apart. (See figure 6.) Since $a(H_{1})=0$, there is a vertex $v$ of $H_{1}$
with $a(v)=0$, and hence with $v\in S$ and $d(v,R)\geq c+4$; let $A_{1}$ be
the one-vertex path consisting of this vertex. For $2\leq i\leq s$, let
$A_{i}$ be a shortest path with one end in $V(H_{i})$ and the other equal to
$r_{a_{i}}$. Similarly, define $B_{s}$ to be a one-vertex path with vertex
some $v\in V(H_{s})\cap T$ with $b(v)=0$; and for $1\leq i<s$ let $B_{i}$ be a
shortest path with one end in $V(H_{i})$ and the other equal to $r_{b_{i}}$.
It follows that $A_{i},B_{i}$ have length at most $c+1$. Let $Q_{i}$ be a path
of $H_{i}$ joining the ends of $A_{i}$ and $B_{i}$ in $H_{i}$. For $1\leq
i,j\leq n-1$, let $R(i,j)=R(j,i)$ be the subpath of $R$ with ends
$r_{i},r_{j}$. Define $b_{0}=1$ and $a_{s+1}=n-1$. It follows that the union
of the paths

  * •

$A_{i}\cup Q_{i}\cup B_{i}$ for $i\in\\{1,\ldots,s\\}$, odd; and

  * •

$R(b_{i},a_{i+2})$ for $i\in\\{0,\ldots,s-1\\}$, odd

contains an $S-T$ path. (It might not itself be a path, because for instance
the paths $B_{1},A_{3}$ might intersect). Also, the union of the paths

  * •

$A_{j}\cup Q_{j}\cup B_{j}$ for $j\in\\{1,\ldots,s\\}$, even; and

  * •

$R(b_{j},a_{j+2})$ for $j\in\\{0,\ldots,s-1\\}$, even

contains an $S-T$ path. We must check that these paths have distance at least
three. This is true if $s=1$, so we assume that $s\geq 2$. We have to check
that:

  1. (i)

$d(Q_{i},Q_{j})\geq 3$ for all $i,j\in\\{1,\ldots,s\\}$ with $i$ odd and $j$
even;

  2. (ii)

$d(A_{i},A_{j}),d(A_{i},B_{j}),d(B_{i},A_{j}),d(B_{i},B_{j})\geq 3$ for all
$i,j\in\\{1,\ldots,s\\}$ with $i$ odd and $j$ even;

  3. (iii)

$d(R(b_{i},a_{i+2}),R(b_{j},a_{j+2}))\geq 3$ for all
$i,j\in\\{0,\ldots,s-1\\}$ with $i$ odd and $j$ even;

  4. (iv)

$d(Q_{i},A_{j}),d(Q_{i},B_{j}),d(A_{i},Q_{j}),d(B_{i},Q_{j})\geq 3$ for all
$i,j\in\\{1,\ldots,s\\}$ with $i$ odd and $j$ even;

  5. (v)

$d(Q_{i},R(b_{j},a_{j+2}))\geq 3$ for all $i,j$ with $i\in\\{1,\ldots,s\\}$,
odd and $j\in\\{0,\ldots,s-1\\}$, even; and $d(R(b_{i},a_{i+2}),Q_{j})\geq 3$
for all $i,j$ with $i\in\\{0,\ldots,s-1\\}$, odd and $j\in\\{1,\ldots,s\\}$,
even; and

  6. (vi)

$d(A_{i},R(b_{j},a_{j+2})),d(B_{i},R(b_{j},a_{j+2}))\geq 3$ for all $i,j$ with
$i\in\\{1,\ldots,s\\}$, odd and $j\in\\{0,\ldots,s-1\\}$, even; and
$d(R(b_{j},a_{j+2}),A_{j}),d(R(b_{j},a_{j+2}),B_{j})\geq 3$ for all $i,j$ with
$i\in\\{0,\ldots,s-1\\}$, odd and $j\in\\{1,\ldots,s\\}$, even.

Statement (i) follows from (4). For statement (ii), suppose first that
$i,j\neq 1,s$. Since every vertex in $A_{i}$ has distance at most $c+1$ from
$r_{a_{i}}$, and the same for $B_{i},A_{j},B_{j}$, it suffices to check that
$d(r_{a_{i}},r_{a_{j}})\geq 2c+5$ and so on. But these four distances are
$|a_{i}-a_{j}|,|a_{i}-b_{j}|,|b_{i}-a_{j}|,|b_{i}-b_{j}|$ respectively, and so
are all at least $\ell\geq 2c+5$, by (6). If $i=1$ and $j\neq s$, the same
argument shows that $d(B_{1},A_{j}),d(B_{1},B_{j})\geq 3$, but we need to
check that $d(A_{1},A_{j}),d(A_{1},B_{j})\geq 3$. In this case $V(A_{1})$ is a
vertex $v\in S$, with $d(v,R)\geq c+4$. Since $A_{j},B_{j}$ both have length
at most $c+1$, it follows that $d(v,A_{j}),d(v,B_{j})\geq 3$. The argument is
similar if $i=s$ or $j=s$. This proves (ii).

For statement (iii), note that the subpaths
$R(b_{i},a_{i+2}),R(b_{j},a_{j+2})$ of $R$ are disjoint (by (6)), and the
distance between them is at least $\ell\geq 3$ (again by (6)). Statement (iv)
follows from (5). For statement (v), (3) implies that every path from a
supercomponent to $R$ has length at least $c-(8-1)/2\geq 3$. Finally, for
statement (vi), we will prove that $d(A_{i},R(b_{j},a_{j+2}))\geq 3$ for all
$i,j$ with $i\in\\{1,\ldots,s\\}$, odd and $j\in\\{0,\ldots,s-1\\}$, even (the
other statement is proved similarly). If $i=1$ then the claim is true since
$d(A_{1},R)\geq c+4\geq 3$, so we assume that $i\geq 3$. The distance between
$r_{a_{i}}$ and $R(b_{j},a_{j+2})$ is at least $\ell$, by (6); and the
distance between $r_{a_{i}}$ and each vertex of $A_{i}$ is at most $c+1$, and
so the distance between $A_{i}$ and $R(b_{j},a_{j+2})$ is at least
$\ell-c-1\geq 3$. This proves 3.4.

## References

  * [1] S. Albrechtsen, T. Huynh, R. W. Jacobs, P. Knappe, and P. Wollan, “The induced two paths problem”, arXiv:2305.04721v3.
  * [2] P. Gartland, T. Koorhonen and D. Lokshtanov, “On induced versions of Menger’s theorem on sparse graphs”, arXiv:2309.08169.
  * [3] A. Georgakopoulos and P. Papasoglu, “Graph minors and metric spaces”, arXiv:2305.07456.
  * [4] K. Hendrey, S. Norin, R. Steiner, J. Turcotte, “On an induced version of Menger’s theorem”, arXiv:2309.07905.


This avoidance of the saddle by the reactive trajectories is sketched in
figure 15 (b), where this atypical case is shown in comparison with the
typical case of figure 15 (a).

The comparison between the reactive trajectory and the nearest fixed point on
the crossed separatrix is very often the focus of attention. This is because,
as stated earlier, in systems which do not have a degenerate saddle [Bouchet
and Touchette, 2012], in the limit of energy injection and/or forcing noise
variance going to zero, the reactive trajectories are structured by
instantons, which cross the separatrix right at a saddle point (see the sketch
in figure 15 (a)). In said regime, one finds a structuration of the
bistability: an exponential dependence of the mean first passage time and
crossing probability in the noise variance, a concentration of trajectories in
phase space and a specific distribution of reactive trajectories duration, to
mention the most important features. Surprisingly enough, all these properties
were found in our reactive trajectories.

This raises the question of why do we have this apparent contradiction. There
can be several causes for such a situation:

  1. i)

The paths sampled by means of AMS could be incorrect. This can happen when the
reaction coordinate is not adapted. One then observes the apparent bias
phenomenon: most sample reactive trajectories do not follow the most likely
path [Bréhier et al., 2016, Lucente et al., 2022]. However, that type of
behaviour would show a clear distinction between the trajectory durations
computed by means of AMS and those computed by means of DNS as well as lead to
a very large relative sample variance of the probability of crossing, which is
not the case here. Moreover, when this phenomenon manifests itself, the
reactive trajectories tend to select a path that still visit the neighbourhood
of a saddle [Rolland and Simonnet, 2015].

  2. ii)

One can observe correctly computed reactive trajectories which are outside of
the instanton regime if the relevant saddle is very flat [Rolland et al.,
2016]. In that situation, one does observes an exponential growth of mean
first passage time and an exponential decay of the crossing probability, which
is our case. Meanwhile, one observes a Gaussian distribution of trajectory
duration and a linear increase of their average duration and variance, which
is not our case. Moreover, this regime still visits the neighbourhood of a
saddle, which is not our case.

  3. iii)

When the saddle in the system can become degenerate, one can observe sub-
instantons, that do not follow the expected path [Bouchet and Touchette,
2012]. However, in that case, the probability of crossing and the mean first
passage time have a very distinct scaling in exponential of the square root of
the noise variance, which is not our case.

  4. iv)

Finally, a peculiar situation has been reported following the computation of
the instanton going from a non linear traveling wave to the laminar flow in
two dimensional plane Poiseuille flow [Wan et al., 2015]. In that case,
sketched in figure 15 (b), the instanton reaches the neighbourhood of the
separatrix near a flow configuration termed a mediator state, travels along
the separatrix toward the unstable fixed point then relaxes toward its
destination. The peculiarity of that situation is that once the flow has
reached the mediator point, a small numerical error in instanton calculation,
or a small amount of noise in a stochastic system, can push the dynamics on
the other side of the separatrix : the dynamics then travels near
deterministically toward the final state $\mathcal{B}$. Let us term
$\mathcal{I}_{\mathcal{A}\rightarrow\mathcal{B}}$ the full action of the
instanton going from $\mathcal{A}$ to $\mathcal{B}$,
$\mathcal{I}_{\mathcal{A}\rightarrow m}$, the action of a trajectory following
the instanton from $\mathcal{A}$ to the mediator state,
$\mathcal{I}_{m\rightarrow s}$ the action of a trajectory following the
instanton from the mediator state to the saddle and
$\mathcal{I}_{m\rightsquigarrow\mathcal{B}}$ the action of a trajectory
starting on the mediator and being slightly perturbed to cross the separatrix
and then travel deterministically toward $\mathcal{B}$. The action of
deterministic paths is always zero: this means that in the limit of noise
variance going to zero, the action of any path starting on the $\mathcal{B}$
side of the separatrix to $\mathcal{B}$ that has any chance of being observed
is zero, because it will follow a deterministic path. This means that
$\mathcal{I}_{\mathcal{A}\rightarrow\mathcal{B}}=\mathcal{I}_{\mathcal{A}\rightarrow
m}+\mathcal{I}_{m\rightarrow s}\simeq\mathcal{I}_{\mathcal{A}\rightarrow m}$:
the action of the instanton is that of traveling toward the mediator point
then to the saddle and then relaxing. Moreover the part of the path along the
separatrix has a negligible action $\mathcal{I}_{m\rightarrow
s}\ll\mathcal{I}_{\mathcal{A}\rightarrow m}$ because it is a near
deterministic path in the stable manifold of the saddle. Similarly, the action
of a path traveling toward the mediator along the instanton then receiving a
small amount of noise to cross the separatrix there (as sketched in blue
sketched in figure 15 (b)) is
$\mathcal{I}_{\mathcal{A}\rightsquigarrow\mathcal{B}}=\mathcal{I}_{\mathcal{A}\rightarrow
m}+\mathcal{I}_{m\rightsquigarrow\mathcal{B}}\simeq\mathcal{I}_{\mathcal{A}\rightarrow
m}$. The action $\mathcal{I}_{\mathcal{A}\rightarrow\mathcal{B}}$ and
$\mathcal{I}_{\mathcal{A}\rightsquigarrow\mathcal{B}}$ are very similar and
the corresponding probabilities and mean first passage time respectively go to
zero and to infinity exponentially as very similar rates. At finite though
small noise variance, the probability of observing a trajectory going along
the instanton all the way becomes small compared to observing a trajectory
going toward the mediator then crossing toward $\mathcal{B}$ there, because
the instanton requires the trajectory not to be perturbed once the mediator
has been reached. Therefore, computations by means of numerical simulation of
the stochastic process (like DNS or AMS) would give the trajectory crossing
near the mediator. Moreover, trajectories would still concentrate up to the
mediator. However, the estimate of the probability and the mean first passage
time would go like $\exp(\pm\beta\mathcal{I}_{\mathcal{A}\rightarrow m})$ and
thus be exponential and very close to the one predicted by the Freidlin
Wentzel principle of large deviations. In our case, the exponential dependence
of $\alpha$ and $T$, the crossing of the separatrix away from the saddle and
the concentration of paths are consistent with this scenario. We note however
that the computed path do not concentrate on top of one another in planes
computed using kinetic energy. This could be an effect of the finite noise
variance in these quadratic spatially averaged quantities. Indeed, the
mechanical scenario is not changed from one value of $\beta$ to another.

As far as we can deduce from the data presented here, scenario iv is the most
similar to build up in plane Couette flow. If it is the case, this would mean
that we would observe an actual instanton all along the trajectory, not just
until the mediator or turning point only, for exceedingly small values of the
noise. Moreover, if we follow this line of reasoning, we cannot rule out the
possibility that there could be a mediator even closer to the laminar state,
comparable to a minimal seed, that would only be reached at minuscule values
of noise variance. It could be even beyond the reach of rare events
simulations methods. The case of build up in plane Couette flow thus helped us
identifying a different regime of convergence toward instantons, already
pointed out in two dimensional plane Poiseuille flow [Wan et al., 2015] and
can be linked to observations made in other systems where crossing away from
the saddle and very flat dependence of the action on the crossing point in
model of oceanic flows [Börner et al., 2023]. This behaviour could thus
manifest itself in more complex bistable geophysical flows.

(a)$\mathcal{A}$$\mathcal{B}$transition stateObserved pathsmallish
$\epsilon$Instanton$\epsilon\rightarrow 0$Expected pathsmallish
$\epsilon$Separatrix (b)$\mathcal{A}$$\mathcal{B}$mediatorObserved
pathsmallish $\epsilon$Instanton$\epsilon\rightarrow 0$Separatrix

Figure 15: (a) Sketch of the two metastable states $\mathcal{A}$ and
$\mathcal{B}$ in phase space, separated by a separatrix (green curve), on
which we have the transition state: the most accessible saddle point (red
arrows indicating stable and unstable directions). In the limit of vanishing
energy injection rate $\epsilon\rightarrow 0$, the reactive trajectory should
follow an instanton (in cyan): on this first sketch, we represent an instanton
that nears the separatrix only as it reaches the saddle along mostly unstable
directions. For small but finite energy injection rate $\epsilon$, we would
expect that trajectories concentrate around the instanton (in yellow).
Instead, we systematically observe trajectories that concentrate around a path
that crosses the separatrix away from the instanton and the most accessible
fixed point (in blue). For these two types of paths: the full line indicates
the average trajectory, while the dashed lines indicate where the zone that
contains the majority of paths. (b) Modification of sketch (a) in the case
where the instanton approaches the separatrix near a mediator state, then goes
along the separatrix approaches the nearest fixed point and finally travels
towards $\mathcal{B}$, with a scenario similar to the one described by [Wan et
al., 2015].

## Acknowledgment

The author thanks Institut PPrime, ENSMA and their computational facilities,
where this work was started, for its hospitality. The author thanks the help
of the computational resources of the PSMN platform of ENS de Lyon, as well as
the hospitality of the laboratoire de Physique de l’ENS de Lyon, where part of
the computation of this work have been performed. Additional computational
resources were granted by _Mésocentre de Calcul Scientifique Intensif_ of the
University of Lille and this work was granted access to the HPC resources of
IDRIS under the allocation 2022-A0122A01741 made by GENCI. The author also
thanks the support from CICADA _(centre de calcul interactifs)_ (now
_mésocentre Azzurra_) of University Nice Sophia-Antipolis where some early
computations have been performed. The author finally thanks F. Bouchet, R.
Börner, J.-C. Vassilicos and J.-P. Laval for inspiring discussions.

##  Appendix A Structure of the forcing noise

In section 2.1, we have introduced a forcing $\mathbf{f}$ in the Navier–Stokes
questions for the departure to laminar plane Couette flow (Eq. (2)). We had
stated that this forcing was prescribed using the spectrum of its correlation
function (Eq. (3)), governed by the shape factor $\Gamma_{l,n_{x},n_{z}}$ on
component $l$ and in plane wavenumbers $n_{x}$ and $n_{z}$. We had mentioned
the two families of forcing used to generate the build up trajectories,
illustrated with a visualisation of $\Gamma_{l,n_{x},n_{z}}$ (Fig. 2 (a,b)).
In this appendix, we will give a quantitative description of the procedure
followed to generate these two forcings:

  * •

Forcing on components. In that case, we prescribe the shape factor of the
Fourier transform of the correlation function: we rewrite
$\Gamma_{l,n_{x},n_{z}}$ using tensors
$\sigma_{l}\gamma_{n_{x}}\gamma_{n_{z}}$ on Fourier component $n_{x},n_{z}$.
The tensor $\sigma_{l}$ scales the correlation function on each component: it
can also be used to select a forcing on one component rather than the other,
using $\sigma_{l}=0$. Meanwhile, the tensors $\gamma$ prescribe the shape of
the spectrum of the correlation function. They all have in common the property
that $\gamma_{n_{x}}=0$ if $n_{x}>\left\lfloor\frac{N_{x}}{2}\right\rfloor$,
$\gamma_{n_{z}}=0$ if $n_{z}>\left\lfloor\frac{N_{z}}{2}\right\rfloor$,
$\gamma_{n_{x}}=0$ if $n_{x}<\left\lfloor\frac{L_{x}}{L_{c}}\right\rfloor$,
$\gamma_{n_{z}}=0$ if $n_{z}<\left\lfloor\frac{L_{x}}{L_{c}}\right\rfloor$.
This first restriction is used to avoid forcing aliased modes. We always used
$L_{c}=1.0$ for the largest scale of cut-off of the forcing.This second
restriction ensures that the low wavelength of transitional wall turbulence
are not directly forced. Using a cut-off wavenumber $N_{r}$, we set
$\gamma_{n_{x}}=1$ for $\left\lfloor\frac{L_{x}}{L_{c}}\right\rfloor\leq
n_{x}\leq N_{r}$ and $\gamma_{n_{z}}=1$ for
$\left\lfloor\frac{L_{z}}{L_{c}}\right\rfloor\leq n_{z}\leq N_{r}$: we have a
white spectrum at small wavenumbers. We then set
$\gamma_{n_{x}}=\frac{N_{r}}{n_{x}}$ for $N_{r}\leq
n_{x}\leq\left\lfloor\frac{N_{x}}{2}\right\rfloor$ and
$\gamma_{n_{z}}=\frac{N_{r}}{n_{z}}$ for $N_{r}\leq
n_{z}\leq\left\lfloor\frac{N_{z}}{2}\right\rfloor$: we have a red spectrum at
larger wavenumbers. The forcing on component $l$ at wavenumber $n_{x}$,
$n_{z}$ is then a Gaussian random number of variance $\frac{1}{\beta}$ times
$(\sigma_{l}\gamma_{n_{x}}\gamma_{n_{z}})^{2}$. This means that
$\Gamma_{l,n_{x},n_{z}}=(\sigma_{l}\gamma_{n_{x}}\gamma_{n_{z}})^{2}$. We
considered such a forcing on the three components (termed “iso”, with
$\sigma_{x}=\sigma_{y}=\sigma_{z}$) or only on the streamwise component
(termed “x” with $\sigma_{x}=1$, $\sigma_{y}=\sigma_{z}=0$). We only used it
in MFU type systems of size $L_{x}\times L_{z}=6\times 4$ for the standard
resolution. We have used several values of $N_{r}=4$, $6$ and $8$ (which are
specified when the results are presented.

  * •

Divergence free forcing obtained from a curl. For this matter, we use a
potential vector $A_{n_{x},n_{y}}$, such that forcing on component $x$ at
wavenumber $n_{x}$, $n_{z}$ is $-\frac{1}{\sqrt{\beta}}\frac{2\pi
n_{z}}{L_{z}}A_{n_{x},n_{z}}$, there is no forcing on component $y$ and the
forcing on component $z$ is $\frac{1}{\beta}\frac{2\pi
n_{x}}{L_{x}}A_{n_{x},n_{z}}$, with $k_{x}=\frac{2\pi n_{x}}{L_{x}}$ and
$k_{z}=\frac{2\pi n_{z}}{L_{z}}$. We then have
$A_{n_{x},n_{z}}=\gamma_{n_{x}}\gamma_{n_{z}}\xi$, with $\xi$ a Gaussian
random number of variance $1$. These factors are non zero in a set range of
wavenumber: we set that $\gamma_{n_{x}}=0$ if
$n_{x}>\left\lfloor\frac{N_{x}}{2}\right\rfloor$, $\gamma_{n_{z}}=0$ if
$n_{z}>\left\lfloor\frac{N_{z}}{2}\right\rfloor$, $\gamma_{n_{x}}=0$ if
$n_{x}<\left\lfloor\frac{L_{x}}{L_{c}}\right\rfloor$, $\gamma_{n_{z}}=0$ if
$n_{z}<\left\lfloor\frac{L_{x}}{L_{c}}\right\rfloor$. We still set
$A_{n_{x},n_{z}}=\gamma_{x}\gamma_{z}$. This time we have
$\gamma_{x}=\frac{1}{n_{x}}$ for
$\left\lfloor\frac{L_{x}}{L_{c}}\right\rfloor\leq n_{x}\leq N_{r}$ and
$\gamma_{z}=\frac{1}{n_{z}}$ for
$\left\lfloor\frac{L_{z}}{L_{c}}\right\rfloor\leq n_{z}\leq N_{r}$. We then
set $\gamma_{n_{x}}=\frac{N_{r}}{n_{x}^{2}}$ for $N_{r}\leq
n_{x}\leq\left\lfloor\frac{N_{x}}{2}\right\rfloor$ and
$\gamma_{n_{z}}=\frac{N_{r}}{n_{z}^{2}}$ for $N_{r}\leq
n_{z}\leq\left\lfloor\frac{N_{z}}{2}\right\rfloor$. The Fourier transform of
the correlation function
$\Gamma_{x,n_{x},n_{z}}=\frac{4\pi^{2}n_{z}^{2}}{L_{z}^{2}}A_{n_{x},n_{z}}^{2}$
is displayed in the $k_{x},k_{z}$ plane in figure 2 (a),
$\Gamma_{y,n_{x},n_{z}}=0$ and
$\Gamma_{z}=\frac{4\pi^{2}n_{x}^{2}}{L_{x}^{2}}A_{n_{x},n_{z}}^{2}$ is
displayed in the $k_{x},k_{z}$ in figure 2 (b).

In the MFU type domain of size $L_{x}\times L_{z}=6\times 4$, for the standard
resolution, we used the parameters $L_{c}=1.0$ and $N_{r}=4$. In that domain,
for the finer resolution, we used the parameters $L_{c}=1.0$ and $N_{r}=4$. In
the domain of intermediate size $L_{x}\times L_{z}=18\times 12$, we used the
parameters $L_{c}=1.0$ and $N_{r}=12$. In the largest domain, of size
$L_{x}\times L_{z}=36\times 24$, we used the parameters $L_{c}=1.0$ and
$N_{r}=24$.

##  Appendix B Parameter used in definition of reaction coordinate in each set
of simulations

In section 2.2.2, we presented the set up of the reaction coordinates (Eq.
(11)), using three free parameters $E_{\mathcal{A}}$ to define the laminar
state $\mathcal{A}$, $\sigma$ to define the hypersurface $\mathcal{C}$ that
surrounds it and $E_{\mathcal{B}}$ to define the turbulent state (Fig. 3 (a)).
Most AMS computations used a systematic definition of these three parameters
with $E_{\mathcal{B}}=0.06$, and the parameters controlling $E_{\mathcal{A}}$
and $\sigma$ reported in table 1

$L_{x}\times L_{z}$ | $N_{x}\times N_{y}\times N_{z}$ | $\Delta t$ | $\beta_{\rm min}$ | $\beta_{\rm max}$ | $L_{c}$ | $N_{r}$ | $d_{E}$ | $o_{E}$ | $d_{S}$ | $o_{S}$ | type
---|---|---|---|---|---|---|---|---|---|---|---
$6\times 4$ | $32\times 27\times 24$ | $0.05$ | $1.5\times 10^{5}$ | $6\times 10^{5}$ | 1.0 | 4 | -1.05 | 7.1 | -1.11 | 6.4 | $\text{div}(\mathbf{f})=0$
$6\times 4$ | $32\times 27\times 24$ | 0.05 | $1.0\times 10^{5}$ | $1.1\times 10^{5}$ | 1.0 | 4 | -1.0 | 4.52 | -1.0 | 1.44 | x
$6\times 4$ | $32\times 27\times 24$ | 0.05 | $1.0\times 10^{5}$ | $4.0\times 10^{5}$ | 1.0 | 4 | -1.02 | 6.33 | -1.03 | 4.46 | iso
$6\times 4$ | $32\times 27\times 24$ | 0.05 | $1.0\times 10^{5}$ | $5.0\times 10^{5}$ | 1.0 | 6 | -1.02 | 6.64 | -0.98 | 3.58 | iso
$6\times 4$ | $32\times 27\times 24$ | 0.05 | $1.0\times 10^{5}$ | $5.5\times 10^{5}$ | 1.0 | 8 | -1.05 | 7.48 | -1.12 | 6.30 | iso
$6\times 4$ | $64\times 27\times 48$ | 0.05 | $1.0\times 10^{5}$ | $4.0\times 10^{5}$ | 1.0 | 4 | -1.01 | 6.47 | -1.02 | 4.30 | iso
$6\times 4$ | $128\times 35\times 96$ | 0.025 | $1.0\times 10^{5}$ | $3.0\times 10^{5}$ | 1.0 | 4 | -1.02 | 6.58 | -1.04 | 4.63 | iso
Table 1: Table of parameters $d_{E}$, $o_{E}$, $d_{S}$, $o_{S}$ used in
systematic AMS simulations to define the reaction coordinate for the study of
build up at Reynolds number $R$ in a system of size $L_{x}\times L_{z}$ using
numerical resolution $N_{x}\times N_{y}\times N_{z}$ in space and time step
$\Delta t$ in space, and a forcing spectrum controlled by $\beta$, $L_{c}$,
$N_{r}$.

Some AMS computations did not use a systematic definition for
$E_{\mathcal{A}}$, $\sigma$ and $E_{\mathcal{B}}$, because the value of
$\beta$ was too low for the system to be in the regime where $E$ is linear in
$\epsilon$. For those cases, the control parameters used are reported in table
2.

$R$ | $L_{x}\times L_{z}$ | $N_{x}\times N_{y}\times N_{z}$ | $\Delta t$ | $\beta$ | $L_{c}$ | $N_{r}$ | $E_{\mathcal{A}}$ | $E_{\mathcal{B}}$ | $\sigma$
---|---|---|---|---|---|---|---|---|---
500 | $6\times 4$ | $64\times 47\times 48$ | $0.0125$ | $5.5\times 10^{5}$ | 1.0 | 4 | 0.0096 | 0.06 | 0.0021
500 | $18\times 12$ | $96\times 27\times 72$ | $0.05$ | 62500 | 1.0 | 12 | 0.0117 | 0.06 | 0.0034
500 | $18\times 12$ | $96\times 27\times 72$ | $0.05$ | 80000 | 1.0 | 12 | 0.0081 | 0.06 | 0.0023
500 | $36\times 24$ | $192\times 27\times 144$ | $0.05$ | 30000 | 1.0 | 24 | 0.0123 | 0.0477 | 0.0028
Table 2: Table of parameters $E_{\mathcal{A}}$, $E_{\mathcal{B}}$ and $\sigma$
used in non systematic AMS simulations to define the reaction coordinate for
the study of build up at Reynolds number $R$ in a system of size $L_{x}\times
L_{z}$ using numerical resolution $N_{x}\times N_{y}\times N_{z}$ in space and
time step $\Delta t$ in space, and a spectrum of the divergence free forcing
controlled by $\beta$, $L_{c}$ and $N_{r}$.

##  Appendix C Convergence of AMS computations

In this appendix, in complement to the precision tests of section 4.1 (Fig. 13
(d)), we will check that the number of clones used in AMS computation was
sufficient. For this matter, we present convergence results with the number of
clones for the two types of forcings in domains of size $L_{x}\times
L_{z}=6\times 4$ at Reynolds number $R=500$ using standard resolution
$N_{x}=32$, $N_{y}=27$, $N_{z}=24$ and $\Delta t=0.05$. Isotropic forcing was
added using $\beta=4\cdot 10^{5}$ and $\beta=5\cdot 10^{5}$ with $N_{r}=6$,
and $L_{c}=1.0$. Divergence free forcing was added using $\beta=2.5\cdot
10^{5}$ and $3\cdot 10^{5}$ using $L_{c}=1$ and $N_{r}=4$. In all four cases,
the crossing probabilities are not that small, so that the reactive
trajectories and their properties can be computed by DNS with a high enough
degree of precision.

We compare the probability $\alpha$ in logarithmic scale computed by means of
AMS and DNS in figure 16 (a). For all four examples considered, we observe the
overlap of the DNS and AMS $66\%$ intervals of confidence, obtained using
$\pm$ the sample standard deviation, as soon as $N\geq 20$. This indicates
that no error are performed in these AMS computation if the number of clones
is sufficient. For $N=5$ and $N=10$, we observe underestimates of $\alpha$
which are expected. Due to the increased rarity of the event for $\beta=3\cdot
10^{5}$ with divergent free forcing, the expensive computations means that the
dataset is smaller, which explains the wider confidence intervals for DNS
estimates.

We then present the normalised standard deviation of the estimate of $\alpha$
in the case where $N_{c}=1$ and in the case where $N_{c}>1$

$\sigma_{norm}=\frac{\sqrt{\langle\alpha^{2}\rangle_{o}-\langle\alpha\rangle_{o}^{2}}\sqrt{N}}{\alpha\sqrt{|\log(\alpha)|}}\,,\,\sigma_{norm,N_{c}}=\frac{\sqrt{\langle\alpha^{2}\rangle_{o}-\langle\alpha\rangle_{o}^{2}}\sqrt{N}}{\alpha\sqrt{\left(\langle\kappa\rangle_{o}\frac{N_{c}}{N-N_{c}}+\frac{1-\langle
r\rangle_{o}}{\langle r\rangle_{o}}\right)}}\,.$ (22)

where $\langle\kappa\rangle_{o}$ is the average number of iterations over AMS
runs and $\langle r\rangle_{o}$ is the average proportion of clones reaching
$\mathcal{B}$ over AMS runs. It has been demonstrated that this quantity is
larger than or equal to one, and it is one when the committor is used as
reaction coordinate [Cérou et al., 2019]. In parallel, it has also been shown
that the closer a reaction coordinate is to the committor, the most precise
the AMS estimates are when a finite number of runs are used. As a consequence,
this quantity is used as an estimate of the quality of the computation because
the better the reaction coordinate, the smaller is $\sigma$. A very large
$\sigma$ would be that the estimates of $\alpha$ and $T$ are incorrect, or
even that the paths are incorrectly selected [Rolland and Simonnet, 2015,
Lucente et al., 2022]. In that case what is typically observed in the
selection of shorter though less probable paths. In the two test cases
considered here (Fig. 16 (c)), we can see that $\sigma$ is slightly larger
than one. This ensures correct estimates, but also tells us that there is room
for improvement of the reaction coordinate.

Figure 16: In a domain of size $L_{x}\times L_{z}=6\times 4$ at Reynolds
number $R=500$ for four different forcings (see § C for details). (a) Crossing
$\alpha$ probability as a function of the number of clones, computed by AMS or
DNS. The error bars correspond to the $66\%$ confidence interval of AMS
computations, the dotted line corresponds to the 66% interval of confidence of
DNS computations. (b) normalised standard deviation (Eq. (22)) of the crossing
probability $\alpha$ as a function of the number of clones, compared to $1$.
(c) Average duration $\tau$ of reactive trajectories as a function of the
number of clones, computed by means of AMS and DNS for the same cases and the
same line codes as (a).

We finally test the computation of the average duration of reactive
trajectories. The result of the AMS computations of $\tau$ as a function of
$N$ in our four cases is presented in figure 16 (c). We add the result of DNS
computation and the 66% interval of confidence to this figure. We note the
overlap of the intervals of confidence in all four cases as soon as $N\geq
10$, indicating that no discernable bias can be observed in the estimates of
$\tau$ by means of AMS. If those estimates are averaged over enough
repetitions, they are precise enough in those cases. In conclusion to this
appendix, we note that we do not discern any irreducible error in the
computations performed by means of AMS, even if the number of clones used is
relatively modest (at least 20). In those case, a larger number of repetitions
of the computations is required to compute said estimates. This confirm the
observation performed in section 4.1 for several values of $\beta$ (and the
corresponding $\alpha$) with only one clone number per case.

## References

  * [Baars et al., 2021] Baars, S., Castellana, D., Wubs, F. W., and Dijkstra, H. A. (2021).  Application of adaptive multilevel splitting to high-dimensional dynamical systems.  Journal of Computational Physics, 424:109876.
  * [Berhanu et al., 2007] Berhanu, M., Monchaux, R., Fauve, S., Mordant, N., Pétrélis, F. c., Chiffaudel, A., Daviaud, F. c., Dubrulle, B., Marié, L., Ravelet, F., Bourgoin, M., Odier, P., Pinton, J.-F. c., and Volk, R. (2007).  Magnetic field reversals in an experimental turbulent dynamo.  Eur. Phys. Lett., 77(5):59001.
  * [Börner et al., 2023] Börner, R., Deeley, R., Römer, R., Grafke, T., Lucarini, V., and Feudel, U. (2023).  Saddle avoidance of noise-induced transitions in multiscale systems.  arXiv preprint arXiv:2311.10231.
  * [Bouchet and Reygner, 2016] Bouchet, F. and Reygner, J. (2016).  Generalisation of the eyring–kramers transition rate formula to irreversible diffusion processes.  In Annales Henri Poincaré, volume 17, pages 3499–3532. Springer.
  * [Bouchet et al., 2019] Bouchet, F., Rolland, J., and Simonnet, E. (2019).  Rare event algorithm links transitions in turbulent flows with activated nucleations.  Physical review letters, 122(7):074502.
  * [Bouchet and Touchette, 2012] Bouchet, F. and Touchette, H. (2012).  Non-classical large deviations for a noisy system with non-isolated attractors.  Journal of Statistical Mechanics: Theory and Experiment, 2012(05):P05028.
  * [Bréhier et al., 2016] Bréhier, C.-E., Gazeau, M., Goudenège, L., Lelièvre, T., and Rousset, M. (2016).  Unbiasedness of some generalized adaptive multilevel splitting algorithms.  The Annals of Applied Probability, 26(6):3559–3601.
  * [Brzeźniak et al., 2015] Brzeźniak, Z., Cerrai, S., and Freidlin, M. (2015).  Quasipotential and exit time for 2d stochastic navier-stokes equations driven by space time white noise.  Probability Theory and Related Fields, 162(3-4):739–793.
  * [Cérou et al., 2019] Cérou, F., Delyon, B., Guyader, A., and Rousset, M. (2019).  On the asymptotic normality of adaptive multilevel splitting.  SIAM/ASA Journal on Uncertainty Quantification, 7(1):1–30.
  * [Cérou and Guyader, 2007] Cérou, F. and Guyader, A. (2007).  Adaptive multilevel splitting for rare event analysis.  Stochastic Analysis and Applications, 25(2):417–443.
  * [Cérou et al., 2013] Cérou, F., Guyader, A., Lelièvre, T., and Malrieu, F. (2013).  On the length of one-dimensional reactive paths.  ALEA, 10(1):359–389.
  * [Cérou et al., 2011] Cérou, F., Guyader, A., Lelièvre, T., and Pommier, D. (2011).  A multiple replica approach to simulate reactive trajectories.  The Journal of chemical physics, 134(5):054108.
  * [Chantry and Schneider, 2014] Chantry, M. and Schneider, T. M. (2014).  Studying edge geometry in transiently turbulent shear flows.  Journal of fluid mechanics, 747:506–517.
  * [Cherubini et al., 2011] Cherubini, S., De Palma, P., Robinet, J.-C., and Bottaro, A. (2011).  The minimal seed of turbulent transition in the boundary layer.  Journal of Fluid Mechanics, 689:221.
  * [Ducimetière et al., 2022] Ducimetière, Y.-M., Boujo, E., and Gallaire, F. (2022).  Weakly nonlinear evolution of stochastically driven non-normal systems.  Journal of Fluid Mechanics, 951:R3.
  * [Farrell and Ioannou, 1993a] Farrell, B. F. and Ioannou, P. J. (1993a).  Optimal excitation of three-dimensional perturbations in viscous constant shear flow.  Physics of Fluids A: Fluid Dynamics, 5(6):1390–1400.
  * [Farrell and Ioannou, 1993b] Farrell, B. F. and Ioannou, P. J. (1993b).  Stochastic forcing of the linearized navier–stokes equations.  Physics of Fluids A: Fluid Dynamics, 5(11):2600–2609.
  * [Freidlin and Wentzell, 1998] Freidlin, M. I. and Wentzell, A. D. (1998).  Random perturbations.  In Random perturbations of dynamical systems, pages 15–43. Springer.
  * [Gibson et al., 2008] Gibson, J. F., Halcrow, J., and Cvitanović, P. (2008).  Visualizing the geometry of state space in plane couette flow.  J. Fluid Mech., 611:107–130.
  * [Gomé et al., 2022] Gomé, S., Tuckerman, L. S., and Barkley, D. (2022).  Extreme events in transitional turbulence.  Philosophical Transactions of the Royal Society A, 380(2226):20210036.
  * [Grafke and Vanden-Eijnden, 2019] Grafke, T. and Vanden-Eijnden, E. (2019).  Numerical computation of rare events via large deviation theory.  Chaos: An Interdisciplinary Journal of Nonlinear Science, 29(6):063118.
  * [Grandemange et al., 2013] Grandemange, M., Gohlke, M., and Cadot, O. (2013).  Turbulent wake past a three-dimensional blunt body. part 1. global modes and bi-stability.  Journal of Fluid Mechanics, 722:51–84.
  * [Hamilton et al., 1995] Hamilton, J. M., Kim, J., and Waleffe, F. (1995).  Regeneration mechanisms of near-wall turbulence structures.  Journal of Fluid Mechanics, 287(1):317–348.
  * [Hänggi et al., 1990] Hänggi, P., Talkner, P., and Borkovec, M. (1990).  Reaction-rate theory: fifty years after kramers.  Reviews of modern physics, 62(2):251.
  * [Herbert et al., 2020] Herbert, C., Caballero, R., and Bouchet, F. (2020).  Atmospheric bistability and abrupt transitions to superrotation: wave–jet resonance and hadley cell feedbacks.  Journal of the Atmospheric Sciences, 77(1):31–49.
  * [Jiménez and Moin, 1991] Jiménez, J. and Moin, P. (1991).  The minimal flow unit in near-wall turbulence.  Journal of Fluid Mechanics, 225:213–240.
  * [Kawahara and Kida, 2001] Kawahara, G. and Kida, S. (2001).  Periodic motion embedded in plane couette turbulence: regeneration cycle and burst.  Journal of Fluid Mechanics, 449:291–300.
  * [Kim and Durbin, 1988] Kim, H.-J. and Durbin, P. A. (1988).  Investigation of the flow between a pair of circular cylinders in the flopping regime.  Journal of Fluid Mechanics, 196:431–448.
  * [Kreilos and Eckhardt, 2012] Kreilos, T. and Eckhardt, B. (2012).  Periodic orbits near onset of chaos in plane couette flow.  Chaos: An Interdisciplinary Journal of Nonlinear Science, 22(4).
  * [Liu et al., 2021] Liu, T., Semin, B., Klotz, L., Godoy-Diana, R., Wesfreid, J. E., and Mullin, T. (2021).  Decay of streaks and rolls in plane couette–poiseuille flow.  Journal of Fluid Mechanics, 915.
  * [Lopes and Lelièvre, 2019] Lopes, L. J. and Lelièvre, T. (2019).  Analysis of the adaptive multilevel splitting method on the isomerization of alanine dipeptide.  Journal of computational chemistry, 40(11):1198–1208.
  * [Lucarini and Bódai, 2017] Lucarini, V. and Bódai, T. (2017).  Edge states in the climate system: exploring global instabilities and critical transitions.  Nonlinearity, 30(7):R32.
  * [Lucarini and Bódai, 2019] Lucarini, V. and Bódai, T. (2019).  Transitions across melancholia states in a climate model: Reconciling the deterministic and stochastic points of view.  Physical review letters, 122(15):158701.
  * [Lucente et al., 2022] Lucente, D., Rolland, J., Herbert, C., and Bouchet, F. (2022).  Coupling rare event algorithms with data-based learned committor functions using the analogue markov chain.  Journal of Statistical Mechanics: Theory and Experiment, 2022(8):083201.
  * [Metzner et al., 2006] Metzner, P., Schütte, C., and Vanden-Eijnden, E. (2006).  Illustration of transition path theory on a collection of simple examples.  The Journal of chemical physics, 125(8):084110.
  * [Monokrousos et al., 2011] Monokrousos, A., Bottaro, A., Brandt, L., Di Vita, A., and Henningson, D. S. (2011).  Nonequilibrium thermodynamics and the optimal path to turbulence in shear flows.  Physical review letters, 106(13):134502.
  * [Nusse and Yorke, 1989] Nusse, H. E. and Yorke, J. A. (1989).  A procedure for finding numerical trajectories on chaotic saddles.  Physica D: Nonlinear Phenomena, 36(1-2):137–156.
  * [Onsager, 1938] Onsager, L. (1938).  Initial recombination of ions.  Physical Review, 54(8):554.
  * [Onsager and Machlup, 1953] Onsager, L. and Machlup, S. (1953).  Fluctuations and irreversible processes.  Physical Review, 91(6):1505.
  * [Philip and Manneville, 2011] Philip, J. and Manneville, P. (2011).  From temporal to spatiotemporal dynamics in transitional plane couette flow.  Physical Review E, 83(3):036308.
  * [Podvin and Sergent, 2017] Podvin, B. and Sergent, A. (2017).  Precursor for wind reversal in a square rayleigh-bénard cell.  Physical Review E, 95(1):013112.
  * [Rabin et al., 2012] Rabin, S. M. E., Caulfield, C.-C. P., and Kerswell, R. R. (2012).  Triggering turbulence efficiently in plane couette flow.  Journal of Fluid Mechanics, 712:244.
  * [Rigas et al., 2021] Rigas, G., Sipp, D., and Colonius, T. (2021).  Nonlinear input/output analysis: application to boundary layer transition.  Journal of Fluid Mechanics, 911.
  * [Rolland, 2015] Rolland, J. (2015).  Mechanical and statistical study of the laminar hole formation in transitional plane couette flow.  The European Physical Journal B, 88(3):66.
  * [Rolland, 2018] Rolland, J. (2018).  Extremely rare collapse and build-up of turbulence in stochastic models of transitional wall flows.  Physical Review E, 97(2):023109.
  * [Rolland, 2022] Rolland, J. (2022).  Collapse of transitional wall turbulence captured using a rare events algorithm.  Journal of Fluid Mechanics, 931.
  * [Rolland et al., 2016] Rolland, J., Bouchet, F., and Simonnet, E. (2016).  Computing transition rates for the 1-d stochastic ginzburg–landau–allen–cahn equation for finite-amplitude noise with a rare event algorithm.  Journal of Statistical Physics, 162(2):277–311.
  * [Rolland and Simonnet, 2015] Rolland, J. and Simonnet, E. (2015).  Statistical behaviour of adaptive multilevel splitting algorithms in simple models.  Journal of Computational Physics, 283:541–558.
  * [Romanov, 1973] Romanov, V. A. (1973).  Stability of plane-parallel couette flow.  Functional analysis and its applications, 7(2):137–146.
  * [Schmid and Henningson, 1994] Schmid, P. J. and Henningson, D. S. (1994).  Optimal energy density growth in hagen–poiseuille flow.  Journal of Fluid Mechanics, 277:197–225.
  * [Schmiegel and Eckhardt, 1997] Schmiegel, A. and Eckhardt, B. (1997).  Fractal stability border in plane couette flow.  Physical review letters, 79(26):5250.
  * [Schneider et al., 2007] Schneider, T. M., Eckhardt, B., and Yorke, J. A. (2007).  Turbulence transition and the edge of chaos in pipe flow.  Physical review letters, 99(3):034502.
  * [Schneider et al., 2008] Schneider, T. M., Gibson, J. F., Lagha, M., De Lillo, F., and Eckhardt, B. (2008).  Laminar-turbulent boundary in plane couette flow.  Physical Review E, 78(3):037301.
  * [Schneider et al., 2010] Schneider, T. M., Marinc, D., and Eckhardt, B. (2010).  Localized edge states nucleate turbulence in extended plane couette cells.  Journal of Fluid Mechanics, 646:441–451.
  * [Simonnet, 2016] Simonnet, E. (2016).  Combinatorial analysis of the adaptive last particle method.  Statistics and Computing, 26(1):211–230.
  * [Simonnet et al., 2021] Simonnet, E., Rolland, J., and Bouchet, F. (2021).  Multistability and rare spontaneous transitions between climate and jet configurations in a barotropic model of the jovian mid-latitude troposphere.  Journal of the Atmospheric Sciences, 78:1889–1911.
  * [Spangler and Wells Jr, 1968] Spangler, J. G. and Wells Jr, C. S. (1968).  Effects of freestream disturbances on boundary-layer transition.  AIAA Journal, 6(3):543–545.
  * [Toh and Itano, 2003] Toh, S. and Itano, T. (2003).  A periodic-like solution in channel flow.  Journal of Fluid Mechanics, 481:67–76.
  * [Touchette, 2009] Touchette, H. (2009).  The large deviation approach to statistical mechanics.  Physics Reports, 478(1-3):1–69.
  * [Trefethen et al., 1993] Trefethen, L. N., Trefethen, A. E., Reddy, S. C., and Driscoll, T. A. (1993).  Hydrodynamic stability without eigenvalues.  Science, 261(5121):578–584.
  * [Van Erp et al., 2003] Van Erp, T. S., Moroni, D., and Bolhuis, P. G. (2003).  A novel path sampling method for the calculation of rate constants.  The Journal of chemical physics, 118(17):7762–7774.
  * [Waleffe, 1997] Waleffe, F. (1997).  On a self-sustaining process in shear flows.  Physics of Fluids, 9(4):883–900.
  * [Wan, 2013] Wan, X. (2013).  A minimum action method for small random perturbations of two-dimensional parallel shear flows.  Journal of Computational Physics, 235:497–514.
  * [Wan and Yu, 2017] Wan, X. and Yu, H. (2017).  A dynamic-solver-consistent minimum action method: With an application to 2d navier-stokes equations.  Journal of Computational Physics, 331:209–226.
  * [Wan et al., 2015] Wan, X., Yu, H., and Weinan, E. (2015).  Model the nonlinear instability of wall-bounded shear flows as a rare event: a study on two-dimensional poiseuille flow.  Nonlinearity, 28(5):1409.
  * [Willis and Kerswell, 2009] Willis, A. P. and Kerswell, R. R. (2009).  Turbulent dynamics of pipe flow captured in a reduced model: puff relaminarization and localized ’edge’ states.  Journal of Fluid Mechanics, 619:213–233.