Nested cycles with no geometric crossings

Abstract

In 1975, Erdős asked the following question: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound $f(n)=O(n)$ using sublinear expanders.

1. Introduction

Extremal problems involving cycles have been extensively studied. In particular, what kinds of cycles can we find in graphs with large (but constant) average/minimum degree? A classical result of this sort is the Corradi-Hajnal theorem 3 from 1963, stating that any graph $G$ with minimum degree $\delta (G)\ge 2k$ and $|G|\ge 3k$ contains $k$ pairwise vertex-disjoint cycles. This was later extended to cycles of the same length. Egawa 4, improving an earlier result of Häggkvist 6, showed that large graphs with $2k$ minimum degrees contain $k$ pairwise vertex-disjoint cycles with the same length. By viewing cycles as minimal graphs of connectivity two or minimum degree two, these results were also generalized in the direction of finding disjoint subgraphs of certain minimum degree or connectivity in 7111415. See also a result of Verstraëte 16 for vertex-disjoint cycles whose lengths form an arithmetic progression in graphs with large average degree.

In this note, we are interested in finding cycles with geometric constraints. Cycles $C_1$, …, $C_k$ in a graph $G$ are said to be nested cycles if the vertex set of $C_{i+1}$ is a subset of the vertex set of $C_i$ for each $i\in [k-1]$. If, in addition, their edge sets are pairwise disjoint, we say they are edge-disjoint nested cycles (see Figure 1a). In 1975, Erdős 5 conjectured that there is a constant $c$ such that graphs with $n$ vertices and at least $cn$ edges must contain two edge-disjoint nested cycles. Bollobás 1 proved this conjecture and asked for an extension to $k$ edge-disjoint nested cycles. This was confirmed later in 1996 by Chen, Erdős and Staton 2, who showed that $O_k(n)$ edge forces $k$ edge-disjoint nested cycles.

A stronger conjecture of Erdős that also appeared in 5 is that there exists a constant $C$ such that graphs with $n$ vertices and at least $Cn$ edges must contain two edge-disjoint nested cycles such that, geometrically, the edges of the inner cycle do not cross each other; in other words, if $C_1=v_1\dots v_{\ell _1}$, then $C_2$ has no two edges $v_iv_{i'}$ and $v_jv_{j'}$ with $i<j<i'<j'$. In this case, $C_1$ and $C_2$ are said to be two nested cycles without crossings (see Figure 1b). The proof of the above nested cycles result of Chen, Erdős and Staton proceeds by finding a cycle $C$ in a graph $G$ with average degree $d$ such that the average degree of the subgraph $H\subseteq G$ induced on $V(C)$ grows with $d$. One can then iterate this to get nested cycles. This argument, however, does not say anything about the shape of the cycles that can be found in $H$.

Here we prove this conjecture allowing us to find nested cycles without crossings.

Theorem 1.1.

There exists a constant $C>0$ such that every graph $G$ with average degree at least $C$ has two nested cycles without crossings.

Our proof utilises a notion of sublinear expanders (see Section 2.2), which plays an important role in some recent resolutions of long-standing conjectures; see e.g. 891213. Our embedding strategy goes in reverse order. That is, we will find the inner cycle first and then embed the outer cycle in such a way that there is no geometric crossing. This is made possible via a structure we call kraken (see Definition 3.1). The bulk of the work is to construct a kraken in a graph with large but constant average degree.

It would be interesting to see if large constant average degree can also force $O(1)$ many nested cycles without crossings. It seems that new ideas are needed for such an extension (if it is true!).

Question 1.2.

Given $k\in \mathbb{N}$, does there exist $f(k)$ such that every graph with average degree $f(k)$ contains $k$ nested cycles without geometric crossings?

Organisation

After laying out the tools needed in Section 2, Theorem 1.1 will be proved in Section 3, assuming that we have a kraken on our side on the battlefield. Then in Section 4, we show how to summon such a creature.

2. Preliminaries

For $n\in \mathbb{N}$, let $[n]\coloneq \{1$, …, $n\}$. If we claim that a result holds for $0<a\ll b,c\ll d<1$, it means that there exist positive functions $f,g$ such that the result holds as long as $a<f(b,c)$ and $b<g(d)$ and $c<g(d)$. We will not compute these functions explicitly. In many cases, we treat large numbers as if they are integers, by omitting floors and ceilings if it does not affect the argument. We write $\log$ for the base-$e$ logarithm.

2.1. Graph notation

Given a graph $G$, denote its average degree $2e(G)/|G|$ by $d(G)$. Let $F\subseteq G$ and $H$ be graphs, and $U\subseteq V(G)$. We write $G[U]\subseteq G$ for the induced subgraph of $G$ on vertex set $U$. Denote by $G\cup H$ the graph with vertex set $V(G)\cup V(H)$ and edge set $E(G)\cup E(H)$, and write $G-U$ for the induced subgraph $G[V(G)\setminus U]$, and $G\setminus F$ for the spanning subgraph of $G$ obtained from removing the edge set of $F$. For a set of vertices $X\subseteq V(G)$ and $i\in \mathbb{N}$, the distance in $G$ between $X$ and a vertex $u$ is the length of a shortest path from $u$ to $X$; denote

