# Embedding clique subdivisions via crux

Donglei Yang School of Mathematics, Shandong University, Jinan, Shandong,
China. Email<EMAIL_ADDRESS>Supported by Natural Science Foundation of
China (12101365) and by Natural Science Foundation of Shandong Province
(ZR2021QA029). Fan Yang Data Science Institute, Shandong University, Jinan,
Shandong, China. Email<EMAIL_ADDRESS>Supported by Natural Science
Foundation of China (12301447) and by China Postdoctoral Science Foundation
(12570073310023).

###### Abstract

For a graph $G$ and a constant $\alpha>0$, we denote by $C_{\alpha}(G)$ the
minimum order of a subgraph $H\subseteq G$ with $d(H)\geq\alpha d(G)$. Liu and
Montgomery conjectured that every graph $G$ contains $K_{\Omega(t)}$ as a
subdivision for $t=\min\\{d(G),\sqrt{\tfrac{C_{\alpha}(G)}{\log
C_{\alpha}(G)}}\\}$. In the paper, we prove this conjecture.

##  1 Introduction

For a graph $H$, a _subdivision_ of $H$, denoted by $TH$, is a graph obtained
by replacing edges of $H$ by internally vertex-disjoint paths. This is a
fundamental concept for studying topological aspects of graphs since
Kuratowski [22] (in 1930) used this notion to characterize the planar graphs,
proving that a graph is planar if and only if it does not contain a
subdivision of $K_{5}$ or $K_{3,3}$. A well-studied direction of research in
extremal graph theory is to find sufficient conditions on a graph $G$ that
would guarantee the existence of an $H$-subdivision in $G$.

Such problem has received considerable attention since the work of Mader [26]
from 1967 on the optimal average degree conditions forcing subdivisions of
large cliques. More precisely, Mader showed that for every $k\in\mathbb{N}$,
there exists (finite) $f(k)$ such that every graph $G$ with average degree at
least $f(k)$ contains a $TK_{k}$. Mader [26], and independently Erdős and
Hajnal [7], conjectured that one can take $f(k)=O(k^{2})$. This conjecture was
finally resolved in 1999 by Bollobás and Thomason [3] and independently by
Komlós and Szemerédi [17]. In fact, Jung [14] observed that
$K_{k^{2}/8,k^{2}/8}$ does not contain $TK_{k}$, which implies that the
quadratic bound on $f(k)$ is best possible.

Note that the extremal examples mentioned above consist of (disjoint union of)
complete bipartite graphs. The following question naturally arises: can we
find a larger clique subdivision in $G$ if it does not structurally look like
(disjoint union of) dense bipartite graph? In 1999, Mader [27] conjectured
that any $C_{4}$-free graph contains a subdivision of a clique with order
linear in its average degree. This linear bound is essentially optimal under
the obvious “degree constraint” as the host graph could be regular. After some
partial results (see e.g. [2, 20, 21]), Mader’s conjecture was subsequently
resolved by Liu and Montgomery [24] in 2017. They also proved an analogous
result for $K_{s,t}$-free graphs, asserting that for $t\geq s\geq 2$, every
$K_{s,t}$-free graph $G$ with $d(G)=d$ contains a $TK_{\Omega(d^{s/2(s-1)})}$.

The exclusion of $K_{s,t}$ has proven to be a good way to formalize the
stability-type question aforementioned. Liu and Montgomery [24] also suggested
another way to formalize this: whether a graph with no small subgraphs which
are almost as dense as the parent graph must contain a large clique
subdivision? To formulate this, they introduced a new graph parameter
depicting the order of the smallest dense patch of a graph, which was recently
named _crux_ by Haslegrave Hu, Kim, Liu, Luan and Wang [10]. The notion of
crux has recently been used to capture the “essential order” of a graph with
applications to finding long cycles in graphs and random subgraphs (see e.g.
[10]), though similar idea already appeared implicitly in previous works due
to for example Krivelevich and Samotij [18].

######  Definition 1.1 (Crux).

Given a graph $G$ and a constant $\alpha>0$, a subgraph $H\subseteq G$ is an
_$\alpha$ -crux_ of $G$ if $d(H)\geq\alpha d(G)$. Let $C_{\alpha}(G)$ be the
minimum order over all $\alpha$-cruxs of $G$.

Observing that the disjoint union of dense bipartite graphs have
$C_{\alpha}(G)$ linear in the average degree, Liu and Montgomery [24] raised
the following conjecture by taking $\alpha=\tfrac{1}{100}$.

######  Conjecture 1.2 ([24]).

There exists some constant $c>0$ such that every graph $G$ contains a
subdivision of a clique with at least
$c\min\Big{\\{}d(G),\sqrt{\tfrac{C_{\alpha}(G)}{\log C_{\alpha}(G)}}\Big{\\}}$
vertices.

If true, this bound is tight: as noted in [24], the $d/1000$-blow-up $G$ of a
$d$-vertex $1000$-regular expander satisfies $C_{\alpha}(G)=\Theta(d^{2})$ and
the largest clique subdivision has order $O(d/\sqrt{\log d})$. For
convenience, we will often call this construction a space barrier. To see
this, note that $G$ has $\Omega(d^{2})$ vertices and any $K_{t}$-subdivision
in $G$ has $\tbinom{t}{2}$ internally vertex-disjoint paths. As discussed in
[24], when $t$ is close to $d$, among any collection of $t$ vertices in $G$,
there are at least $\tfrac{1}{4}t^{2}$ pairs of vertices that are far apart
from each other by a distance $\Omega(\log d)$. This tells that at least half
of the subdivided paths must contain at least $\Omega(\log d)$ vertices, which
implies $t=O(d/\sqrt{\log d})$.

Note that Im, Kim, Kim and Liu [13] recently proved a weaker bound for
$\alpha=\tfrac{1}{100}$.

######  Theorem 1.3 ([13]).

There exists an absolute constant $\beta>0$ such that the following is true.
Let $G$ be a graph with $d(G)=d$. Then $G$ contains a $K_{\beta t/(\log\log
t)^{6}}$-subdivision where

$t=\min\Big{\\{}d,\sqrt{\tfrac{C_{\alpha}(G)}{\log C_{\alpha}(G)}}\Big{\\}}.$

Our main result answers Conjectur 1.2 in the affirmative.

######  Theorem 1.4.

There exists an absolute constant $c>0$ such that the following is true for
any $0<\alpha\leq\tfrac{1}{9\times 10^{4}}$. Let $G$ be a graph with $d(G)=d$.
Then $G$ contains a $K_{ct}$-subdivision where

$t=\min\Big{\\{}d,\sqrt{\tfrac{C_{\alpha}(G)}{\log{C_{\alpha}(G)}}}\Big{\\}}.$

We make no attempt to optimize the constant coefficients $c$ and $\alpha$ in
Theorem 1.4.

Technical Contribution. Our approach builds on the recently-developed
sublinear expander theory and introduces new perspectives on the $\alpha$-crux
number $C_{\alpha}(G)$. To build large clique subdivisions, we adopt a
strategy of Liu and Montgomery [24] (also appeared in previous works [28]),
namely, to find a sufficient number of star-like structures called “units”
that serve as the bases for constructing the required subdivision. To do this,
it is desired that all these units do not overlap too much and each has a
large exterior and (relatively) small interior. Then the arguments often
reduce to robustly connecting the exteriors with disjoint short paths whilst
avoiding the interiors, using the connectivity provided by the sublinear
expander. In this paper, we use a variant of unit structure called web (see
Definition 2.5) and the bulk of the work is therefore to construct a family of
webs as above within a sublinear expander. Note that the extremal construction
(space barrier) tells that the (almost half) subdivided paths in the
$K_{\Omega(t)}$-subdivision has length $\Theta(\log n)$. This requires us to
be able to find disjoint short connections of length $O(\log n)$ , which is in
fact a surprisingly challenging task in previous applications of sublinear
expander (e.g. in [13], they were able to find disjoint subdivided paths of
length $\log n(\log\log n)^{O(1)}$). To see this, note that in the space
barrier, all the subdivided paths have too many (up to $\Omega(n)$) vertices
to naively find one more path which avoids previous paths just by applying the
commonly-used Lemma 2.3. This is where our new perspectives on the
$\alpha$-crux number and a random variant of Lemma 2.3 come into play (see
Section 3.1 for a more elaborate sketch of the proof)..

The proof of Theorem 1.4 is divided into three main cases by distinguishing
the value of the $\alpha$-crux number $C_{\alpha}(G)$. We employ an unified
construction by combining our new perspectives on the $\alpha$-crux number
with an adaptation of random partitions for sublinear expanders appearing in a
very recent work of Bucić and Montgomery [5].

##  2 Preliminaries

###  2.1 Notation

For any positive integer $r$, we write $[r]$ for the set $\\{1,\ldots,r\\}$.
Given a graph $G=(V,E)$, we denote by $v(G),e(G),\Delta(G),\delta(G)$ the
number of vertices in $G$, the size of $G$, the maximum degree of $G$ and the
minimum degree of $G$. Given a set $W\subseteq V(G)$, we write
$N_{G}(W)=(\bigcup_{u\in W}N_{G}(u))\setminus W$. Furthermore, set
$N_{G}^{0}(W):=W$, $N_{G}^{1}(W):=N_{G}(W)$ and $N_{G}[W]=N_{G}(W)\cup W$, and
for each $i\geq 1$, define $N_{G}^{i+1}(W):=N(N_{G}^{i}(W))\setminus
N_{G}^{(i-1)}(W)$. Denote by $B_{G}^{r}(W)$ the ball of radius $r$ around $W$,
that is, $B_{G}^{r}(W)=\bigcup_{i\leq r}N_{G}^{i}(W)$. For simplicity, write
$B_{G}^{r}(v)=B_{G}^{r}(\\{v\\})$. For any set $W\subset V(G)$, the subgraph
of $G$ induced on $W$, denoted as $G[W]$, is the graph with vertex set $W$ and
edge set $\\{xy\in E(G)|x,y\in W\\}$, and write $G-W=G[V(G)\setminus W]$. For
any $A,B\subseteq V(G)$, we denote by $G[A,B]$ the graph with vertex set
$A\cup B$ and edge set $\\{xy\in E(G)|x\in A,y\in B\\}$. We simply use
$e_{G}(A,B)=|E(G[A,B])|$.

For a path $P$, the length of $P$ is the number of edges in $P$, and we say
$P$ is an $x,y$-path if $x$ and $y$ are the endvertices of $P$. A star is
called _$x$ -star_ for some $x\in\mathbb{N}$ if it has exactly $x$ leaves.
Given a family of graphs $\mathcal{F}$, denote by $|\mathcal{F}|$ the number
of graphs in $\mathcal{F}$ and we write
$V(\mathcal{F})=\bigcup_{G\in\mathcal{F}}V(G)$.

Throughout the paper, we will omit floor and ceiling signs when they are not
essential. Also, we use standard hierarchy notation, that is, we write $a\ll
b$ to denote that given $b$ one can choose $a_{0}$ such that the subsequent
arguments hold for all $0<a\leq a_{0}$. All logarithms except labeled one are
natural.

###  2.2 Sublinear expander

Komlós and Szemerédi [16, 17] introduced a notion of sublinear expander that
is a graph in which any subset of vertices of reasonable size expands by a
sublinear factor. Significant progress in several seemingly unrelated long-
standing open problems has been established by using techniques derived in the
notion of sublinear expander. Remarkable applications include the resolution
of Erdős and Hajnal’s odd cycle problem from 1966 [6] and a series of
breakthroughs concerning cycle decomposition (see [5]), graph Ramsey goodness
(see [12]), graph minor (see [19]) and so on. For more recent applications of
sublinear expanders to various problems in Extremal Combinatorics, we refer
readers to a comprehensive survey of Letzter [23].

Komlós and Szemerédi [17] showed that every graph $G$ contains a sublinear
expander almost as dense as $G$. Haslegrave, Kim and Liu [11] slightly
generalised this to a robust version.

######  Definition 2.1 ([11, 16, 17]).

Let $\varepsilon_{1}>0$ and $k\in\mathbb{N}$. A graph $G$ is an
_$(\varepsilon_{1},k)$ -robust-expander_ if for any $X\subseteq V(G)$ of size
$\tfrac{k}{2}\leq|X|\leq\tfrac{2|V(G)|}{3}$111the coefficient $2/3$ makes no
difference and can be easily verified to be valid by going through their proof
in [11], and any subgraph $F\subseteq G$ with $e(F)\leq
d(G)\rho(|X|,\varepsilon_{1},k)\cdot|X|$, we have

$|N_{G\setminus F}(X)|\geq\rho(|X|,\varepsilon_{1},k)\cdot|X|$

where

$\rho(x,\varepsilon_{1},k):=\begin{cases}0&\text{if }x<k/5,\\\
\varepsilon_{1}/\log^{2}(15x/k)&\text{if }x\geq k/5.\end{cases}$

We often say such $G$ is an _$(\varepsilon_{1},k)$ -expander_ if $e(F)=0$. For
simplicity, we write $\rho(x)$ for $\rho(x,\varepsilon_{1},k)$. Note that
$\rho(x)$ is a decreasing function when $x\geq\tfrac{k}{5}$.

######  Lemma 2.2 ([11, 17]).

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

Expanders are usually highly connected sparse graphs with certain expansion
properties. A key property of the subliner expanders that we shall use is to
connect vertex sets with a short path whilst avoiding a reasonable-sized set
of vertices.

######  Lemma 2.3 (Robust connectivity, [17]).

Let $\varepsilon,k>0$. If $G$ is an $n$-vertex $(\varepsilon,k)$-robust-
expander, then for any two vertex sets $X_{1},X_{2}$ each of size at least
$x\geq k$, and a vertex set $W$ of size at most $\tfrac{\rho(x)x}{4}$, there
exists a path in $G-W$ between $X_{1}$ and $X_{2}$ of length at most
$\tfrac{2}{\varepsilon}\log^{3}\Big{(}\tfrac{15n}{k}\Big{)}$.

###  2.3 Units and Webs

######  Definition 2.4 (unit).

For $h_{1},h_{2},h_{3}\in\mathbb{N}$, a graph $F$ is an _$(h_{1},h_{2},h_{3})$
-unit_ if it contains distinct vertices $u$ (the _core_ vertex of $F$) and
$x_{1},\ldots,x_{h_{1}}$, and $F=\bigcup_{i\in[h_{1}]}(P_{i}\cup S_{i})$,
where

  * •

$\mathcal{P}=\bigcup_{i\in[h_{1}]}P_{i}$ is a collection of pairwise
internally vertex-disjoint paths, each of length at most $h_{3}$, such that
$P_{i}$ is a $u,x_{i}$-path, and

  * •

