# A faster exact method for solving the robust multi-mode resource-constrained
project scheduling problem

Matthew Bold111Corresponding author, email<EMAIL_ADDRESS>STOR-i
Centre for Doctoral Training, Lancaster University, Lancaster, UK  Marc
Goerigk  Network and Data Science Management, University of Siegen, Siegen,
Germany

###### Abstract

This paper presents a mixed-integer linear programming formulation for the
multi-mode resource-constrained project scheduling problem with uncertain
activity durations. We consider a two-stage robust optimisation approach and
find solutions that minimise the worst-case project makespan, whilst assuming
that activity durations lie in a budgeted uncertainty set. Computational
experiments show that this easy-to-implement formulation is many times faster
than the current state-of-the-art solution approach for this problem, whilst
solving over 40% more instances to optimality over the same benchmarking set.

Keywords: project scheduling; optimisation under uncertainty; robust
optimisation; budgeted uncertainty

##  1 Introduction

The multi-mode resource-constrained project scheduling problem (MRCPSP) is a
generalisation of the widely-studied resource-constrained project scheduling
problem (RCPSP) to include multiple processing modes for each activity. The
inclusion of these modes allows the modelling of situations in which there is
more than one way of executing project activities, with each option having its
own duration and resource requirements. The MRCPSP consists of selecting the
processing modes and start times for a given set of activities, subject to a
set of precedence constraints and limited resource availability, with the
objective of minimising the overall project duration, known as the makespan.

In this paper we consider the MRCPSP under uncertain activity durations and
model it using a two-stage adjustable robust optimisation framework. In this
setting, a first-stage problem is solved to determine activity mode selections
and make activity sequencing decisions to resolve resource conflicts.
Following this, the actual activity durations are realised and a complete
schedule is computed. The aim of the two-stage adjustable robust MRCPSP is to
find a feasible first-stage solution (i.e. mode selection and sequencing
decisions) in order to minimise the realised worse-case makespan, as computed
in the second-stage. We refer to this problem as the robust MRCPSP.

A number of papers in recent years have applied this two-stage robust
optimisation approach to the RCPSP. First to use this approach were Artigues
et al., (2013), who presented an iterative scenario-relaxation algorithm for
this problem with the objective of minimising the worst-case absolute regret.
More recently, Bruni et al., (2017) introduced a Benders’-style decomposition
approach for solving the robust RCPSP with the objective of minimising the
worst-case project makespan. This work was extended in Bruni et al., (2018),
which presented a computational study comparing an additional Benders’
decomposition approach against a primal decomposition algorithm. Most
recently, Bold and Goerigk, (2021) introduced a compact reformulation of the
robust RCPSP and presented results which showed the superior computational
performance of that formulation over the iterative decomposition-based methods
developed in the two preceding papers.

The application of this two-stage robust optimisation approach for the MRCPSP
is a very recent development. To the best of our knowledge, the only existing
paper to consider this problem is Balouka and Cohen, (2021), in which the
Benders’ decomposition approach introduced by Bruni et al., (2017) for the
robust RCPSP has been extended for application to the MRCPSP. Mirroring that
extension, this paper adapts the compact formulation developed by Bold and
Goerigk, (2021) to the MRCPSP, with the aim of achieving similarly superior
computational performance over the Benders’ solution approach.

Following a formal description of the two-stage robust MRCPSP in Section 2, we
outline the proposed compact formulation for this problem in Section 3 and
present a strengthened version of the Benders’ decomposition solution approach
from Balouka and Cohen, (2021) in Section 4. Results from a computational
comparison of these two approaches are detailed in Section 5.

##  2 Problem description

A project consists of a set of non-preemptive activities
$V=\\{0,1,\dots,n,n+1\\}$, where 0 and $n+1$ denote the dummy source and sink
activities respectively. Each activity $i\in V$ has a set of available
processing modes given by $M_{i}=\\{1,\dots,|M_{i}|\\}$. The nominal duration
of activity $i$ when executed in mode $m\in M_{i}$ is given by $\bar{d}_{im}$,
whilst its worst-case duration is given by $\bar{d}_{im}+\hat{d}_{im}$, where
$\hat{d}_{im}$ is its maximum durational deviation. Each mode for activity
$i$, $m\in M_{i}$, has an associated renewable resource requirement of
$r_{imk}$ for each $k\in K$, where $K$ is the set of renewable resource types
involved in the project. Each renewable resource $k\in K$ has an availability
of $R_{k}$ at each time period in the project horizon. As well as renewable
resource requirements, mode $m$ of activity $i$ also has a non-renewable
resource requirement of $r^{{}^{\prime}}_{imk}$ for each non-renewable
resource type $k\in K^{{}^{\prime}}$, with each non-renewable resource having
an overall availability of $R^{{}^{\prime}}_{k}$ for the entire project
horizon. Additionally, the project is subject to a set of strict finish-to-
start precedence constraints given by $E$, where $(i,j)\in E$ enforces that
activity $i$ must finish before activity $j$ can begin. These form a project
network that can be represented using a directed graph $G(V,E)$. Figure 1
shows an example instance involving five non-dummy activities and a single
renewable resource.

Figure 1: An example instance involving five non-dummy activities and a single
renewable resource with availability $R_{1}=4$. Activities 2 and 5 each have
two available processing modes, whilst the other activities have only a single
mode.

For a given choice of processing modes for each activity
$\bm{m}=(m_{1},\dots,m_{n})$, we assume that the activity durations lie
somewhere in a budgeted uncertainty set of the form

${\mathcal{U}}_{\bm{m}}(\Gamma)=\Bigg{\\{}\bm{d}_{\bm{m}}\in\mathbb{R}_{+}^{|V|}:d_{im_{i}}=\bar{d}_{im_{i}}+\xi_{i}\hat{d}_{im_{i}},\,0\leq\xi_{i}\leq
1,\,\forall i\in V,\,\sum_{i\in V}\xi_{i}\leq\Gamma\Bigg{\\}}.$

Introduced by Bertsimas and Sim, (2004), the motivation of the budgeted
uncertainty set is to control the pessimism of the solution by introducing a
robustness parameter $\Gamma$ to limit the number of jobs that can
simultaneously achieve their worst-case durations. Observe that when
$\Gamma=0$, each activity takes its nominal duration and the resulting problem
is the deterministic MRCPSP. At the other extreme, when $\Gamma=n$, every
activity takes its worst-case duration, in which case the uncertainty set
becomes equivalent to an interval uncertainty set. In this case the problem
can again be solved as a deterministic MRCPSP instance considering only worst-
case durations.

For a given set of activity modes $\bm{m}$, a forbidden set is defined to be
any subset of activities $F_{\bm{m}}\subseteq V$ that are not precedence-
related, such that $\sum_{i\in F_{\bm{m}}}r_{im_{i}k}>R_{k}$ for at least one
resource $k\in K$. That is, a forbidden set is a collection of activities that
cannot be executed in parallel only because of resource limitations. Applying
the main representation theorem of Bartusch et al., (1988), for a particular
choice of activity modes $\bm{m}$, a solution to the MRCPSP can be defined by
a set of additional precedences $X_{\bm{m}}\subseteq V^{2}\setminus E$ such
that the extended precedence network $G(V,E\cup X_{\bm{m}})$ is acyclic and
contains no forbidden sets. Such an extension to the project network is
referred to as a sufficient selection.

The aim of the two-stage robust MRCPSP is therefore to determine activity
modes and a corresponding sufficient selection in order to minimise the worst-
case project makespan. For the case where activity durations lie in a budgeted
uncertainty set that we consider in this paper, this problem can be written as

$\displaystyle\min_{\bm{m}\in{\mathcal{M}},\,X_{\bm{m}}\in{\mathcal{X}}_{\bm{m}}}\max_{\bm{d}\in{\mathcal{U}}_{\bm{m}}(\Gamma)}\
$ $\displaystyle\min S_{n+1}$ (1) s.t. $\displaystyle S_{0}=0$ (2)
$\displaystyle S_{j}-S_{i}\geq d_{im_{i}}\qquad\forall(i,j)\in E\cup
X_{\bm{m}}$ (3) $\displaystyle S_{i}\geq 0\qquad\forall i\in V,$ (4)

where ${\mathcal{M}}\subseteq\mathbb{N}^{n}$ represents the set of all
possible combinations of activity processing mode selections, and
${\mathcal{X}}_{\bm{m}}$ is the set of all possible sufficient selections for
the choice of processing modes given by $\bm{m}$.

An optimal solution to the instance shown in Figure 1 is given by Figure 2(a),
where the mode choices are shown in bold, and the sufficient selection is
given by $\\{(3,2)\\}$. The worst-case schedule for this optimal solution is
shown in Figure 2(b), where activities 1 and 3 have been delayed to achieve a
worst-case makespan of 15 (note that delaying a combination of activity 1 and
any other activity results in the same worst-case makespan).

(a) Activity mode choices are highlighted in bold and sufficient selection is
given by dashed arc $\\{(3,2)\\}$.

(b) Worst-case schedule corresponding to optimal robust solution, where
activities 1 and 3 have been delayed.

Figure 2: Optimal solution to the example instance from Figure 1.

##  3 A compact formulation

We propose solving the robust MRCPSP using an extended version of the mixed-
integer programming formulation developed by Bold and Goerigk, (2021) for
solving the two-stage adjustable robust RCPSP. This formulation combines the
first and second-stage problems into a single compact formulation and was
shown to significantly outperform the strongest iterative decomposition-based
methods for that problem.

This formulation is constructed by recasting the adversarial subproblem of
determining the worst-case activity durations for a given set of mode choices
and sufficient selection as a longest path problem on an augmented project
network. This directed acyclic graph is formed of $\Gamma+1$ connected copies
of the original project network, with each level being used to account for a
delay to a single activity in the project (a similar construction has also
been applied in Bendotti et al., (2019)). Having reformulated the adversarial
subproblem as a longest-path problem, strong duality can be employed to enable
its insertion it into a formulation for the first-stage problem, and
ultimately arrive at a complete compact formulation for the full problem.
Given that the derivation of this formulation is more or less identical to the
derivation of the corresponding formulation for the robust RCPSP, we omit it
here and instead refer the reader to Bold and Goerigk, (2021).

In the resulting compact formulation, $y_{ij}$ variables are used to define a
complete set of transitive precedences between the project activities that are
formed by the original project precedence constraints and the additional
precedences introduced to resolve resource conflicts, i.e. $\\{(i,j),\,i,j\in
V:y_{ij}=1\\}=T(E\cup X_{\bm{m}})$, where $T(\cdot)$ is used to denote the
transitive closure of a set. Variables $x_{im}$ determine the processing mode
for each activity, whilst resource flow variables $f_{ijk}$ track the amount
of renewable resource $k$ that is transferred from activity $i$ to activity
$j$ upon its completion. The $S_{i\gamma}$ variables are dual variables
associated with the longest-path subproblem, which in this formulation are
used to track the start time of activities under the worst-case activity
durations. Using these variables, the compact formulation for the robust
MRCPSP can be written as

$\displaystyle\min\ $ $\displaystyle S_{n+1,\Gamma}$ (5) s.t. $\displaystyle
S_{00}=0$ (6) $\displaystyle
S_{j\gamma}-S_{i\gamma}\geq\bar{d}_{im}x_{im}-N(1-y_{ij})\qquad\forall(i,j)\in
V^{2},\,\forall m\in M_{i},\,\gamma=0,\dots,\Gamma$ (7) $\displaystyle
S_{j,\gamma+1}-S_{i\gamma}\geq(\bar{d}_{im}+\hat{d}_{im})x_{im}-N(1-y_{ij})$
$\displaystyle\forall(i,j)\in V^{2},\,m\in M_{i},\,\gamma=0,\dots,\Gamma-1$
(8) $\displaystyle y_{ij}=1\qquad\forall(i,j)\in E\cup\\{(n+1,n+1)\\}$ (9)
$\displaystyle y_{ij}+y_{ji}\leq 1\qquad\forall i,j\in V,\,i<j$ (10)
$\displaystyle y_{ij}=y_{ip}+y_{pj}-1\qquad\forall i,j,p\in V,\,i\neq j\neq p$
(11) $\displaystyle f_{ijk}\leq P_{ijk}y_{ij}\qquad\forall(i,j)\in
V^{2},\,i\neq n+1,\,j\neq 0,\,\forall k\in K$ (12) $\displaystyle\sum_{i\in
V\setminus\\{n+1\\}}f_{ijk}=\sum_{m\in M_{j}}r_{jmk}x_{jm}\qquad\forall j\in
V\setminus\\{0\\},\,\forall k\in K$ (13) $\displaystyle\sum_{j\in
V\setminus\\{0\\}}f_{ijk}=\sum_{m\in M_{i}}r_{imk}x_{im}\qquad\forall i\in
V\setminus\\{n+1\\},\,\forall k\in K$ (14) $\displaystyle\sum_{m\in
M_{i}}x_{im}=1\qquad\forall i\in V$ (15) $\displaystyle\sum_{m\in
M_{i}}r^{{}^{\prime}}_{imk}x_{im}\leq R^{{}^{\prime}}_{k}\qquad\forall i\in
V,\,k\in K^{{}^{\prime}}$ (16) $\displaystyle S_{i\gamma}\geq 0\qquad\forall
i\in V,\,\gamma\in 0,\dots,\Gamma$ (17) $\displaystyle
y_{ij}\in\\{0,1\\}\qquad\forall(i,j)\in V^{2}$ (18) $\displaystyle f_{ijk}\geq
0\qquad\forall(i,j)\in V^{2},\,\forall k\in K$ (19) $\displaystyle
x_{im}\in\\{0,1\\}\qquad\forall i\in V,\,m\in M_{i},$ (20)

