Large Complete Minors from a Cheeger Condition

Let $G$ be a graph on $n$ vertices, and let $e_G(S,V(G)\setminus S)$ be the number of edges with exactly one endpoint in $S$. The Cheeger constant and the restricted Cheeger constant of $G$, where $k\ge 1$ is real, are, respectively, $$h(G)=\underset{\begin{array}{c}\mathrm{\varnothing }\mathrm{\ne }S\subseteq V(G)\\ \mathrm{\mid }S\mathrm{\mid }\le \frac{n}{2}\end{array}}{\min }\frac{e_G(S,V(G)\setminus S)}{\mathrm{\mid }S\mathrm{\mid }}\text{ and }{h}_k(G)=\underset{\begin{array}{c}\mathrm{\varnothing }\mathrm{\ne }S\subseteq V(G)\mathrm{\mid }S\mathrm{\mid }\le \min \{k,\frac{n}{2}\}\end{array}}{\min }\frac{e_G(S,V(G)\setminus S)}{\mathrm{\mid }S\mathrm{\mid }}\mathrm{.}$$ The contraction clique number $\text{ccl}(G)$ is the largest integer $r$ such that $G$ contains the complete graph $K_r$ as a minor. Krivelevich and Nenadov [Complete minors in graphs without sparse cuts, Int. Math. Res. Not. IMRN 12 (2021) 8996–9015] proved that, for every fixed $\text{eps}>0$ and all sufficiently large $n$ and $d$, if $G$ is a graph on $n$ vertices with maximum degree at most $d$, then $h(G)\ge \text{eps}d$ and $h_{\text{eps}n}(G)\ge (\frac{1}{2}+\text{eps})d$ imply $\text{ccl}(G)={\mathrm{\Omega }}_{\text{eps}}(\sqrt{\frac{nd}{\log d}})$. They asked to determine if one can guarantee the same lower bound on $\text{ccl}(G)$ without the additional condition on $h_{\text{eps}n}(G)$. They showed that this is the case when $d$ is a constant. We answer this question affirmatively. For every $\text{eps}>0$, there are constants $\beta =\beta (\text{eps})>0$ and $n_0=n_0(\text{eps})$ such that, whenever $d\ge 3$ is an integer, for every graph $G$ with $n\ge n_0$ vertices and maximum degree at most $d$, if $h(G)\ge \text{eps}d$, then $\text{ccl}(G)\ge \beta \sqrt{\frac{nd}{\log d}}$. The dependence of this lower bound on $n$ and $d$ is best possible up to a constant factor. As a corollary, a lower bound is derived for the contraction clique number of $d$-regular graphs for which the second largest eigenvalue is bounded away from $d$, compared to earlier $\frac{d}{2}$. The proof combines spectral properties of graphs with an analysis of lazy random walks.