$$\begin{equation*} N_G^i(X)\coloneq \{u\in V(G):\text{ the distance in $G$ between $X$ and $u$ is exactly $i$}\}, \end{equation*}$$

and write $N_G^0(X)=X$, $N_G(X)\coloneq N_G^1(X)$, and for $i\in \mathbb{N}\cup \{0\}$, let $B_G^i(X)=\bigcup _{j=0}^iN_G^j(X)$ be the ball of radius $i$ around $X$. When the underlying graph $G$ is clear from the context, we omit the subscript $G$ and simply write $N(X), N^i(X), B^i(X)$. For a path $P$, we write $\ell (P)$ for its length, which is the number of edges in the path.

2.2. Sublinear expander

Our proof makes use of the sublinear expander introduced by Komlós and Szemerédi 10. Roughly speaking, a sublinear expander is a graph in which all sets of reasonable size expand by a sublinear factor. This weak expansion and its consequence that large sets are linked by a short path drive our whole embedding argument.

We shall use the following extension by Haslegrave, Kim and Liu 8.

Definition 2.1.

Let $\varepsilon _{1}>0$ and $k\in \mathbb{N}$. A graph $G$ is an $(\varepsilon _{1},k)$-expander if for all $X\subset V(G)$ with $k/2\leq |X|\leq |G|/2$, and any subgraph $F\subseteq G$ with $e(F)\leq d(G)\cdot \varepsilon (|X|)|X|$, we have

$$\begin{equation*} |N_{G\setminus F}(X)| \geq \varepsilon (|X|)\cdot |X|, \end{equation*}$$

where