where $N=\sum_{i\in V}\max_{m\in M_{i}}(\bar{d}_{im}+\hat{d}_{im})$ is an
upper bound on the minimum makespan, and $P_{ijk}=\min\\{\max_{m\in
M_{i}}r_{imk},\,\max_{m\in M_{j}}r_{jmk}\\}$ is the maximum possible flow of
resource $k$ from $i$ into $j$.

Constraints (6)-(8) are the dual constraints corresponding to the longest-path
variables in the adversarial subproblem, and serve to ensure that the activity
start times respect the project precedences as well as any delays to activity
durations. Constraints (9) capture the original project precedence
relationships. Although not required for the correctness of the model,
constraints (10) and (11) are additional transitivity constraints that have
been included because they were shown in Bold and Goerigk, (2021) to provide
significant improvements to the computational performance of the model.
Constraints (12)-(14) are resource flow constraints which ensure that the
transfer of resources between activities follows precedence constraints and
that resources are conserved as they flow into and out of each activity in the
network. Constraints (15) allows only one processing mode to be selected for
each activity. Finally, non-renewable resource constraints are enforced by
(16).

With polynomially many variables and constraints this formulation can be
implemented straightforwardly using standard mathematical optimisation
software such as Gurobi or CPLEX.

##  4 A Benders’ decomposition approach

In this section we outline an alternative approach to solving the robust
MRCPSP based on Benders’ decomposition. A Benders’-type approach for solving
the robust MRCPSP was first presented in Balouka and Cohen, (2021), and as
mentioned previously, this itself was based on the approach for solving the
robust RCPSP used in Bruni et al., (2017).

The main idea behind this approach is to decompose the full problem into its
two stages: 1. a master problem that determines activity processing modes and
resolves resource conflicts, and 2. a subproblem that takes the solution from
the master problem and evaluates it by finding the worst-case makespan for the
resulting network by solving a longest path problem. Since the master problem
does not account for all the problem uncertainty at once, its solution forms a
lower bound to the optimal objective value of the original problem. Meanwhile,
the solution to the subproblem is feasible to the original problem, and
therefore provides an upper bound. These two problems are solved iteratively,
with optimality cuts being added to the master problem each iteration based on
the solution to the subproblem until the lower and upper bounds meet.

After initially implementing the Benders’ algorithm as it is presented in
Balouka and Cohen, (2021), it was discovered that its performance could be
strengthened by replacing the master problem formulation used in that
implementation with a stripped-down version of the compact formulation
(5)-(20) in which the uncertainty is removed. In this section we present our
strengthened implementation of the Benders’ approach for solving the robust
MRCPSP. A comparison of these two Benders’ implementations is included in the
results in Section 5. For the details of the original implementation of the
Benders’ decomposition algorithm for the robust MRCPSP, see Balouka and Cohen,
(2021).

###  4.1 The master problem

The role of the master problem is to determine a choice of activity processing
modes $\bm{m}$, as well as a sufficient selection $X_{\bm{m}}$ to resolve any
resulting resource conflicts. This problem is solved without the direct
consideration of the uncertain activity durations, and instead, uncertainty is
accounted for in the subproblem and communicated back to the master problem
with the use of optimality cuts. Hence, to remove the uncertainty from the
model, (5)-(20) is modified by considering only a single level of the
augmented project network. Using this formulation, the master problem at
iteration $t$ can be written as

$\displaystyle\min\ $ $\displaystyle\eta$ (21) s.t. $\displaystyle\eta\geq
S_{n+1}$ (22) $\displaystyle S_{0}=0$ (23) $\displaystyle
S_{j}-S_{i}\geq\bar{d}_{im}x_{im}-N(1-y_{ij})\qquad\forall(i,j)\in
V^{2},\,\forall m\in M_{i}$ (24)
$\displaystyle\eta\geq\lambda(\bm{x},\bm{y},V^{*\ell})\qquad\forall\ell=1,\dots,t-1$
(25) (9)-(16), (18)-(20) (26) $\displaystyle S_{i}\geq 0\qquad\forall i\in V,$
(27)

where (25) are the optimality cuts generated from the solutions of the
resulting subproblems at each of the previous iterations.

The optimal objective value of the master problem (21)-(27), denoted by
$\eta^{*}$, forms a lower bound to the original robust MRCPSP problem. Note
that for the first iteration, the solution to the master problem corresponds
to an optimal solution to the MRCPSP with nominal activity durations.

###  4.2 The subproblem

The subproblem at iteration $t$ computes the worst-case makespan for the mode
choices and sufficient selection from the master problem at iteration $t$,
denoted by $\bm{m}^{*t}$ and $X_{\bm{m}^{*t}}$ respectively. This is done by
solving a longest-path problem through the extended project network $T(E\cup
X_{\bm{m}^{*t}})$, in which the activity durations (i.e. arc lengths) can be
chosen from the budgeted uncertainty set
${\mathcal{U}}_{\bm{m}^{*t}}(\Gamma)$. This problem can be formulated as

$\displaystyle V^{*t}=$ $\displaystyle\max\sum_{(i,j)\in T(E\cup
X_{\bm{m}^{*t}})}\bar{d}_{im^{*t}_{i}}\alpha_{ij}+\hat{d}_{im^{*t}_{i}}w_{ij}$
(28) $\displaystyle\sum_{(i,n+1)\in T(E\cup X_{\bm{m}^{*t}})}\alpha_{i,n+1}=1$
(29) $\displaystyle\sum_{(0,i)\in T(E\cup X_{\bm{m}^{*t}})}\alpha_{0,i}=1$
(30) $\displaystyle\sum_{(i,j)\in T(E\cup
X_{\bm{m}^{*t}})}\alpha_{ij}-\sum_{(j,i)\in T(E\cup
X_{\bm{m}^{*t}})}\alpha_{ji}=0\qquad\forall i\in V\setminus\\{0,n+1\\}$ (31)
$\displaystyle w_{ij}\leq\xi_{i}\qquad\forall(i,j)\in T(E\cup
X_{\bm{m}^{*t}})$ (32) $\displaystyle
w_{ij}\leq\alpha_{ij}\qquad\forall(i,j)\in T(E\cup X_{\bm{m}^{*t}})$ (33)
$\displaystyle\sum_{i\in V}\xi_{i}\leq\Gamma$ (34)
$\displaystyle\alpha_{ij}\in\\{0,1\\}\qquad\forall(i,j)\in T(E\cup
X_{\bm{m}^{*t}})$ (35) $\displaystyle w_{ij}\geq 0\qquad\forall(i,j)\in
T(E\cup X_{\bm{m}^{*t}})$ (36) $\displaystyle 0\leq\xi_{i}\leq 1\qquad\forall
i\in V.$ (37)

Variables $\alpha_{ij}$ define the longest path through the network, which we
denote as $\pi^{*t}=\\{(i,j),\,i,j\in V:\alpha_{ij}=1\\}$, and has length
$V^{*t}$. Variables $\xi_{i}$ are the activity delay variables, whilst
$w_{ij}$ are used to linearise the formulation. Note that this formulation of
the subproblem is identical to the one implemented by Balouka and Cohen,
(2021).

###  4.3 Optimality cuts

Following the solution to the subproblem, a valid cut is generated and added
to the master problem for the next iteration. This cut simply forces an
alternative solution in the master problem if it is to achieve a better
objective value in the next iteration.

Given the current best lower bound for the original problem, $LB$, the mode
selection from the master problem, $\bm{m}^{*t}$, and the optimal objective
value of the subproblem, $V^{*t}$, the cut at iteration $t$ can be written as

$\displaystyle\eta\geq(V^{*t}-LB)\cdot\sum_{(i,j)\in\pi^{*t}}\bigg{(}1/3(y_{ij}+x_{i,m_{i}^{*t}}+x_{j,m_{j}^{*t}})-(3-y_{ij}-x_{i,m_{i}^{*t}}-x_{j,m_{j}^{*t}})\bigg{)}$
$\displaystyle\hskip 230.46748pt-(V^{*t}-LB)\cdot(|\pi^{*t}|-1)+LB.$ (38)

Balouka and Cohen, (2021) show that this constraint is a valid optimality cut
for the problem, and that the number of these cuts that need to be added to
the master problem before finding an optimal solution is finite.

An overview of the implementation of the Benders’ solution approach outlined
in this section is presented in Algorithm 1.

Algorithm 1 Benders’ decomposition algorithm.

1:Initialise: Set $LB=-\infty$, $UB=+\infty$ and $t=1$.

2:while $UB>LB$ do

3: Solve master problem (21)-(27)

4: Get objective value $\eta^{*t}$, processing modes $\bm{m}^{*t}$ and
precedences $\bm{y}_{\bm{m}^{*t}}$

5: If $\eta^{*t}>LB$, update $LB\leftarrow\eta^{*t}$

6: Solve subproblem (28)-(37)

7: Get objective value $V^{*t}$ and longest path $\pi^{*t}$

8: If $V^{*t}<UB$, update $UB\leftarrow V^{*t}$

9: Add cut (38) to master problem

10: Update $t\leftarrow t+1$

11:end while

12:return $UB$

###  4.4 Example

To demonstrate its implementation, we use the Benders’ decomposition approach
to solve the example shown in Figure 1 with $R_{1}=4$ and $\Gamma=2$. The
algorithm solves this instance in 6 iterations, and the solution information
from the master and subproblem at each of these iterations is shown in Table
1.

The first iteration of the master problem solves the nominal instance,
assuming no delays to the activity durations. This solution opts to schedule
activities 2 and 3 in parallel, which can be achieved by setting $m_{2}=2$,
and the sufficient selection for is given by $\\{(4,5)\\}$. This first
solution is evaluated in the subproblem to have a worst-case makespan of 16.
In the second iteration, having added the first optimality cut, the master
problem finds the solution shown in Figure 2(a). By calculating the schedule
shown in Figure 2(b), the subproblem evaluates the objective value of this
solution to be 15. Although this solution is optimal, the algorithm requires a
further four iterations to prove that this is the case. Note that there is no
need to solve the subproblem in the final iteration since after solving the
master problem and updating $UB$, we have that $LB=UB$.

$t$ | $LB$ | $UB$ | $\eta^{*t}$ | $V^{*t}$ | $\bm{m}^{*t}$ | $\pi^{*t}$
---|---|---|---|---|---|---
1 | 11 | 16 | 11 | 16 | 1,2,1,1,2 | 0,1,2,5,6
2 | 12 | 15 | 12 | 15 | 1,1,1,1,1 | 0,1,3,2,4,6
3 | 12 | 15 | 12 | 15 | 1,1,1,1,1 | 0,1,2,3,4,6
4 | 13 | 15 | 13 | 18 | 1,2,1,1,1 | 0,1,2,5,6
5 | 13 | 15 | 13 | 16 | 1,1,1,2,1 | 0,1,3,4,2,5,6
6 | 15 | 15 | 15 | - | 1,1,1,1,1 | -
Table 1: Solution information at each of the six iterations of the Benders’
algorithm required to solve example instance in Figure 1.

##  5 Computational experiments and results

In this section we compare results from using the compact formulation and the
Benders’ decomposition approach to solve uncertain MRCPSP instances. A
complete set of the raw results used to generate the tables and plots
presented here, in addition to the source code used to implement these
experiments, can be found at https://github.com/boldm1/robust-mrcpsp.