$\mathcal{S}=\bigcup_{i\in[h_{1}]}S_{i}$ is a collection of vertex-disjoint
$h_{2}$-stars such that $S_{i}$ has center $x_{i}$ and
$\bigcup_{i\in[h_{1}]}(V(S_{i})\setminus\\{x_{i}\\})$ is disjoint from
$V(\mathcal{P})$.

We call $S_{i}$ a _pendent_ star in the unit $F$ and every such path $P_{i}$
is a _branch_ of $F$. Define the _exterior_
$\mathsf{Ext}(F):=\bigcup_{i\in[h_{1}]}(V(S_{i})\setminus\\{x_{i}\\})$ and
_interior_ $\mathsf{Int}(F):=V(F)\setminus\mathsf{Ext}(F)$.

######  Definition 2.5 (web).

For $h_{1},h_{2},h_{3},h_{4},h_{5}\in\mathbb{N}$, a graph $W$ is an
_$(h_{4},h_{5},h_{1},h_{2},h_{3})$ -web_ if it contains distinct vertices $v$
(the _core_ vertex of $W$), $u_{1},\ldots,u_{h_{4}}$, and
$W=\bigcup_{i\in[h_{4}]}(Q_{i}\cup F_{i})$, where

  * •

$\mathcal{Q}=\bigcup_{i\in[h_{4}]}Q_{i}$ is a collection of pairwise
internally vertex-disjoint paths such that each $Q_{i}$ is a $v,u_{i}$-path of
length at most $h_{5}$.

  * •

$\mathcal{F}=\bigcup_{i\in[h_{4}]}F_{i}$ is a collection of vertex-disjoint
$(h_{1},h_{2},h_{3})$-units such that $F_{i}$ has core vertex $u_{i}$ and
$\bigcup_{i\in[h_{4}]}(V(F_{i})\setminus\\{u_{i}\\})$ is vertex-disjoint from
$V(\mathcal{Q})$.

We call each $Q_{i}$ a _branch_ and call the branches inside each unit $F_{i}$
the _second-level_ branches of $W$. Similarly define the _exterior_
$\mathsf{Ext}(W):=\bigcup_{i\in[h_{0}]}\mathsf{Ext}(F_{u_{i}})$, and the
_interior_ $\mathsf{Int}(W):=V(W)\setminus\mathsf{Ext}(W)$ and additionally
define _center_ $\mathsf{Ctr}(W):=V(\mathcal{Q})$.

Figure 1: unit and web

##  3 Main lemmas and overviews

In this section we give an outline of our proof, and compare with previous
approaches. To construct a large clique subdivision as in Theorem 1.4, we
first apply Lemma 2.2 to obtain in $G$ a subgraph with expansion properties.
Unlike in [13, 24], the construction we use differs by comparing the value of
$C_{\alpha}(G)$ with the density of the subgraph. We first consider the case
when $C_{\beta}(G)$ is larger than $d^{2}\log^{O(1)}n$ (see Lemma 3.1) for
some $\beta$ slightly larger than $\alpha$ given as in Theorem 1.4. Here we
often call it a non-extremal case as it is far apart from the space barrier.

######  Lemma 3.1 (Non-extremal).

Suppose
$\tfrac{1}{n},\tfrac{1}{d}\ll\tfrac{1}{T},c\ll\beta,\varepsilon\leq\tfrac{1}{150}$
and $k\in\mathbb{N}$ has $k\leq\min\\{d^{2},\tfrac{n}{T}\\}$ and
$d\geq\log^{1000}n$. Let $G$ be an $n$-vertex $(\varepsilon,k)$-robust-
expander with $\delta(G)\geq\tfrac{1}{2}d(G)\geq\tfrac{1}{16}\beta d$ and
$m=\log^{4}\tfrac{n}{k}$. If $\tfrac{C_{\beta}(G)}{\log C_{\beta}(G)}\geq
d^{2}m^{100}$, then $G$ contains a $K_{cd}$-subdivision.

The case when $C_{\beta}(G)$ is close to $d^{2}$ (within a polylogarithmic
factor) is most involved and the bulk of the work is to handle this, as the
extremal construction (space barrier) may appear. To achieve this, we choose a
smallest $\beta$-crux $H\subseteq G$ and attempt to find desired clique
subdivisions within $H$ instead. We will again use Lemma 2.2 to find an
$(\varepsilon,k)$-robust-expander $H^{*}\subseteq H$ for a different value of
$k$ and then utilize the following lemma.

######  Lemma 3.2 (Extremal).

Suppose $\tfrac{1}{n},\tfrac{1}{d}\ll c\ll\beta,\varepsilon\leq\tfrac{1}{150}$
and $p,k\in\mathbb{N}$ satisfy
$k=\min\\{\tfrac{d^{2}}{\log^{p}d},\tfrac{n}{\log^{p}n}\\}$ for $p\geq 1000$.
Let $G$ be an $(\varepsilon,k)$-robust-expander with $v(G)\leq n$ and
$\delta(G)\geq\tfrac{1}{2}d(G)\geq\tfrac{1}{16}\beta d$. If
$d\geq\sqrt{\tfrac{n}{\log^{p}n}}$ and $C_{\beta}(G)\geq k\log k$, then $G$
contains a $K_{ct}$-subdivision, where
$t=\min\\{d,\sqrt{\tfrac{C_{\beta}(G)}{\log C_{\beta}(G)}}\\}$.

We shall use Lemma 3.2 to cover the (extremal) case when
$d\geq\sqrt{\tfrac{v(H)}{\log^{p}v(H)}}$ and $C_{\alpha}(G)\geq k\log k$. To
tackle the space barrier, we need to bound the value of $k$ in Lemma 3.2 so as
to robustly find short subdivided paths of nearly optimal length $O(\log n)$
(see Section 3.1 for more details).

The remaining (non-extremal) case is now well understood, due to the work of
Im, Kim, Kim and Liu [13], and the following result suffices to give the
required subdivision when $C_{\alpha}(G)<k\log k$, though the bound on $t$ is
not optimal in general.

######  Lemma 3.3 ([13]).

Suppose $\tfrac{1}{n}\ll\tfrac{1}{T}\ll\varepsilon<\tfrac{1}{100}$ and
$d\geq\exp(\log^{1/6}n)$. If an $n$-vertex $(\varepsilon,\varepsilon
d)$-robust-expander $G$ has average degree at least $\tfrac{d}{2}$ and minimum
degree $\delta(G)\geq\tfrac{d}{4}$, then $G$ contains a $K_{t}$-subdivision
where $t=\min\\{\tfrac{d}{\log^{60}d},\tfrac{\sqrt{n}}{(\log(Tn/d))^{11}}\\}$.

It will be of independent interests to see whether one can find a clique
subdivision of order linear in the average degree whenever the host expander
is slightly sparser than the extremal construction (i.e. $d\leq
n^{1/2-o(1)}$). This is partially confirmed as follows.

######  Lemma 3.4.

Suppose $\tfrac{1}{d}\ll c\ll\varepsilon<\tfrac{1}{100}$ and
$d\leq\sqrt[3]{\tfrac{n}{\log^{100}n}}$. If an $n$-vertex
$(\varepsilon,\varepsilon d)$-expander $G$ has average degree at least
$\tfrac{d}{2}$ and minimum degree $\delta(G)\geq\tfrac{d}{4}$, then $G$
contains a $K_{cd}$-subdivision.

Lemma 3.4 actually strengthens a result in [13] where $d\leq\exp(\log^{1/6}n)$
(see Lemma A.1) is proved, and its proof strategy essentially follows from
that of Lemma 3.1. We will add its proof in Appendix A for completeness.

With the four lemmas, we are now ready to prove Theorem 1.4.

###### Proof of Theorem 1.4.

We choose $\beta=\sqrt{4\alpha}\leq\tfrac{1}{150}$ and $\tfrac{1}{d}\ll
c\ll\tfrac{1}{T}\ll\beta,\varepsilon$, and let $G$ be a graph with $d(G)=d$.
Let

$t=\min\Big{\\{}d,\sqrt{\tfrac{C_{\alpha}(G)}{\log C_{\alpha}(G)}}\Big{\\}}.$

By Lemma 2.2, we have an $(\varepsilon,\varepsilon d)$-robust-expander
$G_{0}\subseteq G$ with
$d(G_{0})\geq\tfrac{d}{2},\delta(G_{0})\geq\tfrac{d}{4}$ and let

$n=|V(G_{0})|,\leavevmode\nobreak\ m=\log^{4}\tfrac{n}{\varepsilon d}.$

Throughout the proof we assume that $\varepsilon d<\tfrac{n}{T}$, otherwise by
a result of Fox and Sudakov [8], we can get a $K_{c\sqrt{n}}$-subdivision, as
desired. If $d\leq\sqrt[3]{\tfrac{n}{\log^{100}n}}$ or
$d\geq\sqrt[3]{\tfrac{n}{\log^{100}n}}\geq\log^{1000}n$ and
$\tfrac{C_{\beta}(G_{0})}{\log C_{\beta}(G_{0})}\geq d^{2}m^{100}$, then using
Lemma 3.4, or Lemma 3.1 with $k=\varepsilon d$, respectively, we obtain that
$G_{0}$ (also $G$) contains a $K_{cd}$-subdivision as desired. It remains to
consider the case $C_{\beta}(G_{0})<d^{2}m^{100}\log
C_{\beta}(G_{0})<d^{2}\log^{500}n$ and $d>\sqrt[3]{\tfrac{n}{\log^{100}n}}$,
which implies

$\displaystyle
d>\max\Big{\\{}\sqrt[3]{\tfrac{n}{\log^{100}n}},\sqrt{\tfrac{C_{\beta}(G_{0})}{\log^{500}n}}\Big{\\}}.$
(1)

Let $H\subseteq G_{0}$ be a minimum $\beta$-crux of $G_{0}$. Then
$v(H)=C_{\beta}(G_{0})$ and $d(H)\geq\beta d(G_{0})\geq\tfrac{1}{2}\beta d$.
Taking
$k=\min\\{\tfrac{d^{2}}{\log^{2500}d},\tfrac{v(H)}{\log^{2500}v(H)}\\}$, we
apply Lemma 2.2 to obtain an $(\varepsilon,k)$-robust-expander $H^{*}\subseteq
H$ with $d(H^{*})\geq\tfrac{1}{4}\beta d$ and
$\delta(H^{*})\geq\tfrac{1}{2}d(H^{*})\geq\tfrac{1}{8}\beta d$. By (1) it
follows that

$\log v(H)\geq\log d(H^{*})\overset{\eqref{eq1}}{>}\tfrac{1}{4}\log
n\leavevmode\nobreak\ \leavevmode\nobreak\ \text{and thus}\leavevmode\nobreak\
\leavevmode\nobreak\
d\overset{\eqref{eq1}}{>}\sqrt{\tfrac{v(H)}{\log^{500}n}}\geq\sqrt{\tfrac{v(H)}{\log^{2500}v(H)}}.$

If $C_{\beta}(H^{*})\geq k\log k$, then applying Lemma 3.2 on $H^{*}$ with
$n=v(H)$ and $p=2500$, we obtain a $K_{ct_{\ref{dense2}}}$-subdivision in
$H^{*}$ (also in $G$) with

$t_{\ref{dense2}}=\min\Big{\\{}d,\sqrt{\tfrac{C_{\beta}(H^{*})}{\log
C_{\beta}(H^{*})}}\Big{\\}}\geq\min\Big{\\{}d,\sqrt{\tfrac{C_{\alpha}(G)}{\log
C_{\alpha}(G)}}\Big{\\}}=t,$

where the inequality follows since $\beta=\sqrt{4\alpha}$ and thus

$C_{\beta}(H^{*})=\min\\{|H^{\prime}|:H^{\prime}\subseteq
H^{*},d(H^{\prime})\geq\beta d(H^{*})\geq\tfrac{1}{4}\beta^{2}d=\alpha
d\\}\geq C_{\alpha}(G).$

Otherwise, we have $C_{\beta}(H^{*})<k\log
k\leq\min\\{\tfrac{d^{2}}{\log^{1500}d},\tfrac{v(H)}{\log^{1500}v(H)}\\}\leq\min\\{\tfrac{d^{2}}{\log^{1500}d},\tfrac{n}{\log^{1500}n}\\}$.
This together with the fact $C_{\beta}(H^{*})\geq C_{\alpha}(G)$ implies that

$t=\min\Big{\\{}d,\sqrt{\tfrac{C_{\alpha}(G)}{\log
C_{\alpha}(G)}}\Big{\\}}=\sqrt{\tfrac{C_{\alpha}(G)}{\log
C_{\alpha}(G)}}\leq\sqrt{k}\leq\min\Big{\\{}\tfrac{d}{\log^{60}d},\tfrac{\sqrt{n}}{\log^{11}n}\Big{\\}}\leq
t_{\ref{lem_dense}}.$

Now we recap the assumption
$d>\sqrt[3]{\tfrac{n}{\log^{100}n}}>\exp(\log^{1/6}n)$ and make use of Lemma
3.3 on $G_{0}$ to obtain a $K_{ct}$-subdivision as desired. ∎

###  3.1 Proof Sketch of Lemmas

We will give a unified approach for Lemma 3.1 and 3.2 via Lemma 3.5, where the
majority of the technical constructions are stated in a combined way.

######  Lemma 3.5.

Suppose
$\tfrac{1}{n},\tfrac{1}{d}\ll\tfrac{1}{T},c\ll\beta,\varepsilon\leq\tfrac{1}{150}$
and $x,k\in\mathbb{N}$ with $x>13,k\leq\tfrac{n}{T},\ d\geq\log^{25x}n$. Let
$G$ be an $n$-vertex $(\varepsilon,k)$-robust-expander with $d(G)\geq d$,
$\delta(G)\geq\tfrac{d}{2}$ and given $t$ satisfying

$t=\min\left\\{d,\sqrt{\tfrac{C_{\beta}(G)}{\log C_{\beta}(G)}}\right\\},\
k\leq t^{2}m,\ t^{2}m^{4x}\leq\tfrac{1}{3}C_{\beta}(G),\leavevmode\nobreak\
\leavevmode\nobreak\ \text{where}\leavevmode\nobreak\ \leavevmode\nobreak\
m=\log^{4}\tfrac{n}{k}.$

Then $G$ contains a $K_{ct}$-subdivision.

As mentioned in the introduction, the main tasks are to

  1. (A1)

build $\Omega(t)$ webs that have disjoint interiors, and then

  2. (A2)