$$\begin{equation*} \varepsilon (x)=\varepsilon \left(x, \varepsilon _{1}, k\right)=\left\{\begin{array}{cc} 0 & \text{ if } x<k / 5, \\\varepsilon _{1} / \log ^{2}(15 x / k) & \text{ if } x \geq k / 5. \end{array}\right. \end{equation*}$$

When the parameters $\varepsilon _1$ and $k$ are clear from the context, we will omit them and write simply $\varepsilon (x)$. Note that when $x\geq k/2$, $\varepsilon (x)$ is decreasing, while $\varepsilon (x)\cdot x$ is increasing.

Though the expansion rate of the expander above is only sublinear, the advantage of this notion is that every graph contains one such sublinear expander subgraph with almost the same average degree.

Theorem 2.2 (8, Lemma 3.2).

There exists some $\varepsilon _1>0$ such that the following holds for every $k>0$. Every graph $G$ has an $(\varepsilon _1,k)$-expander subgraph $H$ with $d(H)\geq d(G)/2$ and $\delta (H)\geq d(H)/2$.

Thanks to this theorem, by passing to an expander subgraph, it suffices to prove Theorem 1.1 for expanders. A key property 10, Corollary 2.3 of expanders that we will use is that there exists a short path between any two sufficiently large sets. This is formalised in the following statement.

Lemma 2.3.

Let $\varepsilon _{1},k>0$. If $G$ is an $n$-vertex $(\varepsilon _{1},k)$-expander, then any two vertex sets $X_1,X_2$, each of size at least $x\geq k$, are at distance of at most $m=\frac{1}{\varepsilon _{1}}\log ^3(15n/k)$ apart. This remains true even after deleting $\varepsilon (x,\varepsilon _1,k)\cdot x/4$ vertices from $G$.

2.3. Robust expansions

For our proof, we need to be able to expand a set $A$ past another set $U$ as long as $U$ does not interfere with each sphere around $A$ too much. The following notion makes this precise.

Definition 2.4.

For $\lambda >0$ and $k\in \mathbb{N}$, we say that a vertex set $U$ in a graph $G$ is $(\lambda ,k)$-thin around $A$ if $U\cap A=\varnothing$ and, for each $i\in \mathbb{N}$,

$$\begin{equation*} |N_G(B_{G-U}^{i-1}(A))\cap U|\leq \lambda i^k. \end{equation*}$$

As shown in the Lemma 2.6 below, the rate of expansion for every small set is almost exponential in an expander even after deleting a thin set around it. Its proof follows essentially 8, Proposition 3.5.

Proposition 2.5.

Let $0<1/d\ll \varepsilon _1\ll 1/\lambda , 1/k$ and $1\leq r\leq \log n$. Suppose $G$ is an $n$-vertex $(\varepsilon _1,\varepsilon _1d)$-expander with $\delta (G)\ge d$, and $X,Y$ are sets of vertices with $|X|\ge 1$ and $|Y|\leq \frac{1}{4}\varepsilon (|X|)\cdot |X|$. Let $W$ be a $(\lambda ,k)$-thin set around $X$ in $G-Y$. Then, for each $1\leq r\leq \log n$, we have

$$\begin{equation*} |B^r_{G-W-Y}(X)|\geq \exp (r^{1/4}). \end{equation*}$$

Proof.

For each $i\ge 0$, let $Z_i= B^{i}_{G-W-Y}(X)$. As $W$ is $(\lambda ,k)$-thin around $X$ in $G-Y$, we obtain that for each $i\ge 0$,

$$\begin{align} \lvert Z_{i+1}\rvert &= \lvert Z_i\rvert + \lvert N_G(Z_i)\setminus (Y\cup W)\rvert \ge \lvert Z_i\rvert + \varepsilon (\lvert Z_i\rvert )\lvert Z_i\rvert - \lvert Y\rvert -\lvert N_{G-Y}(Z_i)\cap W\rvert \\ &\geq \lvert Z_i\rvert + \frac{3}{4}\varepsilon (\lvert Z_i\rvert )\lvert Z_i\rvert - \lambda i^k. {\tag{1}} \end{align}$$

Indeed, this follows from the expansion of $G$ if $|Z_i|\ge \varepsilon _1d$; and if $|Z_i|\le \varepsilon _1d$, it follows from $\delta (G)\ge d$. Thus we have $\lvert Z_0\rvert =|X|$ and $|Z_1|\ge d/2\ge \varepsilon _1d$.

Let $x=|Z_1|\ge \varepsilon _1d$ and define $f(z)=\exp (z^{1/4})$ and $g(z)\coloneq x + \frac{1}{2}\varepsilon (x)x\cdot (z-1)$. We first use induction on $i$ to show that for each $1\le i\le \log ^4x$, $\lvert Z_i\rvert \ge g(i)$. The base case $i=1$ is trivial.

Now for $1\leq i\leq \log ^4x$ we use 1 together with the induction hypothesis and the facts that $\varepsilon (z)z$ is increasing when $z\ge x$ and $\frac{1}{4}\varepsilon (x)x > \lambda i^k$ to obtain

$$\begin{equation*} \lvert Z_{i+1}\rvert \geq \lvert Z_i\rvert + \frac{1}{2}\varepsilon (x)x = \lvert Z_i\rvert + g(i+1)-g(i)\ge g(i+1). \end{equation*}$$

We may then assume $i>\log ^4x$, as $f(i)\le g(i)\le \lvert Z_i\rvert$ when $i\le \log ^4x$. Now, as $i>\log ^4x$ is sufficiently large (due to $x\ge \varepsilon _1d$), we get $\lambda i^k< \frac{ f(i)}{i^{3/4}}$. Finally, noting that $f(i+1)-f(i)\le \frac{f(i)}{i^{3/4}}$ and $\varepsilon (\lvert Z_i\rvert )\lvert Z_i\rvert \ge \varepsilon (f(i))f(i)\ge \frac{\varepsilon _1f(i)}{i^{1/2}}$, we have

$$\begin{align*} \lvert Z_{i+1}\rvert &\ge \lvert Z_i\rvert +\frac{3}{4}\varepsilon (\lvert Z_i\rvert )\lvert Z_i\rvert - \lambda i^k \geq \lvert Z_i\rvert +\frac{3\varepsilon _1f(i)}{4i^{1/2}}- \frac{ f(i)}{i^{3/4}}\\ &\geq \lvert Z_i\rvert +\frac{ f(i)}{i^{3/4}} \geq \lvert Z_i\rvert + f(i+1)-f(i)\ge f(i+1), \end{align*}$$

as desired.

■

We will use Lemma 2.6 13, Lemma 3.12 to find a linear size vertex set with polylogarithmic diameter in $G$ while avoiding an arbitrary set of size $o(n/\log ^2n)$.

Lemma 2.6.

Let $0<1/d\ll \varepsilon _1<1$ and let $G$ be an $n$-vertex $(\varepsilon _1,\varepsilon _1d)$-robust-expander with $\delta (G)\geq d$. For any $W\subseteq V(G)$ with $|W|\leq \varepsilon _1n/100\log ^2n$, there is a set $B\subseteq G-W$ with size at least $n/25$ and diameter at most $100\varepsilon _1^{-1}\log ^3n$.

3. Proof of Theorem 1.1

A key structure we use in our proof is a kraken defined below. The idea of the proof is depicted in Figure 2. We embed the desired nested cycles by taking the cycle in a kraken to be the inner cycle and linking the arms of the kraken iteratively to get the outer cycle so that the cyclic orderings of the vertices of both cycles respect each other.

Definition 3.1.

For $k,m,s\in \mathbb{N}$, a graph $K$ is a $(k,m,s)$-kraken if it contains a cycle $C$ with vertices $v_1$, …, $v_k$ (in the order of the cycle $C$), vertices $u_{i,1}$, $u_{i,2}\in V(G)\setminus V(C), i\in [k]$, and subgraphs $A=\bigcup _{i=1}^{k}\big (A_{i,1}\cup A_{i,2}\big )$ and $R=\bigcup _{i=1}^{k}\big (R_{i,1}\cup R_{i,2}\big )$, where

•

$\{A_{i,j}:i\in [k],\, j\in [2]\}$ is a collection of pairwise disjoint sets of size $s$ lying in $V(G)\setminus V(C)$ with $u_{i,j}\in A_{i,j}$, each with diameter at most $m$.

•

$\{R_{i,j}:i\in [k],\, j\in [2]\}$ is a collection of pairwise internally vertex disjoint paths such that $R_{i,j}$ is a path between $v_i$ and $u_{i,j}$ of length at most $10m$ with internal vertices disjoint from $V(C)\cup (V(A)\setminus V(A_{i,j}))$.

We usually write a kraken as a tuple $(C, A_{i,j}, R_{i,j}, u_{i,j})$, $i\in [k], j\in [2]$. Lemma 3.2 finds a kraken in any expander with average degree at least some large constant.

Lemma 3.2.

Let $0<1/d\ll \varepsilon _1<1$ and let $G$ be an $n$-vertex $(\varepsilon _1,\varepsilon _1d)$-expander with $\delta (G)\geq d$. Let $L$ be the set of vertices in $G$ with degree at least $\log ^{100}n$ and let $m=100\varepsilon _1^{-1}\log ^3n$. Then, there exists a $(k,m,\log ^{10}n)$-kraken $(C, A_{i,j}, R_{i,j}, u_{i,j})$, $i\in [k], j\in [2]$, in $G$ for some $k\le \log n$ such that

•

either $\{u_{i,j}:i̇\in [k], j\in [2]\}\subseteq L$;

•

or $|L|\le 2\log n$ and any distinct $u_{i,j}, u_{i',j'}\not \in L$ are a distance at least $\sqrt {\log n}$ apart in $G-L$.

Proof of Theorem 1.1.

Let $L$ be the set of high degree vertices and $K=(C, A_{i,j}, R_{i,j}, u_{i,j})$, $i\in [k],j\in [2]$, be the kraken as in Lemma 3.2. We will embed, for each $i\in \mathbb{Z}_k$, a path $P_i$ between $u_{i,2}$ and $u_{i+1,1}$ of length at most $30m$, such that all paths $P_i$ are internally pairwise disjoint and also disjoint from $C$ and $R_{i,j}$, $i\in [k], j\in [2]$. Here, indices are taken modulo $k$. Such paths $P_i$, $i\in [k]$, together with $C$ and $R_{i,j}$, $i\in [k], j\in [2]$, form the desired nested cycles without crossings.

If the first alternative in Lemma 3.2 occurs, i.e. all $u_{i,j}\in L$, $i\in [k], j\in [2]$, then we can iteratively find the desired paths $P_i$, $i\in [k]$, by linking $N(u_{i,2})$ and $N(u_{i+1,1})$ avoiding previously built paths and the kraken $K$, using Lemma 2.3. Indeed, the number of vertices to avoid is at most $|V(K)|+k\cdot 30m\le \log ^{20}n$, which is much smaller than the degree of vertices in $L$.

We may then assume that $|L|\leq 2\log n$ and distinct $u_{i,j}, u_{i',j'}\not \in L$ are at distance at least $\sqrt {\log n}$ apart in $G'=G-L$. Let $V'\subseteq V(C)$ be the set of vertices not linked to vertices in $L$, i.e. $V'=\{v_i\in V(C):\nobreakspace \{u_{i,1}, u_{i,2}\}\not \subseteq L\}$.

For each $v_i\in V'$ and $j\in [2]$ with $u_{i,j}\not \in L$, write $Y_{i,j}=(\cup _{i'\in [k], j'\in [2]}R_{i',j'}\setminus \{u_{i,j}\}) \cup V(C)$. Note that $|Y_{i,j}|\le \log ^5n$. Recall that $|A_{i,j}|=\log ^{10}n$. Applying Proposition 2.5 with $(X,Y,W)_{\xhref[statement]{#ltxid18}{2.5}}=(A_{i,j}, Y_{i,j}\cup L,\varnothing )$, we can expand $A_{i,j}$ in $G'$ avoiding $Y_{i,j}$ to get $A_{i,j}^*\coloneq B_{G'-Y_{i,j}}^r(A_{i,j})$ of size at least $\log ^{30}n$, where $r=(\log \log n)^{10}$. Moreover, note that for distinct $v_i,v_{i'}\in V'$ and $j,j'\in [2]$ with $u_{i,j},u_{i',j'}\not \in L$, $u_{i,j}$ and $u_{i',j'}$ are at distance at least $\sqrt {\log n}$ apart in $G'$; therefore the corresponding $A_{i,j}^*$ and $A_{i',j'}^*$ are disjoint.

Finally, for $v_i\in V'$ and $j\in [2]$ with $u_{i,j}\in L$ and all $v_i\in V(C)\setminus V'$ and $j\in [2]$ whose corresponding $u_{i,j}$ lie in $L$, we can choose pairwise disjoint $A_{i,j}^*\subseteq N(u_{i,j})\setminus (\cup _{v_{i'}\in V', j'\in [2]}A^*_{i',j'})$, each of size $\log ^{30}n$. For each $i\in \mathbb{Z}_k$, link $A_{i,2}^*$ and $A_{i+1,1}^*$ in $G$ to get a path $Q_i$ with length at most $m$ using Lemma 2.3, avoiding previously built path $Q_j$ and $K$ (indices are taken modulo $k$). The desired path $P_i$ between $u_{i,2}$ and $u_{i+1,1}$ can be obtained by extending $Q_i$ in $A_{i,2}^*\cup A_{i+1,1}^*$.

This concludes the proof.

■

4. Release the Kraken!

In this section, we prove Lemma 3.2. The idea of the proof is the following. We take a shortest cycle $C$ in the graph, and consider two cases depending on whether the set $L$ of high degree vertices is large or not. For the case where this set $L$ is large, we want to link each vertex on the cycle $C$ to two different vertices in $L$ by expanding vertices in $C$ using Proposition 2.5. If there is a small number of high degree vertices, we will use the fact that the graph $G-L$ has relatively small maximum degree, and so we can find within $G-L$ many large connected sets of vertices that are pairwise far apart. Then we will expand vertices in $C$ to link them to these connected sets.

One difficulty here is that the number of paths we need to build to link either high degree vertices or large connected sets to vertices in $C$ could be as large as $\Omega (\log n)$, while the degree of each vertex in $C$ could be as small as $O(1)$. We have to be careful when embedding these paths so that no vertex in $C$ gets isolated.

Let us first see how we can link vertices on a shortest cycle to high degree vertices in $L$ as follows.

Lemma 4.1.

Let $0<1/d\ll \varepsilon _1<1$ and let $G$ be an $n$-vertex $(\varepsilon _1,\varepsilon _1d)$-expander with $\delta (G)\geq d$. Let $L$ be the set of vertices in $G$ with degree at least $\log ^{100}n$ and let $m=100\varepsilon _1^{-1}\log ^3n$. Let $C$ be a shortest cycle in $G$ with vertices $v_1$, …, $v_k$ and let $\mathcal{P}$ be a maximal collection of paths in $G$ from $V(C)$ to $L$ such that:

•

each $v\in V(C)$ is linked to at most $2$ vertices in $L$;

•

all paths are pairwise disjoint outside of $V(C)$ with internal vertices in $V(G)\setminus (V(C)\cup L)$;

•

each path has length at most $10m$.

Subject to $|\mathcal{P}|$ being maximal, let $\ell (\mathcal{P})\coloneq \sum _{P\in \mathcal{P}}\ell (P)$ be minimised.

Let $U=V(C)\cup V(\mathcal{P})$. Then,

(i)

for any vertex $v\in C$ that is in less than 2 paths in $\mathcal{P}$, the set $U\setminus \{v\}$ is $(10,2)$-thin around $v$ in $G$; and

(ii)

at least $\min \{|L|, 2k\}$ many vertices in $L$ are linked to paths in $\mathcal{P}$.

Proof.

First of all, $|C|=k\leq 2\log _d n\leq \log n$ due to $\delta (G)\ge d$. Consequently, as there are at most two paths containing each vertex in $C$, we have that $|\mathcal{P}|\le 2|C|\le 2\log n$. So

$$\begin{equation} |U|\leq \log n+2\log n\cdot 10m\leq 4000\varepsilon _1^{-1}\cdot \log ^4 n. {\tag{2}} \end{equation}$$

Notice that as $C$ is a shortest cycle in $G$, for any $i\in \mathbb{N}$, we have

$$\begin{equation} |N_G(B_{G-V(C)}^{i-1}(v))\cap V(C)|\leq 2i, {\tag{3}} \end{equation}$$

for otherwise, replacing the segment of $C$ intersecting $N_G(B_{G-V(C)}^{i-1}(v))$ with a path of length at most $2i$ in $B_{G-V(C)}^{i-1}(v)\cup N_G(B_{G-V(C)}^{i-1}(v))$ results in a shorter cycle than $C$, contradicting the minimality of $C$.

Let us first prove (i). Suppose $v\in C$ is in less than 2 paths in $\mathcal{P}$.

Claim 4.2.

$U\setminus \{v\}$ is $(10,2)$-thin around $v$ in $G$.

Proof of Claim 4.2.

Fix first an arbitrary path $P$ in $\mathcal{P}$. Similar to 3, by the minimality of $\ell (\mathcal{P})$, we have for any $i\in \mathbb{N}$ that

$$\begin{equation} |N_G(B_{G-U\setminus \{v\}}^{i-1}(v))\cap V(P)|\leq i. {\tag{4}} \end{equation}$$

Next, fix $i\in \mathbb{N}$ and consider the set $B_C^{4i}(v)$. Let $\widehat{P}$ be a path in $\mathcal{P}$ whose endvertex $\hat{v}$ in $C$ is not in $B_C^{4i}(v)$ (if such a path exists). Notice that

$$\begin{equation} N_G(B_{G-U\setminus \{v\}}^{i-1}(v))\cap \widehat{P}=\varnothing . {\tag{5}} \end{equation}$$

To see this, split $\widehat{P}$ into two parts $\widehat{P}^0$ and $\widehat{P}^1$, with $\widehat{P}^0$ consisting of the nearest $2i$ vertices to $C$ in $\widehat{P}$, and $\widehat{P}^1$ being the remaining ones. If there is a vertex $y\in N_G(B_{G-U\setminus \{v\}}^{i-1}(v))\cap \widehat{P}^0$, let $\widehat{Q}$ be the path between $v$ and $y$ of length $i$ with internal vertices in $B_{G-U\setminus \{v\}}^{i-1}(v)$. Then $\widehat{Q}\cup \widehat{P}^0$ contains a path $Q$ between $v$ and $\hat{v}$ of length at most $3i$ with $V(Q)\cap V(C)=\{v,\hat{v}\}$. Replacing the segment between $v$ and $\hat{v}$ in $C$ (which is of length at least $4i$) with $Q$ results in a shorter cycle than $C$, a contradiction. So, we must have $N_G(B_{G-U\setminus \{v\}}^{i-1}(v))\cap \widehat{P}^0=\varnothing$. If there is $y'\in N_G(B_{G-U\setminus \{v\}}^{i-1}(v))\cap \widehat{P}^1$, then $y'$ is at distance at most $i$ from $v$ in $G-U\setminus \{v\}$ and at distance at least $2i$ from $\hat{v}$ on $\widehat{P}$, so $B_{G-U\setminus \{v\}}^{i-1}(v)\cup \widehat{P}^1$ contains a shorter path between $V(C)$ and $L$, contradicting the minimality of $\ell (\mathcal{P})$. Hence, $N_G(B_{G-U\setminus \{v\}}^{i-1}(v))\cap \widehat{P}^1=\varnothing$, as desired.

Let $\mathcal{P}_{4i}$ be the set of paths in $\mathcal{P}$ whose endvertices in $C$ are in $B_C^{4i}(v)$. By 4 and 5, we see that

$$\begin{equation*} \big |\big (N_G(B_{G-U\setminus \{v\}}^{i-1}(v))\big )\cap V(\mathcal{P})\big |=\Big |\bigcup _{P\in \mathcal{P}_{4i}}\Big (N_G(B_{G-U\setminus \{v\}}^{i-1}(v))\cap V(P)\Big )\Big |\leq 2\cdot 4i\cdot i= 8 i^2. \end{equation*}$$

This, together with 3, implies that

$$\begin{align*} |N_G(B_{G-U\setminus \{v\}}^{i-1}(v))&\cap (U\setminus \{v\})\}|\\ &\leq |N_G(B_{G-U\setminus \{v\}}^{i-1}(v))\cap V(C)|\\ &\quad +|N_G(B_{G-U\setminus \{v\}}^{i-1}(v))\cap V(\mathcal{P})|\leq 10 i^2. \end{align*}$$

Therefore, $U\setminus \{v\}$ is $(10,2)$-thin around $v$ as claimed.

■

Let us now turn to part (ii). Suppose for a contradiction that less than $\min \{|L|, 2k\}$ many vertices in $L$ are linked to paths in $\mathcal{P}$. Then either $|\mathcal{P}|<|L|<2k$ or $|L|\ge 2k$ and $|\mathcal{P}|\le 2k-1$. In both cases, there are a vertex $v\in V(C)$ which is in less than $2$ paths in $\mathcal{P}$ and a high degree vertex $w\in L\setminus V(\mathcal{P})$ not linked to any path in $\mathcal{P}$. Then, by Claim 4.2, $U\setminus \{v\}$ is $(10,2)$-thin around $v$ in $G$.

Setting $r=(\log \log n)^{10}$ and applying Proposition 2.5 with $(X,Y,W)_{\xhref[statement]{#ltxid18}{2.5}}=(\{v\},\varnothing , U\setminus \{v\})$ gives

$$\begin{equation} |B^r_{G-U\setminus \{v\}}(v)|\geq \exp (r^{\frac{1}{4}})=\log ^{100}n. {\tag{6}} \end{equation}$$

Recall that we have a vertex $w\in L\setminus V(\mathcal{P})$ not in any paths in $\mathcal{P}$ with degree $\deg (w)\geq \log ^{100}n$. Thus, by Lemma 2.3, 2 and 6, we can connect $B^r_{G-U\setminus \{v\}}(v)$ and $N_G(w)$ with a path of length at most $m$ in $G-U\setminus \{v\}$, which extends in $B^{r}_{G-U\setminus \{v\}}(v)\cup \{w\}$ to a path between $v$ and $w$ in $G-U\setminus \{v\}$ with length at most $10m$, contradicting the maximality of $\mathcal{P}$. Thus, at least $\min \{|L|, 2k\}$ many vertices in $L$ are linked to paths in $\mathcal{P}$ as desired.

■

We are now ready to prove Lemma 3.2.

Proof of Lemma 3.2.

Let $C$ and $\mathcal{P}$ be as in Lemma 4.1. We distinguish two cases depending on how many high degree vertices there are in $L$.

Case 1.

Suppose $|L|\geq 2k$. Then by Lemma 4.1(ii), at least $2k$ vertices in $L$ are linked in paths in $\mathcal{P}$. By the choice of $\mathcal{P}$, we see that each vertex in $V(C)$ is in exactly $2$ paths in $\mathcal{P}$. Label the paths $R_{i,j}$ so that $v_i$ is the endvertex of $R_{i,j}$ in $C$ for $i\in [k], j\in [2]$, and let $u_{i,j}$ be the endvertex of $R_{i,j}$ in $L$. As vertices in $L$ have high degree, we can comfortably choose pairwise disjoint $A_{i,j}$ from $N(u_{i,j})$, each of size $\log ^{10}n$, yielding the first alternative.

Case 2.

Suppose $|L|<2k$. Then by Lemma 4.1(ii) again, we see that every vertex in $L$ is linked to a path in $\mathcal{P}$, i.e. $L\subseteq V(\mathcal{P})$. Note that $|V(\mathcal{P})|\le 2k\cdot 10m\le \log ^5n$. Relabelling if necessary, let $k'\leq k$ be such that $v_1$, …, $v_{k'}$ are the vertices in $C$ that are not linked in $\mathcal{P}$ to two vertices in $L$. Let

$$\begin{equation*} V'=\{v_1,\dots ,v_{k'}\} \quad \text{ and } G'\coloneq G-(V(\mathcal{P})\setminus V')\subseteq G-L. \end{equation*}$$

Then, by the definition of $L$, $\Delta (G')\leq \log ^{100}n$.

Claim 4.3.

There are sets $B_i\subseteq V(G')$, $i\in [n^{1/8}]$, each of diameter at most $m$ and size $n^{1/8}$, that are at distance at least $4\sqrt {\log n}$ from each other and from $V(C)$ in $G'$.

Proof of Claim.

Take a maximal collection of sets $B_i$, $i\in [s]$, with the claimed size, which are pairwise far apart and far from $V(C)$ in $G'$. If $s<n^{1/8}$, then

$$\begin{equation*} \big |B_{G'}^{4\sqrt {\log n}}(\cup _{i\in [s]}B_i\cup V(C))\big |\leq 2\cdot (s n^{1/8}+\log n)\cdot \Delta (G')^{4\sqrt {\log n}} <\sqrt {n}. \end{equation*}$$

Then by Lemma 2.6 with $W_{\xhref[statement]{#ltxid19}{2.6}}=V(\mathcal{P})\cup B_{G'}^{4\sqrt {\log n}}(\cup _{i\in [s]}B_i\cup V(C))$, we can find another large set with small diameter far apart from $\cup _{i\in [s]}B_i\cup V(C)$ in $G'$, a contradiction.

■

Let $B_i, i\in [n^{1/8}]$, be the sets from the above claim. For each $i\in [n^{1/8}]$, let $B_i'\subseteq B_i$ be a connected subset of size $\log ^{10}n$, and set $\mathcal{B}=\{B_i'\}_{i\in [n^{1/8}]}$. Let $\mathcal{P}'$ be a maximal collection of paths in $G'$ from $V'$ to $V(\mathcal{B})$ such that

•

each $v\in V'$ is in at most two paths of $\mathcal{P}'$ and each set in $\mathcal{B}$ is linked to at most one path;

•

all paths are pairwise disjoint outside of $V'$ with internal vertices in $V(G')\setminus V(\mathcal{B})$;

•

the length of each path is at most $10m$.

Subject to $|\mathcal{P'}|$ being maximal, let $\ell (\mathcal{P}')\coloneq \sum _{P\in \mathcal{P'}}\ell (P)$ be minimised.

Suppose, for contradiction, that there is some $v\in V'$ which is in less than two paths in $\mathcal{P}'$. Let $\mathcal{B}'\subseteq \mathcal{B}$ be the collection of sets linked to some path in $\mathcal{P}'$; then $|V(\mathcal{B}')|\le 2|V'|\cdot \log ^{10}n\le \log ^{12} n$. Let $U''\coloneq V(C)\cup V(\mathcal{P})\setminus \{v\}$ and let $U'\coloneq V(C)\cup V(\mathcal{P})\cup V(\mathcal{P}')\setminus \{v\}$, so $|U'|\le \log n+2k\cdot 10m\le \log ^5n$. Note that $|U'|+|V(\mathcal{B}')|<|\mathcal{B}|/2$, thus taking the subfamily $\mathcal{B}''\subseteq \mathcal{B}$ of connected sets that are disjoint from $U'\cup V(\mathcal{B}')$, we have $|\mathcal{B}''|\ge |\mathcal{B}|/2$.

By the choice of $V'$, the vertex $v\in V'$ is in less than 2 paths in $\mathcal{P}$. Thus, by Lemma 4.1(i), $U''$ is $(10,2)$-thin around $v$ in $G$. On the other hand, by the minimality of $C$ and $\ell (\mathcal{P}')$, as in 4 and 5, we have for any $i\in \mathbb{N}$, for any path $P\in \mathcal{P}'$, and for each path $\tilde{P}\in \mathcal{P}'$ whose endvertex $\tilde{v}$ in $C$ is not in $B_C^{4i}(v)$ (if such a path exists) that

$$\begin{equation*} |N_G(B_{G-U'}^{i-1}(v))\cap V(P)|\leq i \quad \text{ and }\quad N_G(B_{G-U'}^{i-1}(v))\cap \tilde{P}=\varnothing . \end{equation*}$$

Thus, writing $\mathcal{P}'_{4i}$ for the set of paths in $\mathcal{P}'$ whose endvertices in $C$ are in $B_C^{4i}(v)$, we get that

$$\begin{equation*} \big |\big (N_G(B_{G-U'}^{i-1}(v))\big )\cap V(\mathcal{P}')\big |=\Big |\bigcup _{P\in \mathcal{P}'_{4i}}\Big (N_G(B_{G-U'}^{i-1}(v))\cap V(P)\Big )\Big |\leq 2\cdot 4i\cdot i= 8 i^2. \end{equation*}$$

This, together with the fact that $U''$ is $(10,2)$-thin around $v$ in $G$, implies that

$$\begin{align*} \big |\big (N_G(B_{G-U'}^{i-1}(v))\big )\cap U'\big | &\le \big |\big (N_G(B_{G-U'}^{i-1}(v))\big )\cap U''\big | + \big |\big (N_G(B_{G-U'}^{i-1}(v))\big )\cap V(\mathcal{P}')\big | \\ &\leq \big |\big (N_G(B_{G-U''}^{i-1}(v))\big )\cap U''\big | +8i^2\leq 18 i^2, \end{align*}$$

where the second inequality holds as $B_{G-U'}^{i-1}(v)\subseteq B_{G-U''}^{i-1}(v)\subseteq V(G)\setminus U''$.

Thus, $U'$ is $(18,2)$-thin around $v$ in $G$. Then as in 6, we can expand $v$ in $G-U'\subseteq G'$. Furthermore, by Claim 4.3, $B_{G-U'}^r(v)$ is disjoint from $V(\mathcal{B})$. As $U'\cup V(\mathcal{B}')$ is much smaller than $V(\mathcal{B}'')$ and $B_{G-U'}^r(v)$, we can find a path of length at most $m$ in $G-U'-V(\mathcal{B}')$ between $V(\mathcal{B}'')$ and $B_{G-U'}^r(v)$ using Lemma 2.3. Extending this path to $v$ yields one more path between $V'$ and $V(\mathcal{B})$, contradicting the maximality of $\mathcal{P}'$.

Therefore, each vertex in $V'$ is in exactly two paths in $\mathcal{P}'$, and by construction, the non-$V'$ endvertices of $\mathcal{P}'$ (each in some set $B_i$) are pairwise at least $\sqrt {\log n}$ apart in $G'$. Thus, picking appropriate neighbourhoods of endvertices of $\mathcal{P}$ in $L$, together with $\mathcal{P}'$ and $\mathcal{B}'$, yields the second alternative.

■

Figure 1.

Figure 1(a)

(a) Two edge-disjoint nested cycles

Figure 1(b)

(b) Two nested cycles without crossings

Figure 2.

A $(6,m,s)$-kraken with an inner cycle $C$ of length $6$. Each vertex $v_i$ in $C$ has two arms attached to it. The arms of the kraken and the (red) paths linking them form the outer cycle.