The instances used in this computational study have been created from the
deterministic $j10$, and $j20$ MRCPSP instances from the PSPLIB (Kolisch and
Sprecher, (1997), https://www.om-db.wi.tum.de/psplib/). Note that these are
the same instance sets as used for the experiments in Balouka and Cohen,
(2021). The $j10$ set contains a total of 536 instances each involving 10
activities, and the $j20$ set contains a total of 554 instances each involving
20 activities. We introduce uncertainty into these deterministic instances by
setting the maximum durational deviation for each activity to be
$\hat{d}_{im}=\lfloor 0.7\times\bar{d}_{im}\rfloor$ for each mode $m\in
M_{i}$. These uncertain instances have then been solved using both methods for
a range of robustness levels $\Gamma$. In particular we solve the $j10$
instances for $\Gamma\in\\{0,3,5,7\\}$ and the $j20$ instances for
$\Gamma\in\\{0,5,10,15\\}$.

Both the compact reformulation and Benders’ decomposition approach have been
implemented in Python 3.9.2 and solved using Gurobi 9.0.1 running on a single
core of a 2.30 GHz Intel Xeon CPU. A time limit of 2 hours per instance was
imposed on each of the solution methods.

We begin by observing the effect of the robustness parameter $\Gamma$ on the
average optimal objective values shown in Tables 2(a) and 2(b). The values in
these tables have been computed only over the instances for which an optimal
solution was found for all the values of $\Gamma$ (i.e. all 536 instances in
the $j10$ set, and 477 instances of the $j20$ set). As we would expect, the
solution cost increases in a concave manner as $\Gamma$ increases.

$\Gamma$ | 0 | 3 | 5 | 7
---|---|---|---|---
obj. | 16.84 | 25.34 | 26.35 | 26.46
(a) $j10$

$\Gamma$ | 0 | 5 | 10 | 15
---|---|---|---|---
obj. | 24.61 | 37.89 | 38.69 | 38.69
(b) $j20$

Table 2: Average optimal objective values across instances in the $j10$ and
$j20$ instance sets for different values of $\Gamma$.

Table 3 reports the percentage of instances solved to optimality (%sol.), the
average percentage optimality gap over instances for which a feasible solution
was found (gap), and the average solution time in seconds (sol. time) for the
different choices of $\Gamma$ across the two instance sets, for both the
Benders’ decomposition approach and the compact formulation. Note that if no
optimal solution was found within the time limit by one of the solution
methods, the solution time was recorded as the time limit value of 7200
seconds. Additionally, for the Benders’ approach, the average number of
(completed) iterations (it.) and the average time per (completed) iteration
(it. time) are also reported. The average of the reported values across the
different values for $\Gamma$ are also given for each instance set.

Firstly, the results in Table 3 show that for both methods, the instances tend
to increase in difficulty as $\Gamma$ increases. We can also see that for the
nominal problems, i.e. when $\Gamma=0$, the Benders’ approach has a slight
edge on the compact formulation. This is what we would expect given the
relationship between the Benders’ master problem formulation and the compact
formulation. However, for all the non-zero values of $\Gamma$ across both
instance sets, the compact formulation performs significantly better than the
Benders’ approach, solving a greater proportion of instances with dramatically
reduced computation times.

|  |  | Benders’ |  | Compact formulation
---|---|---|---|---|---
| $\Gamma$ |  | %sol. | gap | its. | it. time | sol. time |  | %sol. | gap | sol. time
$j10$ | 0 |  | 100.0 | 0.00 | 1 | 0.96 | 1.1 |  | 100.0 | 0.00 | 1.8
3 |  | 81.7 | 3.13 | 67 | 3.76 | 1551.4 |  | 100.0 | 0.00 | 5.0
5 |  | 79.7 | 4.20 | 76 | 3.89 | 1688.4 |  | 100.0 | 0.00 | 4.6
7 |  | 79.5 | 4.52 | 78 | 3.98 | 1701.1 |  | 100.0 | 0.00 | 6.5
|  |  | 85.2 | 2.96 | 56 | 3.15 | 1235.5 |  | 100.0 | 0.00 | 4.47
$j20$ | 0 |  | 89.9 | 0.00 | 1 | 171.08 | 885.5 |  | 89.5 | 1.89 | 925.1
5 |  | 50.9 | 10.21 | 220 | 133.32 | 4169.3 |  | 88.6 | 1.87 | 1041.5
10 |  | 50.4 | 10.99 | 225 | 138.49 | 4244.6 |  | 87.9 | 2.58 | 1118.5
15 |  | 49.5 | 11.21 | 216 | 146.26 | 4300.3 |  | 86.3 | 2.91 | 1260.6
|  |  | 60.2 | 8.10 | 165 | 147.28 | 3399.9 |  | 88.1 | 2.31 | 1086.4
Table 3: Comparison of the Benders’ decomposition approach and the compact
reformulation across the $j10$ and $j20$ instance sets and for different
values of $\Gamma$.

Figures 3 and 4 show performance profiles and optimality gap plots for the
compact formulation and both implementations of the Benders’ decomposition
solution approach (Algorithm 1 and Balouka and Cohen, (2021)), across the
$j10$ and $j20$ sets respectively. Note that only the results for the
instances with non-zero values for $\Gamma$ were used to generate these plots,
resulting in a total of 1608 $j10$ instances and 1664 $j20$ instances.

(a) Performance profiles showing percentage of instances with a performance
ratio of within $\tau$. Plotted on a log scale.

(b) Percentage of instances solved to within given optimality gap within the
two-hour time limit.

Figure 3: Comparison of the Benders’ approaches and compact formulation over
instances in the $j10$ set.

(a) Performance profile showing percentage of instances with a performance
ratio of within $\tau$. Plotted on a log scale.

(b) Percentage of instances solved to within given optimality gap within the
two-hour time limit.

Figure 4: Comparison of the Benders’ approaches and compact formulation over
instances in the $j20$ set.

Performance profiles (Dolan and Moré, (2002)) provide a visual comparison of
competing solution approaches using their performance ratios. The performance
ratio of algorithm $a\in\mathcal{A}$ for instance $i\in\mathcal{I}$ is defined
to be

$r_{ia}=\frac{t_{ia}}{\min_{a\in\mathcal{A}}t_{ia}},$

where $t_{ia}$ is the time required to solve instance $i$ using algorithm $a$.
If method $a$ is unable to solve an instance $i$ within the 2-hour time limit,
then $r_{ia}=R$, where $R\geq\max_{i,\,m}r_{im}$. The performance profiles in
Figures 3(a) and 4(a) show the percentage of instances that have a performance
ratio within a factor of $\tau$ of the best algorithm. These are plotted using
a log scale for clarity. The y-intercepts of each method give the percentage
of instances for which that method found the optimal solution in the fastest
time, whereas the right-most value gives the overall percentage of instances
that were solved to optimality within the time limit by that method.

These performance profiles show that whenever an instance was able to be
solved to optimality by either solution approach, the compact formulation was
always the faster method. If we specifically compare the solution times of the
compact formulation with the stronger of the two Benders’ implementations,
across the instances in $j10$ for which both methods found the optimal
solution, the average solution time of the compact formulation (1.4s) was
almost 200 times faster than for the Benders’ approach (283.5s). When both
methods found the optimal solution for instances in the $j20$ set, the average
solution time of the compact formulation (13.7s) was almost 100 times faster
than for the Benders’ approach (1304.5s).

Figures 3(b) and 4(b) show the percentage of instances solved by each method
to within a given optimality gap within the 2-hour time limit. These plots
serve as a continuation of the performance profiles beyond just the instances
that were solved to optimality. Summarising the data from these plots across
both the $j10$ and $j20$ instance sets, the Balouka and Cohen, (2021) Benders’
implementation solves 55.1% of instances to optimality and finds feasible
solutions for a further 35.6% of instances. Our Benders’ implementation solves
65.0% of instances and finds feasible solution solutions for a further 30.0%
of instances. The compact formulation on the other hand finds a feasible
solution to every instance, solving 93.1% these to optimality.

The results presented here show the clear improvements to the Benders’
algorithm afforded by amending the master problem to use the formulation
(21)-(27). More significantly however, these results demonstrate the complete
dominance of the compact formulation over both Benders’ methods.

##  6 Conclusions

The work presented in this paper extends the compact mixed-integer programming
formulation first introduced by Bold and Goerigk, (2021), for application to
the two-stage adjustable robust MRCPSP with uncertain activity durations. The
computational performance of this formulation has been examined over a total
of 3270 uncertain MRCPSP instances of varying size and difficulty, and
compared against an improved version of the current state-of-the-art for
solving this problem, based on a Benders’ decomposition approach. The improved
Benders’ approach is the result of replacing the original master problem with
a new formulation based on a simplified version of the compact formulation we
present for the full problem.

Results presented in Section 5 show that the compact formulation completely
dominates the enhanced Benders’ approach, solving over 43% more instances to
optimality, and doing so with dramatically reduced computation times. In
addition to these strong computational improvements, the proposed compact
formulation has the significant added benefit of being simpler to implement
than the iterative Benders’ approach.

Despite these strong results, the instances used in these experiments contain
only up to 20 activities. To enable the solving of larger scale instances, the
development of heuristic solution approaches should be a primary focus of
future research on this problem.

## Acknowledgements

The authors are grateful for the support of the EPSRC-funded (EP/L015692/1)
STOR-i Centre for Doctoral Training.

## References

  * Artigues et al., (2013) Artigues, C., Leus, R., and Talla Nobibon, F. (2013).  Robust optimization for resource-constrained project scheduling with uncertain activity durations.  Flexible Services and Manufacturing Journal, 25(1):175–205.
  * Balouka and Cohen, (2021) Balouka, N. and Cohen, I. (2021).  A robust optimization approach for the multi-mode resource-constrained project scheduling problem.  European Journal of Operational Research, 291(2):457–470.
  * Bartusch et al., (1988) Bartusch, M., Möhring, R. H., and Radermacher, F. J. (1988).  Scheduling project networks with resource constraints and time windows.  Annals of Operations Research, 16(1):199–240.
  * Bendotti et al., (2019) Bendotti, P., Chrétienne, P., Fouilhoux, P., and Pass-Lanneau, A. (2019).  The anchor-robust project scheduling problem.  Preprint hal-02144834.
  * Bertsimas and Sim, (2004) Bertsimas, D. and Sim, M. (2004).  The price of robustness.  Operations Research, 52(1):35–53.
  * Bold and Goerigk, (2021) Bold, M. and Goerigk, M. (2021).  A compact reformulation of the two-stage robust resource-constrained project scheduling problem.  Computers & Operations Research, 130:105232.
  * Bruni et al., (2017) Bruni, M. E., Pugliese, L. D. P., Beraldi, P., and Guerriero, F. (2017).  An adjustable robust optimization model for the resource-constrained project scheduling problem with uncertain activity durations.  Omega, 71:66–84.
  * Bruni et al., (2018) Bruni, M. E., Pugliese, L. D. P., Beraldi, P., and Guerriero, F. (2018).  A computational study of exact approaches for the adjustable robust resource-constrained project scheduling problem.  Computers & Operations Research, 99:178–190.
  * Dolan and Moré, (2002) Dolan, E. D. and Moré, J. J. (2002).  Benchmarking optimization software with performance profiles.  Mathematical Programming, 91(2):201–213.
  * Kolisch and Sprecher, (1997) Kolisch, R. and Sprecher, A. (1997).  PSPLIB - A project scheduling problem library: OR Software - ORSEP Operations Research Software Exchange Program.  European Journal of Operational Research, 96(1):205–216.


# Clique immersion in graphs without a fixed bipartite graph

Hong Liu, Guanghui Wang, Donglei Yang Extremal Combinatorics and Probability
Group (ECOPRO), Institute for Basic Science (IBS), Daejeon, South Korea,
Email<EMAIL_ADDRESS>supported by the Institute for Basic Science
(IBS-R029-C4).School of Mathematics, Shandong University, Jinan, China, Email:
<EMAIL_ADDRESS>supported by Natural Science Foundation of China (11631014)
and Shandong University Multidisciplinary Research and Innovation Team of
Young Scholars.Correspondence: Data Science Institute, Shandong University,
Shandong, China, Email<EMAIL_ADDRESS>supported by the China Postdoctoral
Science Foundation (2021T140413), Natural Science Foundation of China
(12101365) and Natural Science Foundation of Shandong Province (ZR2021QA029).

###### Abstract

A graph $G$ contains $H$ as an _immersion_ if there is an injective mapping
$\phi:V(H)\rightarrow V(G)$ such that for each edge $uv\in E(H)$, there is a
path $P_{uv}$ in $G$ joining vertices $\phi(u)$ and $\phi(v)$, and all the
paths $P_{uv}$, $uv\in E(H)$, are pairwise edge-disjoint. An analogue of
Hadwiger’s conjecture for the clique immersions by Lescure and Meyniel, and
independently by Abu-Khzam and Langston, states that every graph $G$ contains
$K_{\chi(G)}$ as an immersion. We prove that for any constant $\varepsilon>0$
and integers $s,t\geq 2$, there exists $d_{0}=d_{0}(\varepsilon,s,t)$ such
that every $K_{s,t}$-free graph $G$ with $d(G)\geq d_{0}$ contains a clique
immersion of order $(1-\varepsilon)d(G)$. This implies that the above-
mentioned conjecture is asymptotically true for graphs without a fixed
complete bipartite graph.

##  1 Introduction

A graph $H$ is a _minor_ of another graph $G$ if $H$ can be obtained from $G$
via vertex deletions, edge deletions and edge contractions. A conjecture of
Hadwiger [8] states that every graph $G$ with $\chi(G)\geq t$ contains $K_{t}$
as a minor. This conjecture is widely open for $\chi(G)\geq 7$; the case
$\chi(G)=5$ is equivalent to the celebrated Four-Color Theorem and the case
$\chi(G)=6$ was solved by Robertson, Seymour and Thomas [22]. A graph $H$ is a
_topological minor_ of another graph $G$ if there is an injective mapping
$\phi:V(H)\rightarrow V(G)$ such that for each edge $uv\in E(H)$, there is a
path $P_{uv}$ in $G$ joining vertices $\phi(u)$ and $\phi(v)$, and all the
paths $P_{uv}$, $uv\in E(H)$, are pairwise internally vertex-disjoint. A
stronger conjecture proposed by Hajós in 1940’s [9] states that every graph
$G$ contains $K_{\chi(G)}$ as a topological minor. However, this conjecture is
known to be false in general: Catlin [2] disproved this conjecture for all
$\chi(G)\geq 7$. It is also natural to consider graphs with given average
degree. In this direction, Kostochka [13] and independently, Thomason [23]
proved that average degree $d(G)=\Omega(t\sqrt{\log t})$ in a graph $G$ forces
$K_{t}$ as a minor, and this bound is optimal. This remained the best order of
magnitude for Hadwiger’s conjecture until very recent breakthroughs by Norin,
Postle and Song [19] and Postle [20].

In this paper, we consider immersions, first introduced by Nash-Williams [18].
Given two graphs $G$ and $H$, we say $G$ contains an $H$-_immersion_ if there
exists an injective mapping $\phi:V(H)\rightarrow V(G)$ such that for each
edge $uv\in E(H)$, there is a path $P_{uv}$ in $G$ connecting $\phi(u)$ and
$\phi(v)$; and all the paths $P_{uv}$, $uv\in E(H)$, are pairwise edge-
disjoint. We call the vertices $\\{\phi(v)\mid v\in V(H)\\}$ the _branch_
vertices of the immersion. As a weakening of topological minor, the immersion
relation requires paths to be pairwise edge-disjoint rather than vertex-
disjoint. Although graph minors and graph immersions are incomparable,
Robertson and Seymour [21] showed that graphs are well-quasi-ordered by
immersion, analogous to their celebrated graph minors project. An immersion
variant of Hadwiger’s conjecture was proposed by Lescure and Meyniel [16]
111They in fact conjectured a stronger statement that the $K_{t}$-immersion
can be embedded so that every path $P_{uv}$, $uv\in E(K_{t})$ is internally
vertex disjoint from the set of branch vertices. in $1989$, and independently,
by Abu-Khzam and Langston [1] in $2003$.

######  Conjecture 1.1.

_[1, 16]_ Every graph $G$ with $\chi(G)\geq t$ contains $K_{t}$ as an
immersion.

Conjecture 1.1 has seen more success than the Hadwiger’s Conjecture: the cases
$t\leq 4$ are trivial, while the cases $5\leq t\leq 7$ are proved by DeVos,
Kawarabayashi, Mohar and Okamura [5]. Here for any $t\in\mathbb{N}$, we use
$f(t)$ to denote the least integer such that every graph $G$ with
$\delta(G)\geq f(t)$ contains $K_{t}$ as an immersion. In [5], they showed
that $f(t)=t-1$ holds for any $t\in\\{5,6,7\\}$, It is easy to see that
$f(t)\geq t-1$. For $t\geq 8$, there are infinitely many constructions [3, 4]
showing that $f(t)\geq t$. A linear upper bound on $f(t)$ is due to DeVos,
Dvořák, Fox, McDonald, Mohar and Scheide [4], showing that $f(t)\leq 200t$,
and it was then improved to $11t+7$ by Dvořák and Yepremyan [6], who asked
whether for all $t\geq 8$, $f(t)=t$. Building on the work of [6], Gauthier, Le
and Wollan [7] showed that $f(t)\leq 7t+7$.

Our work is motivated by a result of Kühn and Osthus [15]. They proved that
for any fixed bipartite graph $H$, Hadwiger’s conjecture holds strongly for
any $H$-free graph $G$ by constructing a clique minor of order polynomially
larger than $d(G)$. Note that here and throughout the paper, by $H$-free we
mean that there is no subgraph in $G$ that is isomorphic to $H$. Improved
bounds on the order of clique minor in $H$-free graphs for more general
bipartite graphs $H$ were later obtained by Krivelevich and Sudakov [14] and
Norin, Postle and Song [19].

Our main result reads as follows. It in particular implies that Conjecture 1.1
is asymptotically true if we forbid any fixed complete bipartite graph.

######  Theorem 1.2.

Given any positive constant $\varepsilon$ and integers $s,t\geq 2$, there
exists $d_{0}=d_{0}(\varepsilon,s,t)$ such that every $K_{s,t}$-free graph $G$
with $d(G)\geq d_{0}$ contains a clique immersion of order
$(1-\varepsilon)d(G)$.

The bound above is asymptotically optimal as $G$ could be $d$-regular. It
would be interesting to improve on the additive error term.

Our approach differs from previous works on immersions in [4, 6, 7] which
generally reduce the problem on embedding clique immersions to a dense
eulerian graph via suppressing vertices and use some list coloring arguments.
Our proof adopts a more direct embedding approach, making use of certain
expander and builds on the techniques developed in the work of Liu and
Montgomery [17] on embedding clique subdivisions. In [17], to embed large
clique subdivisions in dense expander, a key idea is to build many unit
structures by finding vertices with large boundaries. Then the arguments often
reduce to greedily connecting the units with vertex-disjoint paths. We are
attempting this approach to immersions which boils down to embedding edge-
disjoint paths. Unlike in [17] where the problem is harder for dense
expanders, the bulk of the work in our paper is to handle sparse expanders. In
sparse expanders, one can still adapt the approach in [17] to obtain a clique
immersion of order linear in $d$. As the expansion is sublinear, if a small
constant portion of neighbors of a vertex is used, then the vertex can still
expand well. To embed $K_{(1-o(1))d}$-immersion in sparse expanders, we
essentially need vertices that can expand past a relatively large set of
vertices even after deleting ninety-nine percent of its incident edges.
However the sublinear expansion is not strong enough to guarantee the
expansion of any such vertex. To overcome this issue, we instead use an idea
from the work of Haslegrave, Kim and Liu [10] to find many vertex-disjoint
subexpanders and grow a vertex in each subexpander robustly until it reaches
large enough size to enjoy further expansion in the main expander (see Section
2.2 for a more elaborate sketch of the proof).

The rest of the paper will be organized as follows. In Section 2, we introduce
some necessary notions and tools whilst outline the proof of our main result.
We divide the main proof into two cases depending on the density of our
expander. Sections 3 and 4 are devoted to embedding large clique immersions in
dense and sparse expanders, respectively.

##  2 Preliminaries and notation

For a set of vertices $X\subseteq V(G)$, denote its _external neighbourhood_
by $N_{G}(X):=\\{u\in V(G)\setminus X:uv\in E(G)\mbox{ for some }v\in X\\}$.
Furthermore, denote by $\partial_{G}(X)$ the _edge boundary_ of $X$, i.e.
$E_{G}[X,V(G)\setminus X]$. Define $G-X$ to be the induced subgraph of $G$ on
$V(G)\setminus X$ and for a subgraph $F$, use $G\setminus F$ to denote the
spanning subgraph with $E(F)$ removed. Throughout the paper, the _length_ of a
path always denotes the number of edges in the path. For two sets
$A,B\subseteq V(G)$, an $(A,B)$-path is path $P$ with two endpoints separately
lying in $A$ and $B$ such that $P$ does not have any interior vertices in $A$
or $B$. Moreover, the _distance_ between $A$ and $B$ is the minimum length of
an $(A,B)$-path and if $A\cap B\neq\emptyset$, then the distance is zero. For
each $r\in\mathbb{N}$, the $r$-_th sphere_ around $X$, denoted by
$N^{r}_{G}(X)$, is the set of vertices with distance exactly $r$ from $X$. So
$N_{G}^{0}(X)=X$ and $N_{G}^{1}(X)=N_{G}(X)$. Denote by $B_{G}^{r}(X)$ the
_ball_ of radius $r$ around $X$, i.e. $B_{G}^{r}(X)=\cup_{0\leq i\leq
r}N_{G}^{i}(X)$. Throughout the proof, all logarithms are in the natural
basis.

Let $G$ be a $K_{s,t}$-free graph on $n$ vertices for some $2\leq s\leq t$ and
$d(G)=d$. Then a classical result of Kővári, Sós and Turán [11] on the Turán
number of complete bipartite graphs tells that $e(G)=O(n^{2-1/s})$ and thus we
have

$n/d=\Omega(d^{\frac{1}{s-1}}).$ (1)

We will also make use of the following bipartite version.

######  Lemma 2.1.

_[11]_ For integers $s,t$ with $2\leq s\leq t$, there exists a constant $c$
such that the following holds. Let $G=(V_{1},V_{2},E)$ be a $K_{s,t}$-free
bipartite graph with $|V_{1}|=n_{1},|V_{2}|=n_{2}$. Then

$e(G)\leq cn_{1}^{1-1/s}n_{2}.$

###  2.1 Robust sublinear expander

For $\varepsilon_{1}>0$ and $k>0$, let $\rho(x)$ be the function

$\displaystyle\rho(x)=\rho(x,\varepsilon_{1},k):=\left\\{\begin{tabular}[]{ l
c r }$0$&\mbox{ \leavevmode\nobreak\ if } $x<k/5$\\\
$\varepsilon_{1}/\log^{2}(15x/k)$&$\mbox{ \leavevmode\nobreak\
\leavevmode\nobreak\ if }\leavevmode\nobreak\ x\geq k/5$,\\\
\end{tabular}\right.$ (4)

where, when it is clear from context we will not write the dependency on
$\varepsilon_{1}$ and $k$ of $\rho(x)$. Note that $\rho(x)\cdot x$ is
increasing for $x\geq k/2$. In [12], Komlós and Szemerédi introduced a notion
of $(\varepsilon_{1},k)$-_expander_ $G$ in which for any subset $X\subseteq
V(G)$ with $k/2\leq|X|\leq|V(G)|/2$, we have
$|N_{G}(X)|\geq\rho(|X|)\cdot|X|$. In this paper, we shall utilize the
following robust version recently developed by Haslegrave, Kim and Liu [10].

######  Definition 2.2.

[10] A graph $G$ is an _$(\varepsilon_{1},k)$ -robust-expander_ if for all
subsets $X\subseteq V(G)$ of size $k/2\leq|X|\leq|V(G)|/2$ and any subgraph
$F\subseteq G$ with $e(F)\leq d(G)\cdot\rho(|X|)|X|$, we have that

$\displaystyle|N_{G\setminus F}(X)|\geq\rho(|X|)\cdot|X|.$ (5)

We will use the following version of expander lemma in [10], which states that
every graph contains a robust expander with almost the same average degree.

######  Lemma 2.3.

_[10]_ Let $C>30$,
$0<\varepsilon_{1}\leq\frac{1}{10C},0<\varepsilon_{2}<1/2,d>0,\eta=C\varepsilon_{1}/\log
3$ and $\rho(x)=\rho(x,\varepsilon_{1},\varepsilon_{2}d)$ be as in (4). Then
every graph $G$ with $d(G)=d$ has a subgraph $G^{\prime}$ that is an
$(\varepsilon_{1},\varepsilon_{2}d)$-robust-expander with
$d(G^{\prime})\geq(1-\eta)d$ and $\delta(G^{\prime})\geq d(G^{\prime})/2$.

The following small diameter property is the key property of the expanders
that we will repeatedly make use of. It roughly says that we can find a
relatively short path between any two large sets, avoiding a small set of
vertices or edges.

######  Lemma 2.4 (Robust small diameter, Lemma 2.3 in [10]).

Let $0<\varepsilon_{1},\varepsilon_{2}<1$ and $G$ be an $n$-vertex
$(\varepsilon_{1},\varepsilon_{2}d)$-robust-expander. Given two sets
$X_{1},X_{2}\subseteq V(G)$ of size $x\geq\varepsilon_{2}d/2$, let $Y$ be a
vertex set of size at most $\rho(x)x/4$ and $F$ be a subgraph with at most
$d(G)\rho(x)x$ edges. Then there is an $(X_{1},X_{2})$-path of length at most
$\frac{2}{\varepsilon_{1}}\log^{3}(15n/\varepsilon_{2}d)$ in $(G\setminus
F)-Y$.

The following is our main lemma, which finds in a robust expander a clique
immersion of asymptotically optimal size.

######  Lemma 2.5.

Let $0<\varepsilon_{1}\leq
1/400,0<\varepsilon_{2}<1/2,\eta\geq\max\\{\frac{40\varepsilon_{1}}{\log
3},5\varepsilon_{2}\\}$ and $2\leq s\leq t$. Then there exists $d_{0}$
satisfying the following. Let $G$ be a $K_{s,t}$-free
$(\varepsilon_{1},\varepsilon_{2}d)$-robust-expander of order $n$ and
$d(G)=d\geq d_{0}.$ Then $G$ contains a clique immersion of order at least
$(1-9\eta)d$.

Theorem 1.2 immediately follows from Lemmas 2.3 and 2.5.

###### Proof of Theorem 1.2..

Given any constant $\varepsilon>0$, we choose $C=40$,
$\varepsilon_{1}=\varepsilon\log 3/500$,
$\varepsilon_{2}<\min\\{\varepsilon/50,1/2\\}$ and $\eta=\varepsilon/10$. Then
$\eta\geq\eta^{\prime}:=40\varepsilon_{1}/\log 3$ and Lemma 2.3 applied to $G$
with $\varepsilon_{1},\varepsilon_{2},C=40,\eta^{\prime}$, gives a subgraph
$G^{\prime}$ that is an $(\varepsilon_{1},\varepsilon_{2}d)$-robust-expander
with $d(G^{\prime})\geq(1-\eta^{\prime})d(G)\geq(1-\eta)d(G)$. By applying
Lemma 2.5 to $G^{\prime}$ with
$\varepsilon_{1},\varepsilon_{2},\eta=\varepsilon/10$, we obtain a clique
immersion of order at least $(1-9\eta)d(G^{\prime})\geq(1-\varepsilon)d(G)$ in
$G^{\prime}$, which is also an immersion in $G$. ∎

###  2.2 Outline of the proof

Here we sketch an overview of the proof of Lemma 2.5. We divide the proof into
two cases according to the density $d$ of our expander. For the dense case
$d\geq\log^{200s}n$ in Section 3, we adapt the approach of Liu and Montgomery
[17] on embedding clique subdivisions in dense expanders, in which we
construct a specific unit structure (see Definition 3.1) for embedding a
$K_{d-o(d)}$-immersion. The main work is then to $(1)$ find in a dense
expander $d-o(d)$ mutually edge-disjoint units with distinct centers (see
Lemma 3.2); $(2)$ and connect these units with pairwise edge-disjoint paths so
as to obtain a desired clique immersion.

For the proof of the sparse case, we divide the proof into two cases in
Section 4.3 depending on the number of vertices of sufficiently large degree.
Before that, we first deal with a special case when the maximum degree is
bounded, which is covered by Lemma 4.1. Then we denote $Z_{1}$ as the set of
high degree vertices (to be defined later in Section 4.3). The case
$|Z_{1}|\geq d$ is easy to handle and the strategy here is to greedily connect
those vertices in $Z_{1}$ (see Claim 4.5 in Section 4.3.1). Towards the case
when $G$ has less than $d$ such vertices, we instead focus our attention to
the subgraph $G^{\prime}:=G-Z_{1}$. Using the assumption of
$K_{s,t}$-freeness, we obtain that $G^{\prime}$ has almost the same average
degree with $G$ (see Claim 4.6).

Note that the subgraph $G^{\prime}$ might not have the expansion property for
small sets of vertices as in $G$, whereas we essentially need vertices that
locally expand well for embedding a $K_{d-o(d)}$-immersion. To handle this, we
then show in Section 4.3.2 that there exist in $G^{\prime}$ many dense
$(\varepsilon_{1},\varepsilon_{2}d)$-robust-expanders
$F_{1},F_{2},\cdots,F_{d}$ which are relatively small and pairwise far apart
from each other (Claim 4.7). Here we iteratively make use of Lemma 2.3 and
Lemma 2.1 to guarantee the existence of a dense expander one by one.

Anchoring at these small dense subexpanders, we first grow a vertex $v_{i}$ in
each subexpander $F_{i}$ robustly into a small ball $K_{i}$ which has size
relatively larger than $|Z_{1}|$ even after deleting ninety-nine percent of
incident edges of $v_{i}$ (See Claim 4.8 in Section 4.3.3). Then by further
expanding (subsets of) each $K_{i}$ into two large balls in $G^{\prime}$, we
follow the strategy in the proof of Lemma 4.1 to finish the embedding of a
desired clique immersion.

##  3 Embedding immersions in dense expanders

In this section, we prove Lemma 2.5 assuming in addition that
$d\geq\log^{200s}n$. Throughout the rest of this paper, we write

$\displaystyle\ell=(1-5\eta)d,\quad\ell^{\prime}=(1-4\eta)d,\quad
m:=\frac{2}{\varepsilon_{1}}\log^{3}\left(\frac{15n}{\varepsilon_{2}d}\right).$
(6)

Note that by (1), when $d$ is sufficiently large, then $n/d$ and also $m$ are
sufficiently large, and

$\displaystyle n/d\geq m^{200}\quad\mbox{ and }\quad d\geq m^{50s}.$ (7)

Also, for sufficiently large $d$, since $\rho(x)$ is decreasing in the
interval $[\varepsilon_{2}d/2,n]$, we have that for every
$\varepsilon_{2}d/2\leq x\leq n$,

$\displaystyle\rho(x)\geq\rho(n)\geq\frac{1}{m}.$ (8)

######  Definition 3.1.

Given integers $h_{1},h_{2},h_{3}>0$, an _$(h_{1},h_{2},h_{3})$ -unit_ $F$ is
a graph consisting of a center $v$, $h_{1}$ vertex-disjoint stars $S(u_{i})$
centered at $u_{i}$, each of size $h_{2}$, and edge-disjoint
$(v,u_{i})$-paths, $i=1,\ldots,h_{1}$, each of length at most $h_{3}$.
Moreover, the set of interior vertices in all $(v,u_{i})$-paths is disjoint
from all leaves in $\bigcup_{i=1}^{h_{1}}S(u_{i})$. By the _exterior_ of the
unit, denoted by $\mathsf{Ext}(F)$, we mean the set of all leaves in
$\bigcup_{i=1}^{h_{1}}S(u_{i})$. We call each $(v,u_{i})$-path a _branch_ of
$F$ and each edge in the star $S(u_{i})$ a _pendant_ edge.

Figure 1: $(h_{1},h_{2},h_{3})$-unit: $h_{1}$ vertex-disjoint stars $S(u_{i})$
each of size $h_{2}$; $h_{1}$ edge-disjoint $(v,u_{i})$-paths each of length
at most $h_{3}$. Here $u_{i}$ may appear in a $(v,u_{j})$-path for some $j\neq
i$.

The following lemma guarantees a large collection of edge-disjoint units with
distinct centers.

######  Lemma 3.2.

For each
$0<\varepsilon_{1},\varepsilon_{2}<1,\eta\geq\max\\{\frac{40\varepsilon_{1}}{\log
3},5\varepsilon_{2}\\}$ and $2\leq s\leq t$, there exists $C>0$ such that the
following holds for all $n$ and $d$ with $d\geq\log^{200s}n$ and $n/d\geq C$.
If $G$ is an $n$-vertex $K_{s,t}$-free
$(\varepsilon_{1},\varepsilon_{2}d)$-robust-expander with $d(G)=d$, then $G$
contains $\ell^{\prime}$ pairwise edge-disjoint
$(\ell^{\prime},m^{5},2m)$-units $F_{1},\ldots,F_{\ell^{\prime}}$ with
distinct centers $v_{1},\ldots,v_{\ell^{\prime}}$, where
$\ell^{\prime}=(1-4\eta)d$ and
$m=\frac{2}{\varepsilon_{1}}\log^{3}\left(\frac{15n}{\varepsilon_{2}d}\right)$.

We first see how to construct a $K_{\ell}$-immersion, $\ell=(1-5\eta)d$, using
Lemma 3.2.

###### Proof of Lemma 2.5 when $d\geq\log^{200s}n$..

Given constants $\varepsilon_{1},\varepsilon_{2}$ and integers $t\geq s\geq
2$, we choose $d_{0}$ to be sufficiently large with foresight. Then by (1) and
(6), we obtain that $m$ is also sufficiently large. Let
$F_{1},\ldots,F_{\ell^{\prime}}$ be the $(\ell^{\prime},m^{5},2m)$-units
guaranteed by Lemma 3.2, with distinct centers
$v_{1},\ldots,v_{\ell^{\prime}}$, where $\ell^{\prime}=(1-4\eta)d$. Now we
pick instead, for $\ell^{\prime\prime}=(1-4.5\eta)d$, a subfamily
$\\{F_{1},\ldots,F_{\ell^{\prime\prime}}\\}$ of the
$(\ell^{\prime},m^{5},2m)$-units and then connect pairs of these
$\ell^{\prime\prime}$ centers in the following way.

  1. A1

Greedily connect as many pairs $(v_{i},v_{j})$ of centers as possible through
an $(\mathsf{Ext}(F_{i}),\mathsf{Ext}(F_{j}))$-path $P_{i,j}$ of length at
most $m$.

  2. A2

In each $F_{i}$, a star is _occupied_ if a leaf of it was previously used as
an endpoint in an $(\mathsf{Ext}(F_{i}),\mathsf{Ext}(F_{k}))$-path for some
$k\neq i$.

  3. A3

Let $\mathsf{Ext}(F_{i})$ and $\mathsf{Ext}(F_{j})$ be the current pair to
connect. Then an $(\mathsf{Ext}(F_{i}),\mathsf{Ext}(F_{j}))$-path shall avoid
using

     * •

any leaf of the occupied stars in $F_{i}$ or $F_{j}$ as an endpoint;

     * •

edges that are used in previous connections;

     * •

all centers $v_{p}$, $p\in[\ell^{\prime\prime}]$ and ;

     * •

edges that are in branches of units.

In the process, a star in a unit is _over-used_ if at least half of its
pendant edges were used in previous connections. Discard a unit if it has at
least $\eta d/4$ over-used stars. Note that an
$(\mathsf{Ext}(F_{i}),\mathsf{Ext}(F_{j}))$-path together with the
corresponding branches within $F_{i}$ and $F_{j}$ form a $(v_{i},v_{j})$-path
of length at most $6m$. Thus the total number of edges used in all connections
is at most

$\displaystyle{\ell^{\prime\prime}\choose 2}\cdot 6m\leq 3d^{2}m,$ (9)

while the total number of edges in branches of all units is at most

$\displaystyle\ell^{\prime\prime}\ell^{\prime}2m\leq 2d^{2}m.$ (10)

Thus, in each connection, we avoid using a set of at most $5d^{2}m$ edges and
a set of at most $\ell^{\prime\prime}$ centers
$v_{i},i\in[\ell^{\prime\prime}]$ in A3.

We claim that there are at least $\ell=(1-5\eta)d$ units survived (were not
discarded), say $F_{1},\ldots,F_{\ell}$. Indeed, all units are edge-disjoint
and each unit discarded has at least $\eta d/4\cdot m^{5}/2$ of its edges used
in all connections. Hence by (9), the total number of units discarded is at
most

$\frac{3d^{2}m}{\eta d\cdot m^{5}/8}<\eta d/2\leq\ell^{\prime\prime}-\ell,$

where the first inequality follows as $m$ is sufficiently large.

We now claim that we can connect all pairs of the units
$F_{1},\ldots,F_{\ell}$ in A1. Indeed, let $\mathcal{P}$ be a maximal
collection of paths $P_{i,j}$ in A1 between different units $F_{i}$ with
$i\in[\ell]$. Assume for contradiction that there exists
$\\{i,j\\}\in{[\ell]\choose 2}$ such that there is no
$(\mathsf{Ext}(F_{i}),\mathsf{Ext}(F_{j}))$-path in $\mathcal{P}$. Note that
each unit is connected with less than $\ell^{\prime\prime}$ other units in A1.
Thus each $F_{i}$ (or $F_{j}$) has at least
$\ell^{\prime}-\ell^{\prime\prime}=\eta d/2$ stars not occupied in A2, among
which there are at least $\eta d/4$ stars that are not over-used. Thus,
$v_{i}$ and $v_{j}$ can still reach a subset of at least

$\eta d/4\cdot m^{5}/2\geq dm^{4}=:x$

vertices in $\mathsf{Ext}(F_{i})$ and $\mathsf{Ext}(F_{j})$, denoted by
$L_{i},L_{j}$ respectively. Recall that in A3, by (9) and (10), we need to
avoid a set $P$ of at most $5d^{2}m\leq d(G)\cdot\rho(x)\cdot x$ edges and at
most $d\leq\rho(x)\cdot x/4$ centers in each connection. Hence, Lemma 2.4
applied to $G$ with

$X_{1}=L_{i},\leavevmode\nobreak\ X_{2}=L_{j},\leavevmode\nobreak\
Y=\\{v_{1},v_{2},\ldots,v_{\ell^{\prime\prime}}\\},\leavevmode\nobreak\ F=P$

gives a desired $(L_{i},L_{j})$-path of length at most $m$, a contradiction to
the maximality in A1. Finally, notice that extending these paths in
$\mathcal{P}$ from the exterior to the corresponding centers of the units
yields edge-disjoint $(v_{i},v_{j})$-paths, for all
$\\{i,j\\}\in{[\ell]\choose 2}$, which yields a desired $K_{\ell}$-immersion.
∎

###  3.1 Proof of Lemma 3.2: finding units

Using the $K_{s,t}$-free condition, we first show that after deleting a small
set of arbitrary vertices, the remaining subgraph still has large average
degree.

######  Proposition 3.3.

For integers $n,s,t$ and constants $\eta$ with $0<\eta<1,t\geq s\geq 2$, there
exists $m_{0}\in\mathbb{N}$ such that the following holds for every $m\geq
m_{0}$. If $G$ is an $n$-vertex $K_{s,t}$-free graph with $d(G)=d\geq
m^{50s}$, then for any subset $Z\subseteq V(G)$ with $|Z|\leq dm^{50}$, we
have $d(G-Z)\geq d-\eta d$.

###### Proof.

We may assume that $|Z|\geq\eta d$ as otherwise it is trivial that $d(G-Z)\geq
d-\eta d$. Consider the bipartite subgraph $G_{1}:=G[Z,V(G)\setminus Z]$.
Since $G_{1}$ is $K_{s,t}$-free, by Lemma 2.1, $e(G_{1})\leq
c|Z|^{1-1/s}(n-|Z|)\leq c(dm^{50})^{1-1/s}n\leq\frac{cdn}{m^{50/s}}$, for some
constant $c>0$, where the last inequality follows as $d\geq m^{50s}$. Also,
$e(G[Z])\leq\gamma|Z|^{2-1/s}\leq\gamma(dm^{50})^{2-1/s}\leq\frac{\gamma
dn}{(dm^{50})^{1/s}}$, for some $\gamma>0$, where the last inequality follows
from (1) and the assumption that $d\geq m^{50s}$. Thus

$d(G-Z)=\frac{nd-2e(G_{1})-2e(G[Z])}{n-|Z|}\geq
d-\frac{2cd}{m^{50/s}}-\frac{\gamma d}{d^{1/s}m^{50/s}}\geq d-\eta d,$

where the last inequality follows as long as $m$ is sufficiently large (with
respect to $\eta$). ∎

Now we are ready to prove Lemma 3.2.

###### Proof of Lemma 3.2.

Let $\mathcal{F}=\\{F_{1},F_{2},\ldots,F_{k}\\}$ be a maximal collection of
pairwise edge-disjoint $(\ell^{\prime},m^{5},2m)$-units as desired . Let $Z$
be the centers of all units in $\mathcal{F}$ and $B$ be their edge set.
Suppose for contrary that $|k|<\ell^{\prime}$. Let $G^{\prime}:=(G-Z)\setminus
B$, i.e. the subgraph on vertex set $V(G)\setminus Z$ with edges in $B$
removed. Next we shall find in $G^{\prime}$ one more
$(\ell^{\prime},m^{5},2m)$-unit to reach a contradiction.

By (7), we have $|B|\leq\ell^{\prime}\cdot 2dm^{5}\leq
d^{2}m^{6}\leq\frac{1}{2}\eta d(n-|Z|)$. Together with Proposition 3.3, we
have

$d(G^{\prime})\geq d(G-Z)-2|B|/(n-|Z|)\geq d-2\eta d.$

Then we claim that we can find in $G^{\prime}$ vertex-disjoint stars, say
$S(v_{i})$ centered at some $v_{i}$, $i=1,\ldots,m^{10}$, each of size
$d-3\eta d$ and $S(u_{j})$ centered at $u_{j}$, $j=1,\ldots,dm^{15}$, each of
size $m^{10}$. Indeed, let $U$ be the vertex set of a maximal collection
$\mathcal{S}$ of vertex-disjoint of stars constructed as above. If
$\mathcal{S}$ is not as desired, then $|U|\leq dm^{30}\leq
d(G^{\prime})m^{50}$ and Proposition 3.3 applied to $G^{\prime}$ with $Z=U$
guarantees that $d(G^{\prime}-U)\geq(1-\eta)d(G^{\prime})\geq d-3\eta d$. This
allows us to find one more star as desired, contradicting with the maximality
of $\mathcal{S}$.

We use $L(v_{i})$ to denote the set of all leaves in each star $S(v_{i})$,
$i\in\\{1,\ldots,m^{10}\\}$. Let $V=\\{v_{1},\ldots,v_{m^{10}}\\}$. Now we
shall use these vertex-disjoint stars to construct a new
$(\ell^{\prime},m^{5},2m)$-unit in $G^{\prime}$ as follows.

  1. B1

Connect as many pairs $(v_{i},u_{j})$ as possible through an
$(L(v_{i}),u_{j})$-path of length at most $m$, such that there is at most one
path between any pair.

  2. B2

For each $v_{i}$, a leaf $v\in L(v_{i})$ is _occupied_ if it is previously
used as an endpoint of a path in B1.

  3. B3

Let $(v_{i},u_{j})$ be the current pair to connect. Then an
$(L(v_{i}),u_{j})$-path shall avoid using

     * •

any leaf occupied in $L(v_{i})$ as an endpoint;

     * •

edges in $\bigcup_{p=1}^{m^{10}}S(v_{p})$, $\bigcup_{q=1}^{dm^{15}}S(u_{q})$
and $B$;

     * •

all vertices in $Z\cup V$.

######  Claim 3.4.

There is a vertex $v_{i}$ connected to at least $s=(\ell^{\prime}+\eta d/2)$
distinct centers $u_{j}$.

###### Proof.

Suppose to the contrary that each $v_{i}$ is connected to less than $s$
centers $u_{j}$. Then the number of vertices used in all paths is at most
$d\cdot m^{10}\cdot m=dm^{11}.$ Thus, there are at least $dm^{15}/2$
$u_{j}$-stars that are completely vertex-disjoint from all those paths, and
there are at least $dm^{15}/2>dm^{9}=:x$ available centers from $u_{j}$-stars,
say $U^{\prime}$. Inside each $v_{i}$-star, there are at least $d(G)-3\eta
d-s=\eta d/2$ leaves not occupied. Thus, there is a set $V^{\prime}$ of at
least $\eta d/2\cdot m^{10}>x$ leaves not occupied from all $v_{i}$-stars.

Recall that there are at most $d^{2}m^{6}$ edges in $B$, at most $dm^{11}$
edges used in all paths, at most $dm^{10}$ edges in $v_{i}$-stars and at most
$dm^{25}$ edges in $u_{j}$-stars. Thus, in total, we avoid at most
$d^{2}m^{7}\leq d(G)\cdot\rho(x)\cdot x$ edges and at most $|Z|+|V|\leq
d+m^{10}\leq\rho(x)\cdot x/4$ vertices. Therefore, by Lemma 2.4 with
$X_{1}=U^{\prime},X_{2}=V^{\prime},Y=Z\cup V,F=B$, we can find a path of
length at most $m$ between $U^{\prime}$ and $V^{\prime}$ in $G^{\prime}$,
resulting in one more pair of $v_{i},u_{j}$ connected, a contradiction. ∎

Let $v_{i}$, $u_{1},u_{2},\cdots,u_{s}$ be the centers guaranteed by Claim 3.4
with all $(v_{i},u_{j})$-paths pairwise edge disjoint. If the set of interior
vertices in all $(v_{i},u_{j})$-paths is disjoint from
$\bigcup_{j=1}^{s}S(u_{j})$, then they form a desired unit in $G^{\prime}$.
Otherwise, we discard a star $S(u_{j})$ if at least half of its leaves are
used in $(v_{i},{u_{j}})$-paths. We claim that there are at least
$\ell^{\prime}$ $u_{j}$-stars left, say
$S(u_{1}),\ldots,S(u_{\ell^{\prime}})$. Indeed, recall that all $u_{j}$-stars
are vertex-disjoint and the number of vertices in all all
$(v_{i},u_{j})$-paths is at most $sm$. Thus the number of stars discarded is
at most

$\frac{sm}{m^{10}/2}\leq\eta d/2\leq s-\ell^{\prime}.$

Therefore, each $u_{j}$-stars left has at least $m^{10}/2\geq m^{5}$ leaves
that are not used in a $(v_{i},u_{j^{\prime}})$-path for any
$j^{\prime}\in[s]$. These stars, together with the corresponding paths to
$v_{i}$, form a desired unit in $G^{\prime}$.

∎

##  4 Embedding immersions in sparse expanders

For the proof of the sparse case, we first deal with a special case when the
maximum degree is somewhat bounded. Formally it is stated as follows.

######  Lemma 4.1.

Let $0<\varepsilon_{1}\leq
1/400,0<\varepsilon_{2}<1/2,\eta\geq\max\\{\frac{40\varepsilon_{1}}{\log
3},5\varepsilon_{2}\\}$ and $2\leq s\leq t$. Then there exists $d_{0}$ such
that the following holds for any $d\geq d_{0}$. Let $G$ be an $n$-vertex
$K_{s,t}$-free $(\varepsilon_{1},\varepsilon_{2}d)$-robust-expander with
$d(G)=d<\log^{200s}n$ and $\Delta(G)\leq d\log^{120}n.$ Then $G$ contains a
clique immersion of order at least $\ell^{\prime}=(1-4\eta)d$.

For the proof of this case, we need two technical lemmas which ensure that a
small ball can expand robustly even after deleting a small set of vertices or
edges.

###  4.1 Technical lemmas: robust expansion of a ball

We first need the following lemma in [10], which ensures that a large set of
vertices expands well even after deleting a small set of vertices.

######  Lemma 4.2 (Proposition 3.5 in [10]).

Let $0<\varepsilon_{1}\leq 1/400,0<\varepsilon_{2}<1/2$, and $G$ be an
$n$-vertex $(\varepsilon_{1},\varepsilon_{2}d)$-robust-expander with $d(G)=d$.
If $X,Y\subseteq V(G)$ are sets such that
$|X|=x\geq\varepsilon_{2}d,|Y|\leq\rho(x)x/4$, then for every $i\leq\log n$,

$|B^{i}_{G-Y}(X)|\geq\exp(\sqrt[4]{i}).$

To state the second technical lemma, we need the following notion of
consecutive shortest paths.

######  Definition 4.3.

For a set $X\subseteq W$ of vertices, the paths $P_{1},\cdots,P_{q}$ are
_edge-disjoint consecutive shortest paths from $X$ within $W$_ in $G$ if the
following holds. For each $i\in[q]$, $P_{i}$ is a shortest path from $X$ to a
vertex in $W$ in the graph $G[W]\setminus\bigcup_{j\in[i-1]}E(P_{j})$.

######  Lemma 4.4.

Let $0<\varepsilon_{1}\leq
1/400,0<\varepsilon_{2}<1/2,\eta\geq\max\\{\frac{40\varepsilon_{1}}{\log
3},5\varepsilon_{2}\\}$. Then there exists
$d_{0}:=d_{0}(\varepsilon_{1},\varepsilon_{2})$ such that the following holds
for all $d\geq d_{0}$. Suppose $G$ is an $n$-vertex
$(\varepsilon_{1},\varepsilon_{2}d)$-expander with $d(G)=d$ and $K,Z$ are
disjoint sets of vertices with

$|K|<n/2,\leavevmode\nobreak\ |Z|\leq|K|\rho(|K|)/4,\leavevmode\nobreak\
|N_{G-Z}(K)|\geq\ell^{\prime}+\varepsilon_{2}d,$

where $\ell^{\prime}=(1-4\eta)d$. Let $P_{1},P_{2},\cdots,P_{q}$ be edge-
disjoint consecutive shortest paths from $K$ within $G-Z$ such that
$q<\ell^{\prime}$ and denote $E=\bigcup_{j\in[q]}E(P_{j})$. Then for any
positive integers $t\in\mathbb{N}$ and $D$ with $D\leq n/2$, we have

$|B^{t}_{(G-Z)\setminus E}(K)|\geq\min\left\\{D,\leavevmode\nobreak\
|K|\cdot\left(1+\frac{\varepsilon_{1}}{2\log^{2}(15D/\varepsilon_{2}d)}\right)^{t-1}\right\\}.$

###### Proof.

Let $G^{\prime}=G-Z$. For each $0\leq p\leq t-1$, let
$X_{p}:=B^{p}_{G^{\prime}\setminus E}(K)$ and denote by $E_{p}$ the set of
edges in $E$ that go from the set $X_{p}$ to $N_{G^{\prime}}(X_{p})$. Then we
have

$\displaystyle N_{G^{\prime}\setminus E}(X_{p})=N_{G^{\prime}\setminus
E_{p}}(X_{p}).$ (11)

Note that only the first $p+2$ vertices of each $P_{i}$ can intersect
$N_{G^{\prime}}(X_{p})$ for otherwise a shorter path can be found,
contradicting the choices $P_{1},\ldots,P_{q}$. Therefore $|E_{p}\cap
E(P_{i})|\leq p+1$ for each $i\in[q]$ and it follows that for each $0\leq
p\leq t-1$,

$\displaystyle|E_{p}|\leq q(p+1)<\ell^{\prime}(p+1).$ (12)

We first observe that for all $p\in[t-1]$,
$|X_{p}|\geq|X_{1}|\geq|N_{G^{\prime}}(K)|-|E_{0}|\geq\varepsilon_{2}d$, where
we use (12) and the hypothesis of the lemma for the last inequality. Next we
claim that for all $p\in[t-1]$, it holds that

$\displaystyle|X_{p}|\cdot\rho(|X_{p}|)>p+1,$ (13)

and we shall prove this later. Indeed, if this holds, then we have that
$|E_{p}|<\ell^{\prime}(p+1)<d(G)\cdot|X_{p}|\cdot\rho(|X_{p}|)$ and it follows
from the expansion property as in (5) that

$\displaystyle|N_{G\setminus E_{p}}(X_{p})|\geq|X_{p}|\cdot\rho(|X_{p}|).$
(14)

Since $|X_{p}|\geq|K|$ and $x\rho(x)$ is increasing in $x$, we obtain from the
assumption on $|Z|$ that

$|Z|\leq|K|\rho(|K|)/4<|X_{p}|\cdot\rho(|X_{p}|)/2,$

and it follows from (11) and (14) that

$\displaystyle|N_{G^{\prime}\setminus E}(X_{p})|=|N_{G^{\prime}\setminus
E_{p}}(X_{p})|\geq|N_{G\setminus
E_{p}}(X_{p})|-|Z|\geq|X_{p}|\cdot\rho(|X_{p}|)/2.$ (15)

We may assume $|X_{p}|\leq D$ for all $1\leq p\leq t-1$, otherwise we are
done. Now we have

$\displaystyle|N_{G^{\prime}\setminus E}(X_{p})|$
$\displaystyle\geq|X_{p}|\cdot\rho(|X_{p}|)/2=|X_{p}|\cdot\frac{\varepsilon_{1}}{2\log^{2}(\frac{15|X_{p}|}{\varepsilon_{2}d})}$
$\displaystyle\geq|X_{p}|\cdot\frac{\varepsilon_{1}}{2\log^{2}\left(15D/\varepsilon_{2}d\right)},$

where the equality follows as $\varepsilon_{2}d\leq|X_{p}|\leq D$. Thus by
definition, it follows that $|X_{p+1}|=|B^{1}_{G^{\prime}\setminus
E}(X_{p})|=|X_{p}|+|N_{G^{\prime}\setminus
E}(X_{p})|\geq|X_{p}|\left(1+\frac{\varepsilon_{1}}{2\log^{2}(15D/\varepsilon_{2}d)}\right)$
for each $p\in[t-1]$, and thus

$|X_{t}|\geq|K|\cdot\left(1+\frac{\varepsilon_{1}}{2\log^{2}(15D/\varepsilon_{2}d)}\right)^{t-1}.$

Now it remains to prove (13), which we will show by induction on $p$. Let
$p_{0}$ be the least integer such that for each $p\geq p_{0}$, we have
$p^{2}/4\cdot\rho(p^{2}/4)\geq p+1$. Then $p_{0}=O(\sqrt{d})$. The base cases
$1\leq p\leq p_{0}$ easily follow since
$|X_{p}|\cdot\rho(|X_{p}|)\geq|X_{1}|\cdot\rho(|X_{p}|)>\varepsilon_{2}d\cdot\rho(\varepsilon_{2}d)>p_{0}+1\geq
p+1$ holds whenever $d$ is sufficiently large. Suppose $p>p_{0}$, and assume
that (13) holds for all $p^{\prime}$ with $1\leq p^{\prime}\leq p-1$. Then
$|E_{p^{\prime}}|<\ell^{\prime}(p^{\prime}+1)<d(G)\cdot|X_{p^{\prime}}|\cdot\rho(|X_{p^{\prime}}|)$,
which together with the expansion property from (15) implies that

$\displaystyle|X_{p^{\prime}+1}|$
$\displaystyle\geq|X_{p^{\prime}}|+|X_{p^{\prime}}|\cdot\rho(|X_{p^{\prime}}|)/2$
$\displaystyle\geq|X_{p^{\prime}}|+(p^{\prime}+1)/2.$

Therefore, $|X_{p}|\geq|X_{1}|+\frac{2+3+\cdots+p}{2}\geq p^{2}/4$ and

$|X_{p}|\cdot\rho(|X_{p}|)\geq p^{2}/4\cdot\rho(p^{2}/4)\geq p+1,$

where the last inequality follows since $p>p_{0}$. This completes the proof of
(13). ∎

###  4.2 Almost regular sparse expander: proof of Lemma 4.1

Now we are ready to prove Lemma 4.1. The proof idea is to choose vertices, say
$v_{1},v_{2},\cdots,v_{\ell^{\prime}}$, that are pairwise far apart to be the
branch vertices of our clique immersion. To achieve this, we grow two nested
balls around each $v_{i}$, one inner ball $B^{r}(v_{i})$ and one outer ball
$B^{\kappa+r}(v_{i})$ for integers $r\ll\kappa$. Then we try to connect all
pairs $v_{i},v_{j}$ using a shortest path between the outer balls around them
while avoiding (1) all edges in the inner balls of other branch vertices, that
is, $\bigcup_{p\neq i,j}E(B^{r}(v_{p}))$; (2) all edges used in previous
connections. Using the robust expansion guaranteed by the Lemma 4.2 and Lemma
4.4, we are able to regrow new inner and outer balls around each $v_{i}$ to be
large enough to enable us to connect $v_{i}$ to more branch vertices.

###### Proof of Lemma 4.1.

Let $\kappa=\lceil\log n/(800s\log\log n)\rceil$, $r=\lceil(\log\log
n)^{5}\rceil$ and $d_{0}$ be a sufficiently large integer. First, we claim
that there are at least $d$ vertices of degree at least $d(G)-2\eta d$ which
are pairwise a distance at least $3\kappa+1$ far apart. Indeed, letting $L$ be
the set of vertices with degree at least $d(G)-2\eta d$, as $\Delta(G)\leq
d\log^{120}n$, we see that

$d(G)n<(d(G)-2\eta d)(n-|L|)+d\log^{120}n\cdot|L|,$

implying that $|L|>n/\log^{121}n$. Let $Y$ be a maximal set of vertices in $L$
which are pairwise a distance at least $3\kappa+1$ apart. Suppose to the
contrary $|Y|<d$. Since $d<\log^{200s}n$ and $\Delta(G)\leq d\log^{120}n$, we
have that

$|B^{3\kappa}(Y)|<2d\Delta(G)^{3\kappa}<\log^{700s\kappa}n<n^{7/8}<n/\log^{121}n,$

where the last inequality follows as $d_{0}$, also $n$, is sufficiently large.
Thus there exists $v\in L\setminus B^{3\kappa}(Y)$, contradicting the
maximality of $Y$.

Let then $v_{1},v_{2},\cdots,v_{\ell^{\prime}}$ be such vertices in $Y$, which
will serve as the branch vertices of the clique immersion. By choice, all the
balls $B^{\kappa}_{G}(v_{i})$, $i\in[\ell^{\prime}]$, are pairwise vertex
disjoint. Let $I\subseteq\binom{[\ell^{\prime}]}{2}$ be a maximal subset for
which we can find paths $P_{e},e\in I$, so that the following hold.

  1. C1

For each $\\{i,j\\}\in I$, $P_{ij}$ is a $(v_{i},v_{j})$-path with length at
most $2\log^{4}n$.

  2. C2

For distinct $e,e^{\prime}\in I$, the paths $P_{e}$ and $P_{e^{\prime}}$ are
edge disjoint.

  3. C3

For each $e\in I$ and $i\notin e$, $E(B^{r}_{G}(v_{i}))$ and $E(P_{e})$ are
disjoint.

  4. C4

For each $i\in[\ell^{\prime}]$, the subcollection $P_{e}$, $e\in I$ with $i\in
e$, form edge-disjoint consecutive shortest paths from $v_{i}$ within
$B_{G}^{r}(v_{i})$.

If $I=\binom{[\ell^{\prime}]}{2}$, then by C2, we have a
$K_{\ell^{\prime}}$-immersion with branch vertices
$v_{1},v_{2},\cdots,v_{\ell^{\prime}}$. Suppose there exists some
$\\{i,j\\}\in\binom{[\ell^{\prime}]}{2}\setminus I$. Let $W=\bigcup_{e\in
I}E(P_{e})$. Then by C1 and C2, we have

$|W|<\binom{\ell^{\prime}}{2}\cdot 2\log^{4}n\leq d^{2}\log^{4}n.$

By C4, we can apply Lemma 4.4 on $G$ with $t=r,\leavevmode\nobreak\
D=d^{2}\log^{7}n,\leavevmode\nobreak\ K=\\{v_{i}\\},\leavevmode\nobreak\
Z=\varnothing$ and $E=\bigcup\limits_{i\in e\in I}E(P_{e})$ to get that each
inner ball robustly maintains size

$|B^{r}_{G\setminus W}(v_{i})|\geq\min\left\\{D,\leavevmode\nobreak\
|K|\cdot\left(1+\frac{\varepsilon_{1}}{2\log^{2}(15D/\varepsilon_{2}d)}\right)^{r-1}\right\\}\geq
d^{2}\log^{7}n.$

Furthermore, by Lemma 4.2 with $X=B^{r}_{G\setminus W}(v_{i})$ and
$Y=\bigcup_{e\in I}V(P_{e})$, we have

$|B^{\kappa+r}_{G\setminus
W}(v_{i})|\geq|B^{\kappa}_{G-Y}(X)|\geq\exp(\sqrt[4]{\kappa})\geq\exp(\sqrt[5]{\log
n})=:x.$

Similarly $|B^{\kappa+r}_{G\setminus W}(v_{j})|\geq x$. Let
$W_{i,j}=W\cup(\bigcup_{p\neq i,j}E(B^{r}_{G}(v_{p})))$, that is, the set of
all edges that are either used in some connection or are in some inner ball of
other branch vertices $v_{p}$. As we chose the vertices $v_{i}$ to be pairwise
at least a distance $3\kappa+1>2\kappa+2r$ apart, all the outer balls
$B^{\kappa+r}_{G\setminus W}(v_{i})$ are pairwise vertex-disjoint. Note that

$|W_{i,j}|\leq|W|+\Delta(G)\cdot
2(1-4\eta)d\cdot\Delta(G)^{r}<d(G)\cdot\rho(x)x.$

Therefore, Lemma 2.4 applied to $G$ with $X_{1}=B^{\kappa+r}_{G\setminus
W}(v_{i}),X_{2}=B^{\kappa+r}_{G\setminus W}(v_{j})$ and $F=W_{i,j}$, gives a
($B^{\kappa+r}_{G\setminus W}(v_{i}),B^{\kappa+r}_{G\setminus W}(v_{j})$)-path
in $G\setminus W_{i,j}$ with length at most $m\leq\log^{4}n$, which can be
extended, within the balls $B^{\kappa+r}_{G\setminus W}(v_{i})$ and
$B^{\kappa+r}_{G\setminus W}(v_{j})$, into a $(v_{i},v_{j})$-path. Thus, if we
let $P_{ij}$ be a shortest $v_{i},v_{j}$-path in $G\setminus W_{i,j}$, then
$P_{ij}$ has length at most $\log^{4}n+2(\kappa+r)\leq 2\log^{4}n$. The path
$P_{ij}$, together with all $P_{e},e\in I$, satisfies the conditions C1–C4
above, contradicting the maximality of $I$. ∎

###  4.3 Finishing the proof of Lemma 2.5

This subsection is devoted to finishing the proof of Lemma 2.5 when
$d<\log^{200s}n$. As sketched in Section 2.2, we divide the proof into two
cases depending on the number of vertices of relatively large degree. In
particular, let $Z_{1}=\\{v\in V(G)\mid d(v)\geq dm^{3}\\}$ be the set of high
degree vertices. We first deal with the case that $|Z_{1}|\geq d$ (see Claim
4.5). If $|Z_{1}|<d$, then we show in Claim 4.6 that the subgraph
$G^{\prime}:=G-Z_{1}$ still has large average degree and we focus our
attention to $G^{\prime}$ which additionally has small maximum degree. We then
find in $G^{\prime}$ a collection of small
$(\varepsilon_{1},\varepsilon_{2}d)$-robust-expanders
$F_{1},F_{2},\cdots,F_{d}$ which are pairwise far apart in $G^{\prime}$ (see
Claim 4.7). In Section 4.3.3, we first grow, inside each subexpander $F_{i}$,
a vertex $v_{i}$ robustly into a small ball $K_{i}$, called _kernel_ (See
Claim 4.8). In this case, each $K_{i}$, locally maintains certain robust
expansion property inside $F_{i}$. Moreover, each kernel has large enough size
so as to enjoy further expansion in the original expander $G$. Then Section
4.3.4 is devoted to building a desired clique immersion by further expanding
(subsets of) each kernel into two large balls in $G^{\prime}$, and here we
follow the strategy in the proof of Lemma 4.1.

####  4.3.1 Bounding the size of $Z_{1}$

The following claim builds a large clique immersion with many vertices of
relatively large degree. Recall that $Z_{1}=\\{v\in V(G)\mid d(v)\geq
dm^{3}\\}$.

######  Claim 4.5.

If $|Z_{1}|\geq d$, then $G$ contains a $K_{d}$-immersion.

###### Proof.

Let $v_{1},v_{2},\cdots,v_{d}$ be distinct vertices in $Z_{1}$. We shall
construct a $K_{d}$-immersion with all $v_{i}$ as branch vertices in the
following way, where we let $N_{i}=N_{G}(v_{i})$ for $i\in[d]$ and
$I=\\{\\{i,j\\}\in\binom{[d]}{2}\mid v_{i}v_{j}\notin E(G)\\}$.

  1. D1

Greedily connect as many pairs $v_{i},v_{j}$ with $\\{i,j\\}\in I$ as possible
through an $(N_{i},N_{j})$-path of length at most $m$;

  2. D2

Let $(N_{i},N_{j})$ be the current pair to connect. Then avoid using edges
that are used in previous connections and all other vertices $v_{p}$, $p\neq
i,j$.

Note that an $(N_{i},N_{j})$-path together with the corresponding incident
edges forms a $(v_{i},v_{j})$-path, say $P_{i,j}$, of length at most $m+2<2m$.
Thus the total number of edges used in all connections is at most ${d\choose
2}\cdot 2m\leq d^{2}m$. It remains to show that there exist, for all pairs
$\\{i,j\\}\in I$, pairwise edge-disjoint paths $P_{i,j}$ as above. Indeed,
throughout the process, each $v_{i}$ always has at least $dm^{3}-d\geq
dm^{3}/2$ incident edges which are not used in all previous paths. Thus, each
$v_{i}$ can still reach a set of at least $dm^{3}/2$ neighbors in $N_{i}$,
denoted by $N_{i}^{\prime}$. Let $x:=dm^{3}/2$. Then there are at most
$d^{2}m\leq d(G)\cdot\rho(x)\cdot x$ edges and exactly $d\leq\rho(x)\cdot x/4$
vertices we need to avoid in each connection. Thus any $\\{i,j\\}\in I$, by
Lemma 2.4 applied with $X_{1}=N_{i}^{\prime},X_{2}=N_{j}^{\prime},Y=Z_{1}$ and
$F$ being the set of edges used in all previous paths, there exists an
$(N_{i},N_{j})$-path of length at most $m$ as desired. ∎

Thus, it remains to consider the case $|Z_{1}|<d$. The following claim
guarantees that the subgraph $G-Z_{1}$ still has large average degree, which
allows us to restrict our attention to the subgraph $G-Z_{1}$.

######  Claim 4.6.

$d(G-Z_{1})\geq d(G)-\eta d$.

###### Proof.

We may assume that $|Z_{1}|\geq\frac{\eta d}{2}$, otherwise we are done. It
suffices to show that $e(G[Z_{1}])+e(Z_{1},V(G)-Z_{1})\leq\eta dn/2$. Indeed,
it is easy to see that $e(G[Z_{1}])\leq|Z_{1}|^{2}=o(dn)$ because
$d<\log^{200s}n$. Also, by $K_{s,t}$-freeness, Lemma 2.1 implies that
$e(Z_{1},V(G)\setminus Z_{1})=O(d^{1-1/s}n)=o(dn)$. ∎

####  4.3.2 Finding small dense expanders in $G-Z_{1}$

Let $G^{\prime}=G-Z_{1}$. Then Claim 4.6 tells that $d(G^{\prime})\geq
d(G)-\eta d$. We now proceed to find small expanders of large average degree
that are pairwise far apart from each other in $G^{\prime}$. Recall that
$\kappa=\lceil\log n/(800s\log\log n)\rceil$. Let $\mathcal{F}$ be a maximal
family of subgraphs in $G^{\prime}$ satisfying the following.

  1. E1

Each $F\in\mathcal{F}$ is an $(\varepsilon_{1},\varepsilon_{2}d)$-robust-
expander with $d(F)\geq(1-3\eta)d$.

  2. E2

For distinct $F,F^{\prime}\in\mathcal{F}$, $B_{G^{\prime}}^{\kappa}(V(F))\cap
B_{G^{\prime}}^{\kappa}(V(F^{\prime}))=\varnothing$.

For each $F\in\mathcal{F}$, let $n_{F}=|F|$,
$m_{F}=\frac{2}{\varepsilon_{1}}\log^{3}\left(\frac{15n_{F}}{\varepsilon_{2}d}\right)$.
If $d(F)\geq\log^{200s}n_{F}$ or $\Delta(F)\leq d\log^{120}n_{F}$, then by the
proof of the dense case in Section $3$, or by Lemma 4.1, we have a clique
immersion of order at least $(1-5\eta)d(F)\geq(1-9\eta)d$, finishing the
proof. Thus we may assume that for each $F\in\mathcal{F}$,

$d(F)<\log^{200s}n_{F},\quad\Delta(G^{\prime})\geq\Delta(F)\geq
d\log^{120}n_{F}.$

Recall that $\Delta(G^{\prime})\leq dm^{3}\leq d\log^{12}n$, therefore

$\exp(\sqrt[200s]{d/2})\leavevmode\nobreak\ \leq\leavevmode\nobreak\
n_{F}\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \exp(\sqrt[10]{\log n}).$
(16)

######  Claim 4.7.

It holds that $|\mathcal{F}|\geq d$.

###### Proof.

Otherwise, let $U=\bigcup_{F\in\mathcal{F}}B_{G^{\prime}}^{2\kappa}(V(F))$.
Then

$|U|\leq|\mathcal{F}|\cdot
2\max_{F\in\mathcal{F}}n_{F}\cdot\Delta(G^{\prime})^{2\kappa}\leq
d\exp(\sqrt[10]{\log n})(dm^{3})^{2\kappa}<n/m^{4}$

and it follows that $d(G^{\prime}-U)\geq d(G^{\prime})-2|U|\cdot
dm^{3}/n\geq(1-2\eta)d$. Lemma 2.3 implies that $G^{\prime}-U$ contains an
$(\varepsilon_{1},\varepsilon_{2}d)$-robust-expander $F^{\prime}$ with
$d(F^{\prime})\geq(1-3\eta)d$, which, by choice, is far from all expanders in
$\mathcal{F}$ at a distance of at least $2\kappa+1$, contradicting the
maximality of $\mathcal{F}$. ∎

####  4.3.3 Kernels in subexpanders

As shown in Claim 4.7, $\mathcal{F}$ contains at least $d$ expanders, say
$F_{1},F_{2},\cdots,F_{d}$. Since each $F_{i}$ satisfies
$d(F_{i})\geq(1-3\eta)d$, we can choose distinct vertices
$v_{1},v_{2},\cdots,v_{d}$ as the branch vertices such that $v_{i}\in
V(F_{i})$ and $d_{F_{i}}(v_{i})\geq(1-3\eta)d,i\in[d]$. Note that for
sufficiently large $d$, by (16), each small expander $F_{i}$ has at least
$\exp(\sqrt[200s]{d/2})\geq d^{2}$ vertices. For each $v_{i}$, we shall show
that, it expands robustly in $F_{i}$ as follows.

######  Claim 4.8.

Let $P_{1},P_{2},\cdots,P_{q}$ be edge-disjoint consecutive shortest paths
from $v_{i}$ in $F_{i}$ for any $q<(1-4\eta)d$ and denote
$E=\bigcup_{j\in[q]}E(P_{j})$. Then it holds that $|B^{s}_{F_{i}\setminus
E}(v_{i})|\geq d^{2}$ for any integer $s\geq\log^{4}d$.

###### Proof.

To see this, as
$d_{F_{i}}(v_{i})\geq(1-3\eta)d\geq\ell^{\prime}+\varepsilon_{2}d$, by
applying Lemma 4.4 with $G=F_{i}$, $t=\log^{4}d$, $D=d^{2},K=\\{v_{i}\\}$ and
$Z=\varnothing$, we have for large $d$ that

$|B^{t}_{F_{i}\setminus E}(v_{i})|\geq\min\left\\{D,\leavevmode\nobreak\
\left(1+\frac{\varepsilon_{1}}{2\log^{2}(15D/\varepsilon_{2}d)}\right)^{t-1}\right\\}\geq
d^{2}.$

∎

For each $i\in[d]$ and $s=\log^{4}d$, we call $K_{i}=B^{s}_{F_{i}}(v_{i})$ the
_kernel_ for $v_{i}$. In Claim 4.8, we see that the vertex $v_{i}$ locally
expand robustly in $F_{i}$. Recall that $r=\lceil(\log\log n)^{5}\rceil$. By
E2, we observe that all balls $B^{r}_{G^{\prime}}(K_{i})$ are pairwise
disjoint.

######  Claim 4.9.

Let $K^{\prime}\subseteq K_{i}$ be a subset of size at least $d^{2}$ and
$P_{1},P_{2},\cdots,P_{q}$ be edge-disjoint consecutive shortest paths from
$K^{\prime}$ within $B^{r}_{G^{\prime}}(K^{\prime})$ in $G^{\prime}$ such that
$q<\ell^{\prime}$ and denote $E=\bigcup_{j\in[q]}E(P_{j})$. Then
$|B^{r}_{G^{\prime}\setminus E}(K^{\prime})|\geq d^{2}\log^{7}n.$

Indeed, such $K^{\prime}$ satisfies $|K^{\prime}|\cdot\rho(|K^{\prime}|)/4\geq
d>|Z_{1}|$ and then $N_{G^{\prime}}(K^{\prime})\geq
d\geq\ell^{\prime}+\varepsilon_{2}d$. Therefore, Claim 4.9 follows from Lemma
4.4 applied to $G$ with $t=r,D=d^{2}\log^{7}n,K=K^{\prime}$ and $Z=Z_{1}$.

####  4.3.4 Building a clique immersion

We are now ready to build a clique immersion by iteratively finding edge
disjoint paths connecting all pairs of branch vertices
$v_{1},v_{2},\cdots,v_{\ell^{\prime}}$. To do this, we will further expand
each kernel $K_{i}$ in two stages (to $B_{G^{\prime}}^{r}(K_{i})$ and then
$B_{G^{\prime}}^{\kappa+r}(K_{i})$ as depicted in Figure 2).

Figure 2: Each $v_{i}$ is surrounded by three layers: the kernel
$K_{i}=B^{s}_{F_{i}}(v_{i})$ for $s=\log^{4}d$, the inner ball
$B^{r}_{G^{\prime}}(K_{i})$ (the orange one) and the outer ball
$B^{\kappa+r}_{G^{\prime}}(K_{i})$.

By property E2, all the balls $B^{\kappa}_{G^{\prime}}(K_{i})$ are pairwise
disjoint, $i\in[\ell^{\prime}]$. Let $I\subset\binom{[\ell^{\prime}]}{2}$ be a
maximal subset for which we can find pairwise edge-disjoint paths $P_{e},e\in
I$, so that

  1. F1

for each $e=\\{i,j\\}\in I$, $P_{e}$ is a $(v_{i},v_{j})$-path with length at
most $2\log^{4}n$;

  2. F2

for each $e\in I$, $P_{e}$ is disjoint from the ball
$B^{r}_{G^{\prime}}(K_{i})$ for any $i\notin e$;

  3. F3

for each $i\in[\ell^{\prime}]$, the subcollection $P_{e}$, $e\in I$ with $i\in
e$, form edge-disjoint consecutive shortest paths from $v_{i}$ within $K_{i}$,
and $P_{e}-K_{i}$, $e\in I$ with $i\in e$, are edge-disjoint consecutive
shortest paths from $K_{i}$ within $B_{G^{\prime}}^{r}(K_{i})$.

We may assume there is $\\{i,j\\}\in\binom{[\ell^{\prime}]}{2}\setminus I$ for
otherwise all paths $P_{e}$, $e\in I$, would form a desired clique immersion
with $v_{1},v_{2},\cdots,v_{\ell^{\prime}}$ as branch vertices. We will reach
a contradiction by finding a $(v_{i},v_{j})$-path that is short and
additionally avoids all the edges used in previous connections and all
vertices in the inner balls of other branch vertices $v_{p},p\neq i,j$ as in
F2.

Let $W=\bigcup_{e\in I}E(P_{e})$ and $U=\bigcup_{e\in I}V(P_{e})$, i.e. the
sets of edges and vertices used in all previous connections, respectively.
Then $|W|,|U|\leq d^{2}\log^{4}n$. By F1, F2 and F3, Claim 4.8 implies that
for $i\in[\ell^{\prime}]$, $|B^{s}_{F_{i}\setminus W}(v_{i})|\geq d^{2}.$ Let
$K_{i}^{\prime}=B^{s}_{F_{i}\setminus W}(v_{i})$, $i\in[\ell^{\prime}]$. Then
it follows from F2, F3 and Claim 4.9 that $|B^{r}_{G^{\prime}\setminus
W}(K_{i}^{\prime})|\geq d^{2}\log^{7}n$.

Next, by Lemma 4.2 with $X=B^{r}_{G^{\prime}\setminus
W}(K_{i}^{\prime}),Y=(U\setminus\\{v_{i}\\})\cup Z_{1}$, we have

$|B^{\kappa+r}_{G^{\prime}\setminus
W}(K_{i}^{\prime})|\geq|B^{\kappa}_{G-Y}(X)|\geq\exp(\sqrt[4]{\kappa})\geq\exp(\sqrt[5]{\log
n})=:x.$

Let $U^{*}=\bigcup_{p\neq i,j}B^{r}_{G^{\prime}}(K_{p})$. As we choose the
kernels $K_{i}$ to be pairwise at least a distance $2\kappa+1>\kappa+2r$
apart, both $B^{\kappa+r}_{G^{\prime}\setminus W}(K_{i}^{\prime})$ and
$B^{\kappa+r}_{G^{\prime}\setminus W}(K_{j}^{\prime})$ are disjoint from
$U^{*}$. Recall from (16) that $|K_{i}|\leq|F_{i}|\leq\exp(\sqrt[10]{\log
n})$, for each $i\in[\ell^{\prime}]$ and $\Delta(G^{\prime})\leq dm^{3}$. Thus
the total number of vertices we avoid in F2 is

$|U^{*}|\leq(1-4\eta)d\cdot 2\exp(\sqrt[10]{\log
n})(dm^{3})^{r}\leq\rho(x)x/4.$

Moreover, the number of edges we avoid in F2 is $|W|\leq d^{2}\log^{4}n\leq
d(G)\rho(x)x$. Since $|B^{\kappa+r}_{G^{\prime}\setminus
W}(K_{i}^{\prime})|,\\\ \leavevmode\nobreak\
|B^{\kappa+r}_{G^{\prime}\setminus W}(K_{j}^{\prime})|\geq x,$ by Lemma 2.4
with

$X_{1}=B^{\kappa+r}_{G^{\prime}\setminus
W}(K_{i}^{\prime}),\leavevmode\nobreak\
X_{2}=B^{\kappa+r}_{G^{\prime}\setminus
W}(K_{j}^{\prime}),\leavevmode\nobreak\ Y=U^{*}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ F=W,$

there exists a ($B^{\kappa+r}_{G^{\prime}\setminus
W}(K_{i}^{\prime}),B^{\kappa+r}_{G^{\prime}\setminus
W}(K_{j}^{\prime})$)-path, say $Q_{ij}$, of length at most $m$ in
$(G-U^{*})\setminus W$. It is easy to observe that $Q_{ij}$ can be extended,
first within the ball $B^{\kappa+r}_{G^{\prime}\setminus W}(K_{i}^{\prime})$
(or $B^{\kappa+r}_{G^{\prime}\setminus W}(K_{i}^{\prime})$) and then within
$K_{i}^{\prime}=B^{s}_{F_{i}\setminus W}(v_{i})$ (or $K_{j}^{\prime}$), into a
$(v_{i},v_{j})$-path, in which we denote by $P_{ij}$ such a shortest
$(v_{i},v_{j})$-path in $(G-U^{*})\setminus W$. Then $P_{ij}$ always has
length at most $m+2\kappa+2r+2s\leq 2\log^{4}n$, which together with the paths
$P_{e},e\in I$ satisfy F1, F2 and F3, contradicting the maximality of $I$.

This completes the proof.

## Acknowledgements

We thank the referee for the careful readings and suggestions that improve the
presentation.

## References

  * [1] F. N. Abu-Khzam and M. A. Langston.  Graph coloring and the immersion order.  In Computing and combinatorics, volume 2697 of Lecture Notes in Comput. Sci., pages 394–403. Springer, Berlin, 2003.
  * [2] P. A. Catlin.  A bound on the chromatic number of a graph.  Discrete Math., 22(1):81–83, 1978.
  * [3] K. L. Collins and M. E. Heenehan.  Constructing graphs with no immersion of large complete graphs.  J. Graph Theory, 77(1):1–18, 2014.
  * [4] M. DeVos, Z. Dvořák, J. Fox, J. McDonald, B. Mohar, and D. Scheide.  A minimum degree condition forcing complete graph immersion.  Combinatorica, 34(3):279–298, 2014.
  * [5] M. DeVos, K.-i. Kawarabayashi, B. Mohar, and H. Okamura.  Immersing small complete graphs.  Ars Math. Contemp., 3(2):139–146, 2010.
  * [6] Z. Dvořák and L. Yepremyan.  Complete graph immersions and minimum degree.  J. Graph Theory, 88(1):211–221, 2018.
  * [7] G. Gauthier, T.-N. Le, and P. Wollan.  Forcing clique immersions through chromatic number.  European J. Combin., 81:98–118, 2019.
  * [8] H. Hadwiger.  Über eine Klassifikation der Streckenkomplexe.  Vierteljschr. Naturforsch. Ges. Zürich, 88:133–142, 1943.
  * [9] G. Hajós.  Über eine konstraktion nicht $n$-farbbarer graphen.  Wiss. Z. MartinLuther Univ. Halle-Wittenberg Math. Naturwiss. Reihe, 10:116–117, 1961.
  * [10] J. Haslegrave, J. Kim, and H. Liu.  Extremal density for sparse minors and subdivisions.  International Mathematics Research Notices, 06 2021.  rnab154.
  * [11] T. Kővári, V. T. Sós, and P. Turán.  On a problem of K. Zarankiewicz.  Colloq. Math., 3:50–57, 1954.
  * [12] J. Komlós and E. Szemerédi.  Topological cliques in graphs. II.  Combin. Probab. Comput., 5(1):79–90, 1996.
  * [13] A. V. Kostochka.  Lower bound of the Hadwiger number of graphs by their average degree.  Combinatorica, 4(4):307–316, 1984.
  * [14] M. Krivelevich and B. Sudakov.  Minors in expanding graphs.  Geom. Funct. Anal., 19(1):294–331, 2009.
  * [15] D. Kühn and D. Osthus.  Complete minors in $K_{s,s}$-free graphs.  Combinatorica, 25(1):49–64, 2005.
  * [16] F. Lescure and H. Meyniel.  On a problem upon configurations contained in graphs with given chromatic number.  In Graph theory in memory of G. A. Dirac (Sandbjerg, 1985), volume 41 of Ann. Discrete Math., pages 325–331. North-Holland, Amsterdam, 1989.
  * [17] H. Liu and R. Montgomery.  A proof of Mader’s conjecture on large clique subdivisions in $C_{4}$-free graphs.  J. Lond. Math. Soc. (2), 95(1):203–222, 2017.
  * [18] C. S. J. A. Nash-Williams.  On well-quasi-ordering infinite trees.  Proc. Cambridge Philos. Soc., 61:697–720, 1965.
  * [19] S. Norin, L. Postle, and Z.-X. Song.  Breaking the degeneracy barrier for coloring graphs with no $K_{t}$ minor.  arXiv:1910.09378, 2020.
  * [20] L. Postle.  Further progress towards Hadwiger’s conjecture.  arXiv:2006.11798, 2020.
  * [21] N. Robertson and P. Seymour.  Graph minors XXIII. Nash-Williams’ immersion conjecture.  J. Combin. Theory Ser. B, 100(2):181–205, 2010.
  * [22] N. Robertson, P. Seymour, and R. Thomas.  Hadwiger’s conjecture for $K_{6}$-free graphs.  Combinatorica, 13(3):279–361, 1993.
  * [23] A. Thomason.  The extremal function for complete minors.  J. Combin. Theory Ser. B, 81(2):318–338, 2001.