connect theirs exteriors (each of size essentially $t^{2}m^{O(1)}$ via
pairwise disjoint short paths whilst avoiding the vicinity of core vertices.

For (A1), previous approaches for building units or webs usually proceed by
linking many disjoint stars and then use averaging arguments, which can only
produce web structures with sublinear in $d(G)$ many branches (e.g. in [13],
while in [24], they can obtain a linear bound under the $C_{4}$-free
condition). This much weaker bound only leads them to build a clique
subdivision of order sublinear in $d(G)$ (this is obviously not tight when
$t=d(G)$). To overcome this, the first insight in this paper is a new
perspective we bring to the $\alpha$-crux number.

$(D,\mu)$-dense. We use a notion of $(D,\mu)$-dense as follows.

######  Definition 3.6.

[15] A graph $G$ is called _$(D,\mu)$ -dense_ if for every $W\subseteq V(G)$
with $|W|<D$, we have $d(G-W)\geq\mu d(G)$.

Technically, we employ the following lemma, which allows us to iteratively
build a web which avoids the vicinity of previous core vertices of webs built
so far.

######  Lemma 3.7.

Let $G$ be a graph with $\delta(G)\geq\tfrac{1}{2}d(G)$. Then

  1. (B1)

for any $0<\alpha\leq\tfrac{1}{5}$, $G$ is
$(\tfrac{C_{\alpha}(G)}{2},\tfrac{1-3\alpha}{4})$-dense.

  2. (B2)

for any $K,\alpha>0$ with $\alpha\leq\tfrac{1}{2K+2}$, every $X\subseteq V(G)$
with $|X|\leq\tfrac{C_{\alpha}(G)}{K+1}$ satisfies $N_{G}(X)\geq K|X|$.

For now, an immediate consequence of (B1) is that it allows us to iteratively
find large stars with up to $\tfrac{C_{\alpha}(G)}{2}$ vertices in total (even
additionally avoiding the interiors of previous webs). But this is still far
from clear whether we can build a web as promised in (A1). Here we bring
another new perspective to the $\alpha$-crux number. Instead of averaging
arguments, a crucial ingredient in our construction is that we can robustly
grow a ball around a fixed vertex (up to the size roughly
$\tfrac{C_{\alpha}(G)}{3}$, see Lemma 3.9) so as to further connect up to many
disjoint stars by disjoint paths. This indicates why our main proof is divided
into three cases by distinguishing the value of the $\alpha$-crux number with
the density $d(G)$. Also, to make this happen, we need the following notion
formulated in [24] to iteratively connect from a fixed vertex via disjoint
paths.

######  Definition 3.8 ([24]).

Given a graph $G$ and $W\subseteq V(G)$, we say that paths
$P_{1},\ldots,P_{t}$, each starting with a vertex $v$ and contained in the
vertex set $W$, are _consecutive shortest paths_ from $v$ in $W$ if for each
$i$ $(1\leq i\leq t)$, the path $P_{i}$ is a shortest path between its
endpoints in the set $W\setminus(\bigcup_{j<i}V(P_{j}))\cup\\{v\\}$.

The following lemma allows us to robustly grow a ball.

######  Lemma 3.9.

Suppose $\tfrac{1}{d}\ll c,\beta\leq\tfrac{1}{5}$ and let $G$ be a graph with
$\delta(G)\geq\tfrac{d(G)}{2}\geq 5cd$. Then for any integer
$D\leq\tfrac{1}{3}C_{\beta}(G)$, there exists a positive integer
$\ell\leq\log_{2}(\tfrac{2D}{\delta(G)})$ such that given any vertex $v$ and
consecutive shortest paths $P_{1},\dots,P_{t}$, $t\leq cd$, from $v$ in
$B_{G}^{\ell}(v)$, writing $U=\bigcup_{i\in t}V(P_{i})$, we have
$|B_{G-(U\backslash\\{v\\})}^{\ell}(v)|\geq D$.

However, building up to now, a subtle fact is that once we carry out building
a web by using Lemma 3.9 to expand from a fixed vertex, the resulting web
would witness $\Omega(t)$ consecutive shortest paths whose union has size
$\Omega(t\ell)$. Thus to make (A1) successful, in each iteration (at least for
the last few iterations), we need to avoid $\Omega(t^{2}\ell)$ vertices from
previous webs. Unfortunately, the space barrier tells that
$C_{\beta}(G)=\Omega(n)$ and $\ell=\Omega(\log n)$, and thus
$\Omega(t^{2}\ell)=\Omega(n)$. There are too many (up to $\Omega(n)$) internal
vertices to avoid just by applying the current connection tools such as Lemma
2.3. It seems that we need a stronger connectivity (than Lemma 2.3) for
building short paths, and this appears surprisingly difficult in sublinear
expanders.

Connecting through a random vertex set. To overcome this, we modify our
strategy for (A1) as follows: we first partition $V(G)=V_{1}\cup V_{2}$ by
including each vertex independently in $V_{i}$ uniformly at random. Then in
each iteration of construction, we

  1. (C1)

first apply Lemma 3.9 to robustly grow a ball $B$ (of size roughly
$\tfrac{C_{\alpha}(G)}{3}$) within $V_{1}$ which is disjoint from the
interiors of previous webs; and meanwhile build many disjoint units in
$V_{2}$;

  2. (C2)

then connect the ball up to many distinct units via pairwise disjoint short
paths through $V_{2}$ whilst avoiding the interiors of previous webs;
Meanwhile we find consecutive shortest paths so as to extend every connection
up to the core vertex of the ball.

Here a path through $V_{2}$ is one whose internal vertices all lie in $V_{2}$.
To carry out (C1), our new perspective on the crux number is critical. Note
that the union of all consecutive shortest paths within previous webs built as
in (C2) has size at most $t^{2}\ell<C_{\beta}(G)/2$. By iteratively applying
Lemma 3.7 (B1) on $G[V_{1}]$ (minus the interiors of previous webs), we will
find a subgraph with average degree linear in $d(G)$. To ensure a ball of the
desired size in the subgraph, we recap the definition of the $\alpha$-crux
number and use the following easy fact:

> Given a graph $G$ and a subgraph $H\subseteq G$ with
> $d(H)\geq\tfrac{1}{k}d(G)$ for some $k\in\mathbb{N}$, we obtain that
> $C_{k\alpha}(H)\geq C_{\alpha}(G)$ for any $0<\alpha<\tfrac{1}{k}$.

Thus such a ball always exists from Lemma 3.9. To build disjoint units in
$V_{2}$, again by using Lemma 3.7 (B1) on $G[V_{2}]$, our approach follows the
usual averaging arguments as in [24].

Note that each connection in (C2) automatically avoids
$O(t^{2}\ell)=O(C_{\beta}(G))$ internal vertices from consecutive shortest
paths of previous webs. This turns out to be very efficient as all other
internal vertices sum up to a size $t^{2}m^{O(1)}=o(C_{\beta}(G))$ (valid in
the proof of Lemma 3.5) that is easy to avoid. To make (C2) successful, it is
desired that $G[V_{2}]$ is also a sublinear expander and thus we can apply
Lemma 2.3. However it is surprisingly difficult to verify whether with
positive probability, $G[V_{2}]$ is a sublinear expander as in Definition 2.1
(see [5] for a detailed explanation why the union bound is inefficient). To
get around this, we adopt an idea of Bucić and Montgomery [5] where they bring
many new perspectives on robust sublinear expansion in Definition 2.1 with
useful applications in decompositions of expanders into small ones. To be more
precise, they show that very likely a random set $V\subseteq V(G)$ inherits a
slightly weak expansion property saying that one can expand from any
reasonable-sized vertex set (not necessarily lie inside $V$) in a few more
steps to reach up to $\tfrac{|V|}{2}$ vertices within $V$, even after
additionally deleting superlinearly many edges.

To aid our proof, we develop a random variant of Lemma 2.3, where we also
allow the deletion of sublinearly many vertices.

######  Lemma 3.10 (Robust Connecting Lemma).

Suppose $\tfrac{1}{n},\tfrac{1}{d}\ll\tfrac{1}{k}\ll\varepsilon<1$ and $G$ is
an $n$-vertex $(\varepsilon,k)$-robust-expander with average degree
$d\geq\log^{100}n$, and $V\subseteq V(G)$ is a random subset chosen by
including each vertex independently at random with probability $\tfrac{1}{2}$.
Let $m=\log^{4}\tfrac{n}{k}$. Then, with probability $1-o(\tfrac{1}{n})$, for
any two vertex sets $X_{1},X_{2}$ each of size at least $x\geq km^{9}$, and a
vertex set $W$ of size at most $\tfrac{x}{m^{11}}$, there exists a path
through $V$ of length at most $2m^{2}$ between $X_{1}$ and $X_{2}$, which is
vertex disjoint from $W$.

To sum up, this will allow us to build webs as in step (A1) by recursively
carrying out (C1)-(C2). Now with the aid of Lemma 3.10, the final connections
in (A2) will be easy by linking their exteriors via disjoint paths through
$V_{2}$.

To end this subsection, we give short proofs of Lemma 3.7 and Lemma 3.9, while
the proof of Lemma 3.10 closely follows the strategy in [5] and thus deferred
to Appendix B.

###### Proof of Lemma 3.7.

For part (B1), let $G$ be a graph with $d(G):=d$ and write
$k=\lceil\tfrac{C_{\alpha}(G)}{2}\rceil$. Fix any subset $W\subseteq V(G)$
with $|W|=k-1$. Then $|V(G)\setminus W|>k-1$ and let $n=|V(G)\setminus W|$. We
arbitrarily take a subset $Y\subseteq V(G)\setminus W$ of size $k-1$ and let
$Z=V(G)\setminus(W\cup Y)$. Note that $|X\cup Y|<C_{\alpha}(G)$, and thus by
the definition of $C_{\alpha}(G)$ we have $e(X\cup Y)<(k-1)\alpha d$ and
$e(Y)<\tfrac{1}{2}(k-1)\alpha d$. Then

$e(Y,Z)=\sum_{v\in
Y}d(v)-2e(Y)-e(X,Y)\geq\tfrac{1}{2}(k-1)d-\tfrac{3}{2}(k-1)\alpha
d=(k-1)\tfrac{1-3\alpha}{2}d\geq(k-1)\alpha d.$

This gives $|Z|\geq k$ as otherwise we have $|Y\cup Z|\leq
2(k-1)<C_{\alpha}(G)$ whilst $d(G[Y\cup Z])\geq\alpha d$, a contradiction.
Thus $n\geq 2k-1$ and by double counting the sums of $e(Y,Z)$ over all choices
of $Y\subseteq V(G)-W$, we have

$\tbinom{n}{k-1}(k-1)\tfrac{1-3\alpha}{2}d\leq\sum_{|Y|=k-1}e(Y,Z)\leq
2e(G-W)\tbinom{n}{k-2},$

which implies
$d(G-W)=\tfrac{2e(G-W)}{n}\geq\tfrac{n-k+2}{n}\cdot\tfrac{1-3\alpha}{2}\cdot
d\geq\tfrac{1-3\alpha}{4}d$ as $n\geq 2k-1$.

For part (B2), take a vertex set $X\subseteq V(G)$ with
$|X|\leq\tfrac{C_{\alpha}(G)}{K+1}$. Suppose to the contrary that
$N_{G}(X)<K|X|$, and we consider the subgraph $H:=G[X\cup N_{G}(X)]$. Thus

$d(H)\geq\tfrac{\delta(G)|X|}{|X\cup N_{G}(X)|}>\tfrac{1}{2K+2}d(G)\geq\alpha
d(G).$

However,

$v(H)<|X|+K|X|\leq C_{\alpha}(G),$

which contradicts to the definition of $C_{\alpha}(G)$. ∎

###### Proof of Lemma 3.9.

Given $\beta\leq\tfrac{1}{5}$, we choose $\tfrac{1}{d}\ll c,\beta$ and let $G$
be with $\delta(G)\geq\tfrac{d(G)}{2}\geq 5cd$, and $P_{1},\ldots,P_{t}$ be
consecutive shortest paths from $v$ in $V(G)$. Let
$U=\bigcup_{i\in[t]}V(P_{i})$ and $F=G-(U\backslash\\{v\\})$. Recall that
$D\leq\tfrac{C_{\beta}(G)}{3}$. We shall show by induction on $p\geq 1$ that,
if $|B_{F}^{p}(v)|\leq\tfrac{C_{\beta}(G)}{3}$, then

$|N_{F}(B_{F}^{p}(v))|\geq|B_{F}^{p}(v)|.$ (2)

Also we will show that $|B_{F}^{1}(v)|\geq\tfrac{4}{5}\delta(G)$, which
together with this inductive statement will prove the lemma. Actually, we may
take the conclusion for granted, and thus if
$|B_{F}^{p}(v)|\leq\tfrac{C_{\beta}(G)}{3}$, then we have

$|B_{F}^{p+1}(v)|=|B_{F}^{p}(v)|+|N_{F}(B_{F}^{p}(v))|\geq 2|B_{F}^{p}(v)|.$

Then there exists $\ell\leq\log_{2}(\tfrac{2D}{\delta(G)})$ for which
$|B_{F}^{\ell}(v)|\geq 2^{\ell}|B_{F}^{1}(v)|\geq
2^{\ell}\cdot\tfrac{4}{5}\delta(G)\geq D$ as desired.

Thus, we only need to prove the inductive statement and
$|B_{F}^{1}(v)|\geq\tfrac{4}{5}\delta(G)$. As the paths $P_{i}$ are also
consecutive shortest paths from $v$ in $B^{\ell}_{G}(v)$, only the first $p+2$
vertices of each path $P_{i}$, including $v$, can belong to
$N_{G}(B_{G-\cup_{j<i}(V(P_{j})\backslash\\{v\\})}^{p}(v))$. Hence, only the
first $p+2$ vertices of each of the path $P_{i}$, including the vertex $v$ can
belong to $N_{G}(B_{F}^{p}(v))$. On the other hand, as we have at most $cd$
paths $P_{i}$, $|N_{G}(B_{F}^{p}(v))\cap U|\leq(p+1)cd$, so that

$|N_{G-F}(B_{F}^{p}(v))|\leq(p+1)cd.$ (3)

In particular, when $p=0$, we have

$|N_{F}(B_{F}^{0}(v))|=|N_{F}(v)|\geq d(v)-cd\geq\tfrac{4}{5}\delta(G).$ (4)

Hence, $|B_{F}^{1}(v)|\geq\tfrac{4}{5}\delta(G)\geq 4cd$. Next we aim to prove
(2). When $p\geq 1$. Suppose that (2) holds for all $p^{\prime}$ with $0\leq
p^{\prime}<p$. By the assumption $|B_{F}^{p}(v)|\leq\tfrac{C_{\beta}(G)}{3}$,
Proposition 3.7 (B2) applied with $K=3/2$ and $\alpha=\beta$, implies that
$|N_{G}(B_{F}^{p}(v))|\geq\tfrac{3}{2}|B_{F}^{p}(v)|$. Now by (3) and the fact
that

$|N_{G}(B_{F}^{p}(v))|=|N_{G-F}(B_{F}^{p}(v))|+|N_{F}(B_{F}^{p}(v))|,$

it suffices to prove that

$|B_{F}^{p}(v)|\geq 2(p+1)cd.$ (5)

By the induction hypothesis, we have
$|B_{F}^{p^{\prime}}(v)|=|B_{F}^{p^{\prime}-1}(v)|+|N_{F}(B_{F}^{p^{\prime}-1}(v))|\geq
2|B_{F}^{p^{\prime}-1}(v)|$ for every $1\leq p^{\prime}\leq p$ and thus
$|B_{F}^{p}(v)|\geq 2^{p-1}|B_{F}^{1}(v)|\geq 2^{p-1}4cd\geq 2(p+1)cd$,
finishing the proof. ∎

###  3.2 Finish up: proofs of Lemmas 3.1 and 3.2

###### Proof of Lemma 3.1.

We choose
$\tfrac{1}{n},\tfrac{1}{d}\ll\tfrac{1}{T},c\ll\beta,\varepsilon\leq\tfrac{1}{150}$
and let $G$ be an $n$-vertex $(\varepsilon,k)$-robust-expander with
$\delta(G)\geq\tfrac{d(G)}{2}\geq\tfrac{\beta d}{16}$ and
$k\leq\min\\{d^{2},\tfrac{n}{T}\\}$. Since
$d^{2}m^{100}\leq\tfrac{C_{\beta}(G)}{\log C_{\beta}(G)}$ and
$\beta\leq\tfrac{1}{150}$, taking $t=\min\\{\tfrac{\beta
d}{8},\sqrt{\tfrac{C_{\beta}(G)}{\log C_{\beta}(G)}}\\}=\tfrac{\beta d}{8}$,
we have

$k\leq d^{2}<t^{2}m,\ \
t^{2}m^{100}\leq\tfrac{\beta^{2}}{64}\cdot\tfrac{C_{\beta}(G)}{\log
C_{\beta}(G)}\leq\tfrac{1}{3}C_{\beta}(G),$

as $\tfrac{n}{k}$ and also $m$ are sufficiently large. Applying Lemma 3.5 with
$(k,t,d,x)=(k,\tfrac{\beta d}{8},\tfrac{\beta d}{8},25)$, we can obtain that
$G$ contains a $K_{cd}$222Actually $c$ can arrive $\tfrac{1}{1200}$ when we
take $\beta=\tfrac{1}{150}$.-subdivision. ∎

###### Proof of Lemma 3.2.

We choose $\tfrac{1}{n},\tfrac{1}{d}\ll
c\ll\beta,\varepsilon\leq\tfrac{1}{150}$ and let $G$ be an
$(\varepsilon,k)$-robust-expander with
$\delta(G)\geq\tfrac{1}{2}d(G)\geq\tfrac{1}{16}\beta d$ and

$d\geq\sqrt{\tfrac{n}{\log^{p}n}},\leavevmode\nobreak\ C_{\beta}(G)\geq k\log
k,\leavevmode\nobreak\
k=\min\\{\tfrac{d^{2}}{\log^{p}d},\tfrac{n}{\log^{p}n}\\},\leavevmode\nobreak\
\text{and let}\leavevmode\nobreak\ \leavevmode\nobreak\
m=\log^{4}\tfrac{n}{k}.$

Note that by the assumption $d\geq\sqrt{\tfrac{n}{\log^{p}n}}$, we obtain that

$k=\min\\{\tfrac{d^{2}}{\log^{p}d},\tfrac{n}{\log^{p}n}\\}>\tfrac{n}{\log^{2p}n}\leavevmode\nobreak\
\leavevmode\nobreak\ \text{and thus}\leavevmode\nobreak\ \leavevmode\nobreak\
m\leq(\log\log n)^{5}.$

Let $t=\min\\{\tfrac{\beta d}{8},\sqrt{\tfrac{C_{\beta}(G)}{\log
C_{\beta}(G)}}\\}$. We shall find a $K_{ct}$-subdivision by Lemma 3.5. From
above, we want to claim that

$k\leq t^{2}m,\ \ t^{2}m^{100}\leq\tfrac{C_{\beta}(G)}{3}.$ (6)

Indeed, as $C_{\beta}(G)\geq k\log k$, we have

$t^{2}m=\min\\{\tfrac{\beta^{2}d^{2}}{64},\tfrac{C_{\beta}(G)}{\log
C_{\beta}(G)}\\}m\geq\min\\{\tfrac{\beta^{2}d^{2}}{64},\tfrac{k\log
k}{\log(k\log k)}\\}m\geq k.$

On the other hand, as $k>\tfrac{n}{\log^{2p}n}$ and $m<(\log\log n)^{5}$, we
have

$\log C_{\beta}(G)\geq\log(k\log k)>\log(\tfrac{n}{\log^{2p}n})>3m^{100}.$

Hence,

$t^{2}m^{100}\leq\tfrac{C_{\beta}(G)}{\log
C_{\beta}(G)}m^{100}\leq\tfrac{C_{\beta}(G)}{3}.$

Consequently, (6) holds. Finally, applying Lemma 3.5 with
$(k,t,d,x)=(k,t,\tfrac{\beta d}{8},25)$, we obtain that $G$ contains a
$K_{ct}$-subdivision. ∎

##  4 Proof of Lemma 3.5

###### Proof of Lemma 3.5.

Choose
$\tfrac{1}{n},\tfrac{1}{d}\ll\tfrac{1}{T},c\ll\beta,\varepsilon\leq\tfrac{1}{150}$
and $x,k\in\mathbb{N}$ with $x>13,k\leq\tfrac{n}{T},d\geq\log^{25x}n$. Let $G$
be an $n$-vertex $(\varepsilon,k)$-robust-expander with $d(G)\geq d$,
$\delta(G)\geq\tfrac{d}{2}$ and given $t\in\mathbb{N}$ satisfying

$t=\min\left\\{d,\sqrt{\tfrac{C_{\beta}(G)}{\log C_{\beta}(G)}}\right\\},\
k\leq t^{2}m,\ t^{2}m^{4x}\leq\tfrac{1}{3}C_{\beta}(G),\leavevmode\nobreak\
\leavevmode\nobreak\ \text{where}\leavevmode\nobreak\ \leavevmode\nobreak\
m=\log^{4}\tfrac{n}{k}.$

Since $C_{\beta}(G)\geq\beta d$, we get that $t\geq m^{3x}$. To build a
$K_{ct}$-subdivision, we first partition $V(G)=V_{1}\cup V_{2}$, where each
vertex is independently included in $V_{i}$, $i\in[2]$, uniformly at random.
It follows from standard concentration methods that for each $i\in[2]$,
$G_{i}:=G[V_{i}]$ has $d(G_{i})\geq\tfrac{d}{3}$.

Phase $1$. Building $t$ webs that have disjoint interiors.

Let $\ell=\log_{2}(\tfrac{C_{\beta}(G)}{d})$. We need the following main
result.

######  Claim 4.1.

The graph $G$ contains $t$ distinct
$(4ct,\ell+m^{3},2m^{x},\tfrac{t}{80},m^{3})$-webs
$\mathcal{W}_{1},\ldots,\mathcal{W}_{t}$ such that they have disjoint
interiors and each $\mathcal{W}_{i}$ satisfies
$|\mathsf{Int}(\mathcal{W}_{i})\cap V_{1}|\leq 4ct\ell$ and
$|\mathsf{Int}(\mathcal{W}_{i})\cap V_{2}|\leq 10ctm^{x+3}$.

###### Proof of Claim 4.1.

As sketched in Section 3.1, we shall proceed by first growing a ball inside
$V_{1}$ and meanwhile building many disjoint units in $V_{2}$, whilst avoiding
the interiors of previous webs. Suppose we have built
$\mathcal{W}_{1},\ldots,\mathcal{W}_{t^{\prime}}$ as desired for some $0\leq
t^{\prime}<t$, and let

$W_{i}=\cup_{j\in[t^{\prime}]}\mathsf{Int}(\mathcal{W}_{j})\cap
V_{i}\leavevmode\nobreak\ \text{for}\leavevmode\nobreak\ i\in[2].$

Then $|W_{1}|\leq 4ct^{2}\ell$ and $|W_{2}|\leq t^{2}m^{2x}$. We first build
many disjoint units in $V_{2}$ in the following, whose proof is postponed
later.

######  Subclaim 4.2 (build units).

The graph $G_{2}-W_{2}$ contains vertex-disjoint
$(2m^{x},\tfrac{t}{40},m^{3})$-units $F_{1},\ldots,F_{2tm^{x+12}}$.

Denote by $f_{i}$ the core vertex of each $F_{i}$ as above. Let

$W_{3}=\bigcup_{i\in[2tm^{x+12}]}V(F_{i})\leavevmode\nobreak\ \text{
and}\leavevmode\nobreak\ W_{4}=\bigcup_{i\in[2tm^{x+12}]}\mathsf{Int}(F_{i}).$

Then we have $|W_{4}|\leq 5tm^{2x+15}$,
$|W_{3}|\leq\tfrac{t^{2}m^{2x+15}}{4}$.

Next, we shall grow a ball in $V_{1}-W_{1}$. Observe that
$d(G_{1})\geq\tfrac{1}{3}d$ and thus one can easily choose a subgraph
$H\subseteq G_{1}$ such that
$\delta(H)\geq\tfrac{1}{2}d(H)\geq\tfrac{1}{2}d(G_{1})$. Then by definition
$C_{3\beta}(H)\geq C_{\beta}(G)$. Note that

$|W_{1}|\leq 4ct^{2}\ell<\tfrac{C_{\beta}(G)}{2}\leavevmode\nobreak\ \text{
as}\leavevmode\nobreak\ \ell<\log C_{\beta}(G)\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ t\leq\sqrt{\tfrac{C_{\beta}(G)}{\log
C_{\beta}(G)}}.$

Applying Lemma 3.7 (B1) to $H$, we get that
$d(H-W_{1})\geq\tfrac{d(H)}{10}\geq\tfrac{d}{30}$. Further choose a subgraph
$H^{\prime}\subseteq H-W_{1}$ such that
$\delta(H^{\prime})\geq\tfrac{1}{2}d(H^{\prime})\geq\tfrac{1}{2}d(H-W_{1})\geq\tfrac{d}{60}$
and pick a vertex $v\in V(H^{\prime})$ of degree at least $\tfrac{d}{30}$.

######  Subclaim 4.3.

There is a $(4ct,\ell+m^{3},m^{x},\tfrac{t}{80},m^{3})$-web centered at $v$,
denoted $\mathcal{W}_{t^{\prime}+1}$, which is internally disjoint from
$W_{1}\cup W_{2}$, and $|\mathsf{Int}(\mathcal{W}_{t^{\prime}+1})\cap
V_{1}|\leq 4ct\ell$, $|\mathsf{Int}(\mathcal{W}_{t^{\prime}+1})\cap V_{2}|\leq
10ctm^{x+3}$.

###### Proof.

To build the desired $(4ct,\ell+m^{3},m^{x},\tfrac{t}{80},m^{3})$-web, we
shall proceed by finding $4ct$ internally vertex-disjoint paths
$Q_{1},\ldots,Q_{4ct}$ in $G$ from $v$ satisfying the following rules.

  1. (D1)

Each path $Q_{i}$ is a unique $v,f_{x_{i}}$-path, where
$x_{i}\in[2tm^{x+12}]$, and furthermore $|V(Q_{i})\cap
V_{1}|\leq\ell,|V(Q_{i})\cap V_{2}|\leq m^{3}$.

  2. (D2)

Each path does not contain any vertex in $W_{2}\cup W_{4}$ as an internal
vertex.

  3. (D3)

The sequence of subpaths $Q_{i}[B^{\ell}_{H^{\prime}}(v)]$ $(i\in[4ct])$ form
consecutive shortest paths from $v$ in $B^{\ell}_{H^{\prime}}(v)$.

Assume that we have iteratively obtained a collection of shortest paths
$\mathcal{Q}=\\{Q_{1},\ldots,Q_{s}\\}$ $(0\leq s<4ct)$ as in (D1)-(D3). Note
that (D3) gives $s$ consecutive shortest paths $P_{1},\ldots,P_{s}$ from $v$
in $B^{\ell}_{H^{\prime}}(v)$, where $P_{i}=Q_{i}[B^{\ell}_{H^{\prime}}(v)]$
and write $\mathcal{P}=\\{P_{1},\ldots,P_{s}\\}$. Note that
$C_{30\beta}(H^{\prime})\geq C_{\beta}(G)$. Applying Lemma 3.9 to $H^{\prime}$
with $D=\tfrac{C_{\beta}(G)}{3}$ , we get

$|B^{\ell}_{H^{\prime}-\mathsf{Int}(\mathcal{Q})}(v)|=|B_{H^{\prime}-\mathsf{Int}(\mathcal{P})}^{\ell}(v)|\geq\tfrac{C_{\beta}(G)}{3}>t^{2}m^{4x-1}.$

We call a unit $F_{i}$ available if its core vertex is not used as an endpoint
of a path in $\mathcal{Q}$. Let $U^{\prime}$ be the leaves of all pendent
stars in available units. Then we have

$|U^{\prime}|\geq
2m^{x}\cdot\tfrac{t}{40}(2tm^{x+12}-4ct)>\tfrac{t^{2}m^{2x+12}}{20}.$

Note that

$|W_{2}|+|W_{4}|+|V(\mathcal{Q})\cap V_{2}|\leq
t^{2}m^{2x}+5tm^{2x+15}+4ctm^{3}<2t^{2}m^{2x}.$

Applying Lemma 3.10 on $G$ with
$V_{2},B_{H^{\prime}-\mathsf{Int}(\mathcal{Q})}^{\ell}(v)$, $U^{\prime}$,
$W_{4}\cup W\cup(V(\mathcal{Q})\cap V_{2})$ playing the roles of
$V,X_{1},X_{2},W$, respectively, we can find a shortest path through $V_{2}$
of length at most $m^{3}$, say $Q$, joining a vertex $w$ from
$B_{H^{\prime}-\mathsf{Int}(\mathcal{Q})}^{\ell}(v)$ to a leaf
$u_{j}\in\mathsf{Ext}(F_{j})$ for some available unit $F_{j}$. One can easily
find a $v,w$-path within $B^{\ell}_{H^{\prime}-\mathsf{Int}(\mathcal{P})}(v)$,
denoted as $P_{s+1}$, and a $u_{j},f_{j}$-path inside the unit $F_{j}$,
denoted as $R_{s+1}$. Let $Q_{s+1}=P_{s+1}QR_{s+1}$. Then the paths
$Q_{1},\ldots,Q_{s+1}$ satisfy (D1)-(D3). Repeating this for
$s=0,1,\ldots,4ct$, yields $4ct$ paths $Q_{1},\ldots,Q_{4ct}$ as desired.

For every $i\in[2tm^{x+12}]$, we say a pendent star in $F_{i}$ is _overused_
if at least $\tfrac{t}{80}$ (half of) leaves are used in $V(\mathcal{Q})$ and
a unit is _bad_ if at least $m^{x}$ pendent stars are overused. Then there are
at most $\tfrac{4ctm^{3}}{t/80}=320cm^{3}<m^{x}$ overused pendent stars, and
therefore there is no bad unit. Then removing from every unit the second-level
branches each attached with overused pendant stars and combining corresponding
paths $Q_{i}$ yield a $(4ct,\ell+m^{3},m^{x},\tfrac{t}{80},m^{3})$-web as
desired. ∎

Up to now, the proof of Claim 4.1 is completed. ∎

Phase $2$. Building a $K_{ct}$-subdivision: linking webs via paths through
$V_{2}$.

Let $\mathcal{W}_{1},\ldots,\mathcal{W}_{2ct}$ be a subfamily of internally
vertex-disjoint $(4ct,\ell+m^{3},m^{x},$ $\tfrac{t}{80},m^{3})$-webs as in
Claim 4.1 and let $W=\bigcup_{i\in[2ct]}\mathsf{Ctr}(\mathcal{W}_{i})\cap
V_{2}$. Then $|W|\leq 8c^{2}t^{2}m^{3}$. We shall inductively construct a
$K_{ct}$-subdivision as follows. Let $\mathcal{P}$ be a maximum collection of
vertex-disjoint paths through $V_{2}$ of length at most $4m^{3}$ under the
following rules.

  1. (E1)

Each path $P_{ij}\in\mathcal{P}$ connects a pair of core vertices of unit from
different webs $\mathcal{W}_{i}$ and $\mathcal{W}_{j}$. We say the
corresponding units are then occupied.

  2. (E2)

For each pair of webs, there is at most one path in $\mathcal{P}$ between the
core vertices from their respective units. All paths in $\mathcal{P}$ are
internally disjoint from $W$.

It is easy to see that the paths $P_{ij}$ can be extended using branches
within $\mathcal{W}_{i}$ and $\mathcal{W}_{j}$ to a path of length at most
$2\ell+8m^{3}$ joining the core vertices of those two webs. Based on (E2), at
most $4c^{2}t^{2}$ paths are built and thus $|V(\mathcal{P})|\leq
16c^{2}t^{2}m^{3}$.

  * •

For each second-level branch in a unit, if more than $\tfrac{t}{80}$ (half of)
leaves of the corresponding pendant star belong to $V(\mathcal{P})$ or a
vertex in the second-level branch belongs to $V(\mathcal{P})$, then we say the
second-level branch is used.

  * •

For each unit within a web, if more than $\tfrac{m^{x}}{2}$ second-level
branches are used, then we say the unit over-used.

  * •

If more than $ct$ units within the web are over-used, then the web is bad, and
otherwise it is good.

Note that all webs are internally vertex disjoint. As the paths in
$\mathcal{P}$ do not intersect the centers of webs, a web is bad only when
more than $ct$ units within the web are over-used, each such unit containing
at least $\tfrac{m^{x}}{2}$ vertices in $V(\mathcal{P})$. This implies that
each bad web contains at least $\tfrac{ctm^{x}}{2}$ vertices of
$V(\mathcal{P})$ in its interior. Hence, there are at most
$\tfrac{16c^{2}t^{2}m^{3}}{ctm^{x}/2}<ct$ bad webs. The following claim would
give a desired $K_{ct}$-subdivision by combining $ct$ good webs and the paths
in (E1).

######  Claim 4.4.

For every pair of good webs, there is a path in $\mathcal{P}$ between two core
vertices from their respective units.

###### Proof.

Without loss of generality, we may assume for a contradiction that
$\mathcal{W}_{1}$ and $\mathcal{W}_{2}$ are a pair of good units for which
there is no desired path in $\mathcal{P}$. If a web is good, then by
definition it has at least $ct$ units that are not occupied and not over-used,
namely, each such unit has at least $\tfrac{m^{x}}{2}$ second-level branches
attached with at least $\tfrac{t}{80}$ leaves. Therefore, the new web obtained
by deleting over-used units and all used second-level branches, still has an
exterior of at least $\tfrac{ct^{2}m^{x}}{320}$ vertices. Hence, since $|W\cup
V(\mathcal{P})|\leq t^{2}m^{3}$, by Lemma 3.10, we can connect the exteriors
of two new webs by a path of length at most $m^{3}$ whilst avoiding $W\cup
V(\mathcal{P})$. One can easily extend this path to a desired path as in (E1).
∎

∎

We now complement the proof of Subclaim 4.2 to end the section.

###### Proof of Subclaim 4.2.

If we have $F_{1},\ldots,F_{s}$ for some $0\leq s<2tm^{x+12}$, then the set
$W:=\bigcup_{i\in[s]}V(F_{i})$ has size at most
$2tm^{x+12}[2m^{x}(m^{3}+\tfrac{t}{20})]\leq\tfrac{t^{2}m^{2x+12}}{4}$. To
build one more unit, we first claim that $G_{2}-W_{2}-W$ contains vertex-
disjoint stars $S_{1},\cdots,S_{tm^{4x}}$ where each $S_{i}$ has exactly
$\tfrac{t}{30}$ leaves. Indeed, we choose $G_{2}^{\prime}\subseteq G_{2}$ such
that
$\delta(G_{2}^{\prime})\geq\tfrac{1}{2}d(G_{2}^{\prime})\geq\tfrac{1}{2}d(G_{2})$.
Then by definition we obtain $C_{3\beta}(G_{2}^{\prime})\geq C_{\beta}(G)$.
Let $S_{1},\cdots,S_{p}$ be a maximal collection of stars as required in
$G_{2}^{\prime}$ for some $0\leq p<tm^{4x}$. Then
$W^{\prime}:=\bigcup_{i\in[p]}V(S_{i})$ has size at most
$\tfrac{t^{2}m^{4x}}{10}$. Since $G_{2}^{\prime}$ is
$(\tfrac{C_{\beta}(G)}{2},\tfrac{1}{10})$-dense and $|W_{2}\cup W^{\prime}\cup
W|\leq t^{2}m^{2x}+\tfrac{t^{2}m^{4x}}{10}+\tfrac{t^{2}m^{2x+12}}{4}\leq
t^{2}m^{4x}<\tfrac{C_{\beta}(G)}{3}$, Lemma 3.7 (B1) implies that
$d(G_{2}^{\prime}-W_{2}-W^{\prime})\geq\tfrac{d(G^{\prime}_{2})}{10}\geq\tfrac{t}{30}$.
Thus we can take a star denoted as $S_{p+1}$ with $\tfrac{t}{30}$ leaves,
which is disjoint from $W^{\prime}$, contrary to the maximality of $p$.

We take disjoint stars (renaming if necessary) $S_{1},\cdots,S_{tm^{3x-1}}$,
$T_{1},\ldots,T_{4tm^{4x-1}}$ as above, with centers
$u_{1},\ldots,u_{tm^{3x-1}}$, $v_{1},\ldots,v_{4tm^{4x-1}}$, respectively. Let
$Z=\\{u_{1},\ldots,u_{tm^{3x-1}},v_{1},\ldots,v_{4tm^{4x-1}}\\}$. Let
$\mathcal{P}$ be a maximum collection of internally disjoint paths $P_{ij}$ in
$G_{2}-W-W_{2}$ satisfying the following rules.

  1. (F1)

Each path $P_{ij}$ in $\mathcal{P}$ is a unique $u_{i},v_{j}$-path of length
at most $m^{3}$.

  2. (F2)

Each $P_{ij}$ does not contain any vertex in $Z\cup W_{2}\cup W$ as an
internal vertex.

Now we claim that there is a center $u_{i}$ connected to at least $2m^{x}$
distinct centers $v_{j}$ via the paths in $\mathcal{P}$. Suppose to the
contrary that every $u_{i}$ is connected to less than $2m^{x}$ centers
$v_{j}$. Then $|\mathcal{P}|\leq 2tm^{4x-1}$ and $|V(\mathcal{P})|\leq
2tm^{4x-1}\cdot m^{3}\leq 2tm^{4x+2}$. Let

$U:=\bigcup_{i\in[tm^{3x-1}]}(S_{i}\backslash\\{u_{i}\\})\setminus
V(\mathcal{P}),$

and $V$ be the set of leaves of all stars $T_{i}$ whose centers are not used
as endpoints of paths in $\mathcal{P}$. Then we have

$|U|\geq\tfrac{t^{2}m^{3x-1}}{30}-2tm^{4x+2}\geq\tfrac{t^{2}m^{3x-1}}{60},$

and

$|V|\geq\tfrac{t}{30}\cdot(4tm^{4x-1}-2tm^{4x-1})\geq\tfrac{t^{2}m^{4x-1}}{60}.$

On the other hand, recall that $t\geq m^{3x}$, thus

$|W|+|W_{2}|+|\mathsf{Int}(\mathcal{P})|+|Z|\leq\tfrac{t^{2}m^{2x+12}}{4}+t^{2}m^{2x}+3tm^{5x+2}+4tm^{4x}\leq
t^{2}m^{2x+12}.$

Hence, applying Lemma 3.10 with $V_{2},U,V,W\cup
W_{2}\cup\mathsf{Int}(\mathcal{P})\cup Z$ playing the roles of
$V,X_{1},X_{2},W$, respectively, we obtain vertices $x_{1}\in U,x_{2}\in V$
and a path through $V_{2}$ of length at most $m^{3}$ connecting $x_{1}$ and
$x_{2}$ whilst avoiding vertices in $W\cup
W_{2}\cup\mathsf{Int}(\mathcal{P})\cup Z$. Denote by $S_{k_{1}},T_{k_{2}}$ the
stars which contain $x_{1},x_{2}$ as leaves, respectively. This yields a
$u_{k_{1}},v_{k_{2}}$-path $P_{k_{1},k_{2}}$, which is internally disjoint
from $W\cup W_{2}\cup\mathsf{Int}(\mathcal{P})\cup Z$. Hence,
$P_{k_{1},k_{2}}$ satisfies (F1) and (F2), a contradiction to the maximum of
$\mathcal{P}$.

Therefore, there exists a center $u_{i}$ connected to $2m^{x}$ distinct
centers $v_{j}$, say $v_{1},\ldots v_{2m^{x}}$, which correspond to stars
$T_{1},\ldots T_{2m^{x}}$. Recall that all stars in $\\{T_{1},\ldots
T_{2m^{x}}\\}$ are vertex disjoint and the number of vertices in all $P_{i,j}$
$(j\in[2m^{x}])$ is at most $2m^{x+3}<\tfrac{t}{120}$. Hence, every $T_{j}$
$(j\in[2m^{x}])$ has at least $\tfrac{t}{40}$ leaves that are not used in
$P_{i,j}$ for any $j\in[2m^{x}]$. These stars, together with the corresponding
paths to $u_{i}$, form a desired unit in $G-W-W_{2}$. Thus, we can greedily
pick vertex-disjoint units as above. ∎

##  5 Concluding remarks

As discussed in the introduction, the term $\sqrt{\tfrac{C_{\alpha}(G)}{\log
C_{\alpha}(G)}}$ is tight by considering the $d/1000$-blow-up of a $d$-vertex
$1000$-regular expander, which consists of large complete bipartite graphs. It
would be possible that the logarithmic term can be removed by excluding any
fixed bipartite graph, thus generalising the result of Liu-Montgomery [24].

## References

  * [1] N. Alon, J. H. Spencer, The Probabilistic Method, 4th edition, John Wiley & Sons, 2016.
  * [2] J. Balogh, H. Liu, M. Sharifzadeh, Subdivisions of a large clique in $C_{6}$-free graphs, Journal of Combinatorial Theory, Series B, 2015, 112: 18-35.
  * [3] B. Bollobás, A. Thomason, Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs, European Journal of Combinatorics, 1998, 19: 883-887.
  * [4] A. Bondy and M. Simonovits, Cycles of even length in graphs, J. Combinatorial Theory Ser. B, 1974, 16: 97-105.
  * [5] M. Bucić, R. Montgomery, Towards the Erdős-Gallai cycle decomposition conjecture, Advances in Mathematics, 2024, 437: 109434.
  * [6] P. Erdős, A. Hajnal, On chromatic number of graphs and set-systems. Acta Mathematica Hungarica, 1966, 17(1-2): 61-99.
  * [7] P. Erdős, A. Hajnal, On topological complete subgraphs of certain graphs. Annales Universitatis Scientiarum Budapestinensis, 1969, 7: 193-199.
  * [8] J. Fox, B. Sudakov, Dependent random choice, Random Structures and Algorithms, 2011, 38: 68-99.
  * [9] L. Friedman, M. Krivelevich, Cycle lengths in expanding graphs, Combinatorica, 2021, 41: 53-74.
  * [10] J. Haslegrave, J. Hu, J. Kim, H. Liu, B. Luan, and G. Wang, Crux and long cycles in graphs, SIAM Journal on Discrete Mathematics, 2022, 36: 2942-2958.
  * [11] J. Haslegrave, J. Kim, and H. Liu, Extremal density for sparse minors and subdivisions, International Mathematics Research Notices, 2022, 2022(20): 15505-15548.
  * [12] J. Haslegrave, J. Hyde, J. Kim, H. Liu, Ramsey numbers of cycles versus general graphs, Forum of Mathematics, Sigma, 2023, 11: 1-18.
  * [13] S. Im, J. Kim, Y. Kim, H. Liu, Crux, space constraints and subdivisions, arXiv:2207.06653, 2022.
  * [14] H. A. Jung, Eine Verallgemeinerung des $n$-fachen Zusammenhangs für Graphen, Mathematische Annalen, 1970, 187: 95-103.
  * [15] J. Kim, H. Liu, Y. Tang, G. Wang, D. Yang, F. Yang, Extremal density for subdivisions with length or sparsity constraints, arXiv: 2401.15403, 2024.
  * [16] J. Komlós, E. Szemerédi, Topological cliques in graphs, Combinatorics, Probability and Computing, 1994, 3: 247-256.
  * [17] J. Komlós, E. Szemerédi, Topological cliques in graphs II, Combinatorics, Probability and Computing, 1996, 5: 79-90.
  * [18] M. Krivelevich, W. Samotij, Long paths and cycles in random subgraphs of $H$-free graphs. Electronic Journal of Combinatorics, 2014, 21(1): P1.30.
  * [19] M. Krivelevich, B. Sudakov, Minors in expanding graphs, Geometric and Functional Analysis, 2009, 19: 294-331.
  * [20] D. Kühn, D. Osthus, Topological minors in graphs of large girth, Journal of Combinatorial Theory, Series B, 2002, 86: 364-380.
  * [21] D. Kühn, D. Osthus, Improved bounds for topological cliques in graphs of large girth, SIAM Journal on Discrete Mathematics, 2006, 20: 62-78.
  * [22] K. Kuratowski, Surle, problème des courbes gauches en topologie, Fundamenta Mathematica, 1930, 15: 271-283.
  * [23] S. Letzter, Sublinear expanders and their applications, Surveys in Combinatorics 2024, London Math. Soc. Lecture Note Ser., vol. 493, Cambridge Univ. Press, Cambridge (2024), to appear.
  * [24] H. Liu, R. Montgomery, A proof of Mader’s conjecture on large clique subdivisions in $C_{4}$-free graphs, Journal of the London Mathematical Society, 2017, 95(2): 203-222.
  * [25] H. Liu, R. Montgomery, A solution to Erdős and Hajnal’s odd cycle problem, Journal of the American Mathematical Society, 2023, 36(4): 1191-1234.
  * [26] W. Mader, Homomorphieegenschaften und mittlere Kantendichte von Graphen, Mathematische Annalen, 1967, 174: 265-268.
  * [27] W. Mader, An extremal problem for subdivisions of $K^{-}_{5}$, Journal of Graph Theory, 1999, 30: 261-276.
  * [28] R. Montgomery, Logarithmically small minors and topological minors, Journal of the London Mathematical Society, 2015, 91: 71-88.
  * [29] L. Pósa, Hamiltonian circuits in random graphs, Discrete Math., 1976, 14: 359-364.
  * [30] B. Sudakov and J. Verstraëte, Cycle lengths in sparse graphs, Combinatorica, 2008, 28: 357-372.

##  Appendix A Proof of Lemma 3.4

As promised, we shall prove Lemma 3.4, and this improves a result in [13] as
follows.

######  Lemma A.1 ([13]).

Suppose $\tfrac{1}{n}\ll c\ll\varepsilon\ll\tfrac{1}{100}$ and
$d\leq\exp(\log^{1/6}n)$. If an $n$-vertex $(\varepsilon,\varepsilon
d)$-robust-expander $G$ has average degree at least $\tfrac{d}{2}$ and minimum
degree $\delta(G)\geq\tfrac{d}{4}$, then $G$ contains a $K_{cd}$-subdivision.

We will use the following result due to Komlós and Szemerédi to robustly find
expanders.

######  Lemma A.2 ([17]).

There exist $0<\varepsilon_{0},\varepsilon_{1}<\tfrac{1}{8}$ such that for any
$k\in\mathbb{N}$ every graph $G$ contains an $(\varepsilon_{1},k)$-expander
$H(V,E)$ with

$d(H)\geq\tfrac{d(G)}{1+\varepsilon_{0}}\geq\tfrac{d(G)}{2}\ \text{and}\
\delta(H)\geq\tfrac{d(H)}{2},$

which has the following additional robust property where $n=|V|$. For every
$X\subseteq V$ with $|X|<\tfrac{n\rho(n)d(H)}{4\Delta(H)}$, there is a subset
$Y\subseteq V\setminus X$ of size
$|Y|>n-\tfrac{2\Delta(H)}{d(H)}\cdot\tfrac{|X|}{\rho(n)}$ such that $H[Y]$ is
still an $(\varepsilon_{1},k)$-expander. Moreover,
$d(H[Y])\geq\tfrac{d(H)}{2}$.

We will use a result in [13, Lemma 4.2] which reduces the problem to finding
clique subdivisions in expanders of bounded maximum degree.

######  Lemma A.3 ([13]).

Suppose $\tfrac{1}{d}\ll c\ll\varepsilon\ll 1$ and $\varepsilon d\leq k\leq
d^{2}\log^{9}n$. Let $G$ be an $n$-vertex $(\varepsilon,k)$-expander with
$\delta(G)\geq\tfrac{d}{2}$. If $G$ does not contain a $K_{cd}$-subdivision,
then $G$ contains an $(\tfrac{\varepsilon}{2},k)$-expander subgraph $H$ with
at least $\tfrac{n}{2}$ vertices such that $\delta(H)\geq\tfrac{d}{4}$ and
$\Delta(H)\leq 10d^{2}\log^{10}n$.

The proof of Lemma 3.4 essentially follows from that of Lemma 3.1, and the
main task therefore is to build many webs that have disjoint interiors. To do
this, we first robustly grow a ball around a vertex as follows (in place of
Lemma 3.9).

######  Lemma A.4.

Suppose $\tfrac{1}{n},\tfrac{1}{d}\ll c\ll\varepsilon\leq\tfrac{1}{5}$ and
$d\leq\tfrac{\sqrt{n}}{2\log^{20}n}$. Let $G$ be an $n$-vertex
$(\varepsilon,\varepsilon d)$-expander with $\delta(G)\geq\tfrac{d}{100}$. Let
$\ell=\log^{4}(d\log^{40}n)$ and $P_{1},\dots,P_{t}$ be consecutive shortest
paths from a fixed vertex $v$ in $B_{G}^{\ell}(v)$. Writing $U=\bigcup_{i\in
t}V(P_{i})$, if $t\leq cd$, then $|B_{G-(U\backslash\\{v\\})}^{\ell}(v)|\geq
d^{2}\log^{40}n$.

Lemma A.4 follows from the same proof as in [15, Lemma 4.8] using slightly
different parameters.

###### Proof of Lemma 3.4.

We may assume that $d\geq\log^{50}n$ in the whole process of the proof,
otherwise Lemma A.1 implies that the result holds. Choose $\tfrac{1}{d}\ll
c\ll b\ll\varepsilon\ll 1$, and $d,n$ satisfy $\log^{50}n\leq
d\leq\sqrt[3]{\tfrac{n}{\log^{100}n}}$. Let $G$ be an $n$-vertex
$(\varepsilon,\varepsilon d)$-expander with average degree at least
$\tfrac{d}{2}$ and minimum degree $\delta(G)\geq\tfrac{d}{4}$. Suppose to the
contrary that $G$ contains no $K_{cd}$-subdivision, then by Lemma A.3 with
$(k,d)=(\varepsilon d,\tfrac{d}{2})$, there is an
$(\tfrac{\varepsilon}{2},\varepsilon d)$-expander $H$ in $G$ such that
$|H|\geq\tfrac{n}{2}$, $\delta(H)\geq\tfrac{d}{8}$ and $\Delta(H)\leq
3d^{2}\log^{10}n$. In the following, we shall find a $K_{cd}$-subdivision in
$H$ to yield a contradiction. Let $m=\log^{4}\tfrac{n}{d}$.

######  Claim A.5.

For any set $W\subseteq V(H)$ with $|W|\leq d^{2}m^{9}$, $H-W$ contains a
$(4cd,4m,m^{8},\tfrac{d}{40},m+2)$-web.

###### Proof of Claim A.5.

We use Lemma A.2 to greedily find vertex-disjoint stars.

  * $(1)$

For any set $X$ of size at most $d^{2}m^{10}$, the graph $H-W-X$ contains
vertex-disjoint stars $S_{1},\cdots,S_{2dm^{24}}$ where each $S_{i}$ has
exactly $\tfrac{d}{10}$ leaves.

Indeed, if we have $S_{1},\cdots,S_{\ell}$ for some $0\leq\ell<2dm^{24}$, then
the set $W_{1}:=\bigcup_{i\in[\ell]}V(S_{i})$ has size at most $d^{2}m^{24}$.
By Lemma A.2 and the assumption $d\leq\sqrt[3]{\tfrac{n}{\log^{100}n}}$, there
exists $Y\subseteq V(H)\setminus(W_{1}\cup W\cup X)$ such that

$|Y|\geq\tfrac{n}{2}-\tfrac{2\Delta(H)|W_{1}\cup W\cup
X|}{d(H)\rho(n)}\geq\tfrac{n}{4},\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ d(H[Y])\geq\tfrac{d}{8}.$

Thus $H-W-X$ contains a star $S_{\ell+1}$ with $\tfrac{d}{10}$ leaves disjoint
from $W_{1}$. By repeating this for $s=0,1,\ldots,2dm^{24}$, we obtain the
desired stars.

  * $(2)$

The graph $H-W$ contains vertex-disjoint $(2m^{8},\tfrac{d}{20},m+2)$-units
$F_{1},\ldots,F_{2dm^{2}}$.

If we have $F_{1},\ldots,F_{\ell}$ for some $0\leq\ell<2dm^{2}$, then the set
$W_{2}:=\bigcup_{i\in[\ell]}V(F_{i})$ has size at most
$2dm^{2}[2m^{8}(m+2+\tfrac{d}{20})]\leq\tfrac{d^{2}m^{10}}{4}$. By $(1)$,
$H-W-W_{2}$ contains vertex-disjoint stars $S_{1},\cdots,S_{dm^{12}}$,
$T_{1},\ldots,T_{dm^{24}}$ with centers $u_{1},\ldots,u_{dm^{12}}$,
$v_{1},\ldots,v_{dm^{24}}$, respectively, where each of these stars has
exactly $\tfrac{d}{10}$ leaves. We denote
$Z=\\{u_{1},\ldots,u_{dm^{12}},v_{1},\ldots,v_{dm^{24}}\\}$.

Let $\mathcal{P}$ be a maximum collection of internally disjoint paths
$P_{ij}$ in $H-W-W_{2}$ satisfying the following rules.

  1. (G1)

Each path $P_{ij}$ in $\mathcal{P}$ is a unique $u_{i},v_{j}$-path of length
at most $m+2$.

  2. (G2)

Each $P_{ij}$ does not contain any vertex in $Z\cup W_{2}\cup W$ as an
internal vertex.

Now we declare that there is a center $u_{i}$ connected to at least $2m^{8}$
distinct centers $v_{j}$ via the paths in $\mathcal{P}$. Suppose to the
contrary that every $u_{i}$ is connected to less than $2m^{8}$ centers
$v_{j}$. Then $|\mathcal{P}|\leq 2dm^{20}$ and $|V(\mathcal{P})|\leq
2dm^{20}\cdot(m+2)\leq 3dm^{21}$. Let

$U:=\left(\bigcup_{i\in[dm^{12}]}(V(S_{i})\backslash\\{u_{i}\\})\right)\setminus
V(\mathcal{P}),$

and $V$ be the set of leaves of all stars $T_{i}$ whose centers are not used
as endpoints of paths in $\mathcal{P}$. Then we have

$|U|\geq\tfrac{d^{2}m^{12}}{10}-3dm^{21}\geq\tfrac{d^{2}m^{12}}{20},$ (7)

and

$|V|\geq\tfrac{d}{10}\cdot(dm^{24}-2dm^{20})\geq\tfrac{d^{2}m^{12}}{20}.$ (8)

On the other hand,

$|W|+|W_{2}|+|\mathsf{Int}(\mathcal{P})|+|Z|\leq
d^{2}m^{9}+\tfrac{d^{2}m^{10}}{4}+3dm^{21}+dm^{12}+dm^{24}\leq d^{2}m^{10}.$
(9)

Thus, applying Lemma 2.3 with $U,V$, $W\cup
W_{2}\cup\mathsf{Int}(\mathcal{P})\cup Z$ playing the roles of
$X_{1},X_{2},W$, respectively, we obtain vertices $x_{1}\in U,x_{2}\in V$ and
a path of length at most $m$ connecting $x_{1}$ and $x_{2}$ whilst avoiding
vertices in $W\cup W_{2}\cup\mathsf{Int}(\mathcal{P})\cup Z$. Denote by
$S_{k_{1}},T_{k_{2}}$ the stars which contain $x_{1},x_{2}$ as leaves,
respectively. This yields a $u_{k_{1}},v_{k_{2}}$-path $P_{k_{1},k_{2}}$,
which is internally disjoint from $W\cup
W_{2}\cup\mathsf{Int}(\mathcal{P})\cup Z$. Hence, $P_{k_{1},k_{2}}$ satisfies
(F1) and (F2), a contradiction to the maximum of $\mathcal{P}$.

Therefore, there exists a center $u_{i}$ connected to $2m^{8}$ distinct
centers $v_{j}$, say $v_{1},\ldots v_{2m^{8}}$, which correspond to stars
$T_{1},\ldots T_{2m^{8}}$. Recall that all stars in $\\{T_{1},\ldots
T_{2m^{8}}\\}$ are vertex-disjoint and the number of vertices in all $P_{i,j}$
$(j\in[2m^{8}])$ is at most $2m^{8}(m+2)<\tfrac{d}{20}$. Hence, every $T_{j}$
$(j\in[2m^{8}])$ has at least $\tfrac{d}{20}$ leaves that are not used in
$P_{i,j}$ for any $j\in[2m^{8}]$. These stars, together with the corresponding
paths to $u_{i}$, form a desired unit in $H-W-W_{2}$. Thus, we can greedily
pick vertex-disjoint units as above.

Now we get pairwise vertex-disjoint $(2m^{8},\tfrac{d}{20},m+2)$-units
$F_{1},\ldots,F_{2dm^{2}}$, and denote by $f_{i}$ the core vertex of $F_{i}$
and $F=\\{f_{1},\ldots,f_{2dm^{2}}\\}$. Let
$W_{3}=\bigcup_{i\in[2dm^{2}]}V(F_{i})$ and
$W_{4}=\bigcup_{i\in[2dm^{2}]}\mathsf{Int}(F_{i})$. Then we have $|W_{4}|\leq
4dm^{11}$ and $|W_{3}|\leq\tfrac{d^{2}m^{10}}{4}$. As $|W|+|W_{3}|\leq
d^{2}m^{9}+\tfrac{d^{2}m^{10}}{4}<d^{2}m^{10}$, by Lemma A.2, we again get
that there exists $Y^{\prime}\subseteq V(H)\setminus(W\cup W_{3})$ with
$|Y^{\prime}|\geq\tfrac{n}{2}$ such that the subgraph $G_{1}:=H[Y^{\prime}]$
is still an $(\tfrac{\varepsilon}{2},\varepsilon d)$-expander with
$\delta(G_{1})\geq\tfrac{1}{2}d(G_{1})\geq\tfrac{d}{16}$ and pick a vertex
$v\in V(G_{1})$. We claim that there is a
$(4cd,4m,m^{8},\tfrac{d}{40},m+2)$-web centered at $v$.

To build the desired $(4cd,4m,m^{8},\tfrac{d}{40},m+2)$-web, we shall proceed
by finding $4cd$ internally vertex-disjoint paths $Q_{1},\ldots,Q_{4cd}$ in
$G$ from $v$ satisfying the following rules, where $\ell$ is a constant
obtained from Lemma A.4 applied on $G_{1}$.

  1. (H1)

Each path $Q_{i}$ is a unique $v,f_{x_{i}}$-path of length at most
$3m+\log^{4}(d\log^{40}n)\leq 4m$, where $x_{i}\in[2dm^{2}]$.

  2. (H2)

Each path does not contain any vertex in $W_{4}\cup W$ as an internal vertex.

  3. (H3)

The sequence of subpaths $Q_{i}[B^{\ell}_{G_{1}}(v)]$ $(i\in[4cd])$ form
consecutive shortest paths from $v$ in $B^{\ell}_{G_{1}}(v)$.

Assume that we have iteratively obtained a collection of shortest paths
$\mathcal{Q}=\\{Q_{1},\ldots,Q_{s}\\}$ $(0\leq s<4cd)$ as in (H1)-(H3). Then
$|\mathsf{Int}(\mathcal{Q})|<16cdm$. Note that (H3) gives $s$ consecutive
shortest paths $P_{1},\ldots,P_{s}$ from $v$ in $B_{G_{1}}(v)$, where
$P_{i}=Q_{i}[B^{\ell}_{G_{1}}(v)]$ and write
$\mathcal{P}=\\{P_{1},\ldots,P_{s}\\}$. Applying Lemma A.4 to $G_{1}$, we get

$|B^{\ell}_{G_{1}-\mathsf{Int}(\mathcal{Q})}(v)|=|B_{G_{1}-\mathsf{Int}(\mathcal{P})}^{\ell}(v)|\geq
d^{2}\log^{40}(\tfrac{n}{2})\geq d^{2}m^{10}.$

We call a unit $F_{i}$ available if its core vertex is not used as an endpoint
of a path in $\mathcal{Q}$. Let $U^{\prime}$ be the leaves of all pendent
stars in available units. Then we have

$|U^{\prime}|\geq
2m^{8}\cdot\tfrac{d}{20}(2dm^{2}-4cd)>\tfrac{d^{2}m^{10}}{10}.$

Note that

$|W|+|V(\mathcal{Q})|+|W_{4}|\leq d^{2}m^{9}+16cdm+4dm^{11}<2d^{2}m^{9}.$

Applying Lemma 2.3 on $H$ with
$B_{G_{1}-\mathsf{Int}(\mathcal{Q})}^{\ell}(v)$, $U^{\prime}$, $W_{4}\cup
W\cup V(\mathcal{Q})$ playing the roles of $X_{1},X_{2},W$, respectively, we
can find a shortest path, say $Q$, joining a vertex $w$ from
$B_{G_{1}-\mathsf{Int}(\mathcal{Q})}^{\ell}(v)$ to a leaf
$u_{j}\in\mathsf{Ext}(F_{j})$ for some $j\in[2dm^{2}]$. One can easily find a
$v,w$-path within $B^{\ell}_{G_{1}-\mathsf{Int}(\mathcal{Q})}(v)$, denoted as
$P_{s+1}$, and a $u_{j},f_{j}$-path, denoted as $R_{s+1}$, inside the unit
$F_{j}$. Let $Q_{s+1}=P_{s+1}QR_{s+1}$. Then the paths $Q_{1},\ldots,Q_{s+1}$
satisfy (H1)-(H3). Repeating this for $s=0,1,\ldots,4cd$, yields $4cd$ paths
$Q_{1},\ldots,Q_{4cd}$ as desired.

For every $i\in[2dm^{2}]$, we say a pendent star in $F_{i}$ is _overused_ if
at least $\tfrac{d}{40}$ leaves are used in $V(\mathcal{Q})$ and a unit is
_bad_ if at least $m^{8}$ pendent stars are overused. Then there are at most
$\tfrac{16cdm}{d/40}=160cm<m^{8}$ overused pendent stars in total, and
therefore there is no bad unit. By removing from every unit $F_{i}$ the
branches attached with overused pendant stars and combining corresponding
paths $Q_{i}$, we obtain a $(4cd,4m,m^{8},\tfrac{d}{40},m+2)$-web as desired.
∎

By repeatedly using Claim A.5, we can greedily find $d$ distinct
$(4cd,4m,m^{8},\tfrac{d}{40},m+2)$-webs in $H$ that have disjoint interiors,
as the total number of internal vertices of these webs is at most

$d\cdot 4cd\cdot(4m+(m+2)\cdot m^{8})\leq 20cd^{2}m^{9}<d^{2}m^{9}.$

By the same connection process as in the proof of Lemma 3.5 (see (E1)-(E2) in
Phase $(2)$), there is a $K_{cd}$-subdivision in $H$ as promised. ∎

##  Appendix B Proof of Lemma 3.10

The proof of Lemma 3.10 is immediately derived from the following result.

######  Lemma B.1.

Suppose $\tfrac{1}{n},\tfrac{1}{d}\ll\varepsilon<\tfrac{1}{5}$,
$d\geq\log^{100}n$ and $x,k\in\mathbb{N}$ with $x\geq 11$. Let $G$ be an
$n$-vertex $(\varepsilon,k)$-robust-expander with average degree $d$ and
$V\subseteq V(G)$ be a random subset chosen by including each vertex in
dependently at random with probability $\tfrac{1}{2}$. Let
$m=\log^{4}\tfrac{n}{k}$. Then with probability at least $1-o(\tfrac{1}{n})$,
for every $U,W\subseteq V(G)$ with
$km^{9}\leq|U|\leq\tfrac{2n}{3},|W|=\tfrac{|U|}{m^{x}}$

$|B^{m^{2}}_{G-W}(U)|>\tfrac{|V|}{2}.$

We shall first introduce some more notation and tools for the proof. Let
$N_{G,\lambda}(U):=\\{v\in V(G)\setminus U:|N_{G}(v)\cap U|\geq\lambda\\}$,
that is, the set of vertices in $V(G)\setminus U$ of degree at least $\lambda$
towards $U$. The following lemma shows that for every vertex subset $U$,
either $U$ or its robust neighborhood of vertices with plenty of edges towards
$U$ expands nicely.

######  Lemma B.2.

Suppose $\tfrac{1}{n}\ll\varepsilon<\tfrac{1}{5}$ and let $G$ be an $n$-vertex
$(\varepsilon,k)$-expander with average degree $d$ and
$m=\log^{4}\tfrac{n}{k}$, and let $U\subseteq V(G)$ with
$\tfrac{k}{2}\leq|U|\leq\tfrac{n}{2}$. Then for any $0<\lambda<d$, either

$\mathbf{(a)}.\ |N_{G}(U)|\geq\tfrac{d|U|}{\lambda m},\ \ \ \ \ \text{or}\ \ \
\ \ \mathbf{(b)}.\ |N_{G,\lambda}(U)|\geq\tfrac{|U|}{m}.$

###### Proof.

Suppose that $\mathbf{(a)}$ is not true, that is,
$|N_{G}(U)|<\tfrac{d|U|}{\lambda m}$. Let $X=N_{G}(U)\setminus
N_{G,\lambda}(U)$, so that $|X|\leq|N_{G}(U)|<\tfrac{d|U|}{\lambda m}$. Let
$F$ be the edges of $G$ between $U$ and $X$, so that

$|F|<\lambda|X|<\tfrac{d|U|}{m}<\rho(|U|)|U|d.$

Then we obtain that $\mathbf{(b)}$ holds as

$|N_{G,\lambda}(U)|\geq|N_{G-F}(U)|\geq\rho(|U|)|U|\geq\tfrac{|U|}{m}.$

∎

The following result was first observed in [5], and we make a slight
adaptation for our proof.

######  Lemma B.3.

Suppose $\tfrac{1}{n}\ll\varepsilon<\tfrac{1}{5}$ and $x,k\in\mathbb{N}$ with
$x\geq 2$. Let $G$ be an $n$-vertex $(\varepsilon,k)$-robust-expander with
average degree $d$, $m=\log^{4}\tfrac{n}{k}$ and $U,W\subseteq V(G)$ with
$k\leq|U|\leq\tfrac{2n}{3},|W|\leq\tfrac{|U|}{m^{x}}$. Then for all positive
integers $\lambda,s,t$ with $s\geq 8m,t\geq 2\lambda$ and $d\geq 10tm\lambda$,
we can find in $G-W$ either

  * $(1)$

$\tfrac{|U|}{s}$ vertex-disjoint stars, whose centers in $U$ and each with $t$
leaves such that all lie in $V(G)\setminus(U\cup W)$, or

  * $(2)$

a bipartite subgraph $H$ with vertex classes $U$ and $X\subseteq
V(G)\setminus(U\cup W)$ such that $|X|\geq\tfrac{|U|}{4m}$ and every vertex in
$X$ has degree at least $\lambda$ in $H$ and every vertex of $U$ has degree at
most $2t$ in $H$.

###### Proof.

First, we take a maximal collection of vertex-disjoint $t$-stars in $G-W$ such
that all centers lie in $U$ and leaves outside $U$. Denote by $C,L$ the set of
centers and the set of all leaves, respectively, of these stars. If $(1)$ dose
not hold, then we can assume that $|C|<\tfrac{|U|}{s}$ and
$|L|<\tfrac{|U|t}{s}$. By the maximality, every vertex in $U\setminus C$ has
less than $t$ neighbors in $V(G-W)\backslash(U\cup L)$. Thus,

$|N_{G-W}(U\setminus C)|\leq|C|+|L|+(|U|-|C|)t\leq 2|U|t.$ (10)

Second, we aim to construct the bipartite subgraph $H$ through the following
process. Let $X_{0}=\emptyset$, and set $H_{0}$ to be the graph with vertex
set $U\cup X_{0}$ and no edges. Let $r=|V(G)\setminus(U\cup W)|$ and label the
vertices of $V(G)\setminus(U\cup W)$ arbitrarily $v_{1},v_{2},\ldots,v_{r}$.
For each $i\geq 1$, if possible pick a star $S_{i}$ in $G-W$ with center
$v_{i}$ and $\lambda$ leaves in $U$ such that $H_{i-1}\cup S_{i}$ has maximum
degree at most $2t$, and let $H_{i}=H_{i-1}\cup S_{i}$ and
$X_{i}=X_{i-1}\cup\\{v_{i}\\}$, while otherwise we set $H_{i}=H_{i-1}$ and
$X_{i}=X_{i-1}$. Finally, we shall claim that $(2)$ holds for $H_{r}$ with
bipartition $(U,X_{r})$.

By the construction, $\Delta(H_{i})\leq 2t$ holds for each $i\in[r]$, and
every vertex $v_{i}$ in $X_{r}$ has degree exactly $\lambda$ in $H_{r}$. It
remains to show that $|X_{r}|\geq\tfrac{|U|}{4m}$. Suppose for contradiction
that $|X_{r}|<\tfrac{|U|}{4m}$ and let $U^{\prime}=\\{v\in U\setminus
C:d_{H_{r}}(v)=2t\\}$. Due to the maximality of the family of vertex-disjoint
stars defining $C$ and $L$ we picked before, each vertex in $U^{\prime}$ has
fewer $t$ neighbors in $X_{r}\backslash(L\cup W)$. That is, it must have at
least $t$ neighbors in $X_{r}\cap L$. Recall that for each $v\in X_{r}\cap L$,
we have $d_{H_{r}}(v)=\lambda$. Thus,

$|U^{\prime}|\leq\tfrac{\lambda|X_{r}\cap
L|}{t}\leq\tfrac{\lambda|X_{r}|}{t}\leq\tfrac{\lambda|U|}{4tm}.$

Let $B=C\cup U^{\prime}$. Then
$|B|\leq\tfrac{|U|}{s}+\tfrac{\lambda|U|}{4tm}\leq\tfrac{|U|}{4m}$, and thus
$|U\setminus B|\geq\tfrac{2|U|}{3}\geq\tfrac{k}{2}$. Applying Lemma B.2 to
$U\setminus B$, we have either

$|N_{G-W}(U\setminus B)|\geq\tfrac{d|U\setminus B|}{\lambda
m}-|W|\geq\tfrac{d|U\setminus B|}{2\lambda m},\ \ \text{or}\ \
|N_{G-W,\lambda}(U\setminus B)|\geq\tfrac{|U|}{m}-|W|\geq\tfrac{|U|}{2m}.$

Since

$|N_{G-W}(U\setminus C)|\geq|N_{G-W}(U\setminus B)|-|U|\geq\tfrac{d|U\setminus
B|}{2\lambda m}-|U|\geq\tfrac{d|U|}{3\lambda m}-|U|>2|U|t,$

a contradiction to (10). Therefore, $|N_{G-W,\lambda}(U\setminus
B)|\geq\tfrac{|U|}{2m}>|B|+|X_{r}|$. Note that every vertex $v$ in
$N_{G-W,\lambda}(U\setminus B)\setminus(B\cup X_{r})$ has at least $\lambda$
neighbors in $U\setminus B$ in $G-W$ while every vertex in $U\setminus B$ has
degree strictly less than $2t$ in $H_{r}$. Thus we can further add a
$\lambda$-star centered at $v$ to $H_{r}$, a contradiction to the maximality
of $H_{r}$. ∎

Lemma B.4 depicts that any vertex $U$ in an $(\varepsilon,k)$-expander $G$
contains a “not small” subset $U^{\prime}$ such that $U^{\prime}$ also expands
well, and so that $U^{\prime}$ captures lots of the expansion properties of
$U$.

######  Lemma B.4.

Suppose $\tfrac{1}{n},\tfrac{1}{d}\ll\varepsilon<\tfrac{1}{5}$ and
$k\in\mathbb{N}$. Let $G$ be an $n$-vertex $(\varepsilon,k)$-robust-expander
with average degree $d$ and $U\subseteq V(G)$ with
$\tfrac{k}{2}\leq|U|\leq\tfrac{2n}{3}$. Let $m=\log^{4}\tfrac{n}{k}$. Then for
any positive constant $\kappa\leq\tfrac{d}{m}$, there exists
$U^{\prime}\subseteq U$ with $|N_{G}(U^{\prime})|\geq\kappa|U^{\prime}|$ and
$|U^{\prime}|>\tfrac{|U|}{\kappa m}$.

###### Proof.

We may assume that $|U|\geq 1$, otherwise we just take $U^{\prime}=\emptyset$
satisfying the required conditions. Let $U^{\prime}\subseteq U$ be a maximal
set subject to $|N_{G}(U^{\prime})|\geq\kappa|U^{\prime}|$, and this is
possible as $U^{\prime}=\emptyset$ satisfies these conditions. If
$U=U^{\prime}$, then $U$ satisfies the condition itself. Next, we assume that
$U\neq U^{\prime}$. By the maximality of $U^{\prime}$, we have that
$|N_{G}(U^{\prime})|<\kappa(|U^{\prime}|+1)$, and every vertex $u$ in
$U\setminus U^{\prime}$ satisfying that $d_{G-N_{G}[U^{\prime}]}(u)<\kappa$.
Let $F$ be the set consisting of edges $uv$ with $u\in U\setminus U^{\prime}$
and $v\in V(G)-N_{G}[U^{\prime}]$. Then $|F|<\kappa|U\setminus
U^{\prime}|<\tfrac{|U|d}{m}<\rho(|U|)|U|d$. As $G$ is an
$(\varepsilon,k)$-robust-expander, we obtain

$\rho(|U|)|U|\leq|N_{G-F}(U)|\leq|N_{G}(U^{\prime})|<\kappa(|U^{\prime}|+1).$

Hence, $|U^{\prime}|\geq\tfrac{\rho(|U|)|U|}{2\kappa}>\tfrac{|U|}{\kappa m}$.
∎

We also introduce the well-known martingale concentration result, which will
be used to prove Lemma B.1.

######  Lemma B.5 ([1]).

Suppose that $X:\prod_{i=1}^{n}\Omega_{i}\rightarrow\mathbb{R}$ is
$k$-Lipschitz. Then, for each $t>0$,

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

######  Lemma B.6.

Suppose $\tfrac{1}{n},\tfrac{1}{d}\ll\varepsilon<\tfrac{1}{5}$ and
$x,k,\kappa\in\mathbb{N}$ with $x\geq 2,d\geq\log^{100}n$. Let $G$ be an
$n$-vertex $(\varepsilon,k)$-expander with average degree $d$ and
$m=\log^{4}\tfrac{n}{k}$ and choose $\kappa\geq m^{8}$. Given subsets
$U,W\subseteq V(G)$ with $|N_{G}(U)|\geq\kappa|U|$ for
$k\leq|U|\leq\tfrac{2n}{3}$ and $|W|\leq\tfrac{|U|}{m^{x}}$, and let $V$ be a
random subset chosen by including each vertex independently at random with
probability $\tfrac{1}{2}$. Then, with probability
$1-\exp\left(-\Omega(\tfrac{\kappa|U|}{m^{6}})\right)$,

$|B_{G-W}^{m^{2}}(U,V)|>\tfrac{|V|}{2}.$

###### Proof.

Take $q=\frac{9}{20},\ell=m^{2}$ and $p$ be such that
$1-(1-p)^{\ell-1}(1-q)=\frac{1}{2}$. Then $(1-p)^{m^{2}-1}=\tfrac{10}{11}$ and
thus $p\geq\tfrac{1}{11m^{2}}$. For each $i\in[m^{2}]$, let $V_{i}$ be a
random subset of $V(G)$ with each vertex included independently at random with
probability $p$ if $i\leq m^{2}-1$ and with probability $q$ if $i=m^{2}$. Set
$V=V_{1}\cup\ldots\cup V_{m^{2}}$. Recall that each vertex is included in $V$
independently at random with probability $\tfrac{1}{2}$. For each $0\leq i\leq
m^{2}$, let $B_{i}$ be the set of vertrices of $G$ which can be reached via a
path in $G-W$ which starts in $U$ and has length at most $i$ and whose
internal vertices (if there are any) are in $V_{1}\cup\ldots\cup V_{i-1}$. In
particular, let $B_{0}=U$ and $B_{1}=B_{G-W}(U)$. Note that $B_{0}\subseteq
B_{1}\subseteq\ldots\subseteq B_{m^{2}}$. By the construction of $B_{i}$, we
know that it is completely determined by the sets $U,V_{1},\ldots,V_{i-1}$
while independent of $V_{i}$, and any vertex in $N_{G-W}(B_{i})$ with a
neighbor in $B_{i}$ that gets sampled into $V_{i}$ belongs to $B_{i+1}$. We
aim to evaluate the value of $|B_{m^{2}}\cap V_{m^{2}}|$ in order to get the
lower bound of $|B_{G-W}^{m^{2}}(U,V)|$.

Now we have the following claim, which states that either $B_{i}$ is very
large or $B_{i+1}$ is likely to be larger than $B_{i}$. Denote by
$N_{G}(v,A):=N_{G}(v)\cap A$ for some $A\subseteq V(G)$.

######  Claim B.7.

For each $1\leq i\leq m^{2}$, with probability
$1-\exp\left(-\Omega(\tfrac{\kappa|U|}{m^{6}})\right)$, either
$|B_{i}|\geq\tfrac{2n}{3}$ or $|B_{i+1}\setminus
B_{i}|\geq\tfrac{|B_{i}|}{128m}$.

###### Proof of Claim.

Observe that

$\\{v\in N_{G-W}(B_{i}):N_{G-W}(v,B_{i})\cap V_{i}\neq\emptyset\\}\subseteq
B_{i+1}\setminus B_{i}.$

We shall show that, for any set $Z\subseteq V(G)$ with $|Z|\leq\tfrac{2n}{3}$
and $B_{1}\subseteq Z$, the following holds.

$\mathbb{P}\left(|\\{v\in N_{G-W}(Z):N_{G-W}(v,Z)\cap
V_{i}\neq\emptyset\\}|\geq\tfrac{|Z|}{128m}\right)\geq
1-\exp\left(-\Omega(\tfrac{|B_{1}|}{m^{6}})\right).$ (11)

Hence, for all $1\leq i\leq m^{2}-1$

$\displaystyle\mathbb{P}\left(|B_{i}|\geq\tfrac{2n}{3}\ \ \text{or}\ \
|B_{i+1}\setminus
B_{i}|\geq\tfrac{|B_{i}|}{128m}\right)\geq\mathbb{P}\left(|B_{i+1}\setminus
B_{i}|\geq\tfrac{|B_{i}|}{128m}\mid|B_{i}|\leq\tfrac{2n}{3}\right)$
$\displaystyle\geq\mathbb{P}\left(|\\{v\in N_{G-W}(B_{i}):N_{G-W}(v,B_{i})\cap
V_{i}\neq\emptyset\\}|\geq\tfrac{|B_{i}|}{128m}\mid|B_{i}|\leq\tfrac{2n}{3}\right)$
$\displaystyle\geq 1-\exp\left(-\Omega(\tfrac{|B_{1}|}{m^{6}})\right)\geq
1-\exp\left(-\Omega(\tfrac{\kappa|U|}{m^{6}})\right),$

where the last second inequality we used
$|B_{1}|=|B_{G-W}(U)|\geq\kappa|U|-|W|\geq\tfrac{\kappa|U|}{2}$. Let
$Z\subseteq V(G)$ with $|Z|\leq\tfrac{2n}{3}$ and $B_{1}\subseteq Z$. As
$|Z|\leq\tfrac{2n}{3}$ and
$|W|\leq\tfrac{|U|}{m^{x}}\leq\tfrac{|B_{1}|}{m^{x}}\leq\tfrac{|Z|}{m^{x}}$,
we can apply Lemma B.3 to $Z$ and $W$ with

$\lambda=m^{2},\leavevmode\nobreak\ s=8m,\leavevmode\nobreak\ t=8m^{2},$

to show that (11) holds in either case as follows.

Suppose $G-W$ contains $\tfrac{|Z|}{8m}$ vertex-disjoint stars with $8m^{2}$
leaves, with the center in $Z$ and all leaves $V(G)\setminus Z$. Let
$C\subseteq Z$ be the set of centers of these stars and $|C|=\tfrac{|Z|}{8m}$.
Note that

$|\\{v\in N_{G-W}(Z):N_{G-W}(v,Z)\cap V_{i}\neq\emptyset\\}|\geq 8m^{2}|C\cap
V_{i}|.$ (12)

By the Chernoff bound and $p\geq\tfrac{1}{11m^{2}}$, with probability at least
$1-\exp\left(-\tfrac{p|C|}{8}\right)=1-\exp\left(\Omega(\tfrac{|Z|}{m^{3}})\right)$,
we have $|C_{i}\cap V_{i}|\geq\tfrac{p|C|}{2}\geq\tfrac{|Z|}{240m^{3}}$.
Combining this with (12) we have that (11) holds.

Suppose that there is a bipartite subgraph $H\subseteq G-W$ with partition $Z$
and $X$ such that $|X|\geq\tfrac{|Z|}{4m}$ and every vertex in $X$ has degree
at least $m^{2}$ in $H$ and every vertex of $Z$ has degree at most $16m^{2}$
in $H$. For each $v\in X$, the probability that $v$ has no neighbors in $H$ in
$V_{i}$ is at most $(1-p)^{m^{2}}\leq e^{-pm^{2}}\leq
e^{-1/11}\leq\tfrac{15}{16}$. Let $Y$ be the random variable counting the
number of vertices of $X$ having a neighbor in $V_{i}$ in $H$, so that
$\mathbb{E}[Y]\geq\tfrac{|X|}{16}$. Observe that $Y$ is $16m^{2}$-Lipschitz
since for each $v\in Z$, the event $\\{v\in V_{i}\\}$ affects $Y$ by at most
$d_{H}(v)\leq 16m^{2}$. Hence by Lemma B.5

$\mathbb{P}\left(Y<\tfrac{|X|}{32}\right)\leq\mathbb{P}\left(Y<\mathbb{E}[Y]-\tfrac{|X|}{32}\right)\leq
2\exp\left(-\tfrac{|X|^{2}}{2^{11}m^{4}|Z|}\right)\leq\exp\left(-\Omega(\tfrac{|Z|}{m^{6}})\right).$

Each vertex in $X$ with a neighbor in $V_{i}$ in $H$ lies in $\\{v\in
N_{G-W}(Z):N_{G-W}(v,Z)\cap V_{i}\neq\emptyset\\}$, so with probability
$\exp\left(-\Omega(\tfrac{|Z|}{m^{6}})\right)$, we have $|\\{v\in
N_{G-W}(Z):N_{G-W}(v,Z)\cap V_{i}\neq\emptyset\\}|\geq
Y\geq\tfrac{|X|}{32}\geq\tfrac{|Z|}{128m}$, and thus (11) holds. ∎

As $B_{m^{2}}$ and $V_{m^{2}}$ are independent and
$\frac{2}{3}q=\frac{3}{10}>\frac{4}{15}$, by Chernoff’s bound, we have that

$\mathbb{P}\left(|B_{m^{2}}\cap
V_{m^{2}}|\leq\frac{4}{15}n\mid|B_{m^{2}}|\geq\frac{2}{3}n\right)\leq\mathbb{P}\left(\mathsf{Bin}\big{(}\frac{2}{3}n,q\big{)}\leq\frac{4}{15}n\right)\leq
e^{-\Theta(n)}.$

As $\mathbb{P}\left(|V|\geq\frac{8}{15}n\right)\leq e^{-\Theta(n)}$. In
conclusion, we have that

  * $(i)$

for each $i\in[m^{2}-1]$, $|B_{i}|\geq\tfrac{2n}{3}$ or $|B_{i+1}\setminus
B_{i}|\geq\tfrac{|B_{i}|}{128m}$, and

  * $(ii)$

$|B_{m^{2}}|<\tfrac{2n}{3}$ or $|B_{m^{2}}\cap V_{m^{2}}|>\frac{4}{15}n$, and

  * $(iii)$

$|V|\leq\frac{8}{15}n$

with probability at least

$1-m^{2}\exp\left(-\Omega(\tfrac{\kappa|U|}{m^{6}})\right)-e^{-\Theta(n)}\geq
1-\exp\left(-\Omega(\tfrac{\kappa|U|}{m^{6}})\right).$

On the other hand, if $(i)-(iii)$ all hold, then for each $i\in[m^{2}-1]$, we
have

$|B_{i}|\geq\min\\{\tfrac{2n}{3},(1+\tfrac{1}{128m})^{i}|U|\\}.$

Let $i=m^{2}$, we have $|B_{m^{2}}|\geq\tfrac{2n}{3}$, and therefore,
combining $(ii)-(iii)$, we have $|B_{m^{2}}\cap V_{m^{2}}|>\tfrac{V}{2}$.
Hence, $|B_{G-W}^{m^{2}}(U,V)|>\tfrac{V}{2}$ with probability at least
$1-\exp\left(-\Omega(\tfrac{\kappa|U|}{m^{6}})\right)$. ∎

###### Proof of Lemma B.1.

A set $U^{\prime}\subseteq V(G)$ is a _well-expanding set_ in $G$ if
$|N_{G-W}(U^{\prime})|\geq m^{8}|U^{\prime}|$. First, we claim that Lemma B.1
is true for all well-expanding sets. Given a non-empty well-expanding set
$U_{1}\subseteq V(G)$ and a vertex set $W$ with
$|W|\leq\tfrac{|U_{1}|}{m^{x}}$, Lemma B.6 applied to $U_{1}$ with
$\kappa=m^{8}$ implies that the following fails with probability at most
$\exp\left(-\Omega(|U_{1}|m^{2})\right)$

$|B^{m^{2}}_{G-W}(U_{1},V)|>\tfrac{|V|}{2}.$ (13)

By union bound, we have

$\displaystyle\sum_{(U_{1},W)}\exp\left(-\Omega(|U_{1}|m^{2})\right)$
$\displaystyle\leq\sum_{j=k}^{n}\binom{n}{j}\binom{n}{j/m^{x}}\exp\left(-\Omega(jm^{2})\right)$
$\displaystyle\leq\sum_{j=k}^{n}(\tfrac{en}{j})^{2j}\exp\left(-\Omega(jm^{2})\right)$
$\displaystyle\leq\sum_{j=k}^{n}\exp\left(3j\log\tfrac{n}{k}-\Omega(jm^{2})\right)=\sum_{j=k}^{n}\exp\left(-\Omega(jm^{2})\right)=o\left(\tfrac{1}{n}\right),$

Thus, with probability $1-o\left(\tfrac{1}{n}\right)$, we obtain that (13)
holds for every well-expanding set $U_{1}$ and $W$ with
$|W|\leq\tfrac{|U_{1}|}{m^{x}}$, as claimed.

Let $U_{2}\subseteq V(G)$ with $km^{9}\leq|U_{2}|\leq\tfrac{2n}{3}$ and let
$W\subseteq V(G)$ with $|W|\leq\tfrac{|U_{2}|}{m^{x}}$. By Lemma B.4 with
$\kappa=m^{8}$, there is a set $U_{2}^{\prime}\subseteq U_{2}$ such that
$|N_{G}(U_{2}^{\prime})|\geq m^{8}|U_{2}^{\prime}|$ and
$|U_{2}^{\prime}|\geq\tfrac{|U_{2}|}{m^{9}}\geq k$. Therefore as
$|W|\leq\tfrac{|U_{2}|}{m^{x}}\leq\tfrac{|U_{2}^{\prime}|}{m^{x-9}}$ and
$x\geq 11$, one can apply Lemma B.6 with $(x,U,W)=(x-9,U_{2}^{\prime},W)$ to
get

$|B_{G-W}^{m^{2}}(U_{2},V)|\geq|B_{G-W}^{m^{2}}(U_{2}^{\prime},V)|>\tfrac{|V|}{2}.$

∎