Large Complete Minors from a Cheeger Condition
Abstract
Let G be a graph on n vertices, and let eG(S,V(G)∖ S) be the number of edges with exactly one endpoint in S. The Cheeger constant and the restricted Cheeger constant of G, where k≥1 is real, are, respectively, h(G)=minsubstack∅≠ S⊆ V(G) |S|≤ n/2 (eG(S,V(G)∖ S))/|S| and hk(G)=minsubstack∅≠ S⊆ V(G) |S|≤min{k,n/2} (eG(S,V(G)∖ S))/|S|. The contraction clique number ccl(G) is the largest integer r such that G contains the complete graph Kr 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 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)≥eps d and heps n(G)≥(1/2+eps)d imply ccl(G)=Ωeps(√(nd/(log d))). They asked to determine if one can guarantee the same lower bound on ccl(G) without the additional condition on heps n(G). They showed that this is the case when d is a constant. We answer this question affirmatively. For every eps>0, there are constants β=β(eps)>0 and n0=n0(eps) such that, whenever d≥ 3 is an integer, for every graph G with n≥ n0 vertices and maximum degree at most d, if h(G)≥eps d, then ccl(G)≥β√(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 d/2. The proof combines spectral properties of graphs with an analysis of lazy random walks.
Related
- An explicit bound on the extremal function for complete graph minors
- Groups satisfying the minimal condition on centralizers are complete co-analytic
- The Game Chromatic Number of Complete Multipartite Graphs with Singletons and Large Parts
- Arithmetic purity of strong approximation for complete intersections of large dimension
- Cheeger constant rigidity for cocompact negatively curved manifolds
BibTeX
@misc{li2026large,
title = {{Large Complete Minors from a Cheeger Condition}},
author = {Chengli Li and Leyou Xu and Bo Zhou},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15414},
eprint = {2609.15414},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15414},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Large Complete Minors from a Cheeger Condition
AU - Chengli Li
AU - Leyou Xu
AU - Bo Zhou
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15414
UR - https://arxiv.org/abs/2609.15414
AB - Let G be a graph on n vertices, and let e_G(S,V(G)∖ S) be the number of edges with exactly one endpoint in S. The Cheeger constant and the restricted Cheeger constant of G, where k≥1 is real, are, respectively, h(G)=min_substack∅≠ S⊆ V(G) |S|≤ n/2 (e_G(S,V(G)∖ S))/|S| and h_k(G)=min_substack∅≠ S⊆ V(G) |S|≤min{k,n/2} (e_G(S,V(G)∖ S))/|S|. The contraction clique number 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 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)≥eps d and h_eps n(G)≥(1/2+eps)d imply ccl(G)=Ω_eps(√(nd/(log d))). They asked to determine if one can guarantee the same lower bound on ccl(G) without the additional condition on h_eps n(G). They showed that this is the case when d is a constant. We answer this question affirmatively. For every eps>0, there are constants β=β(eps)>0 and n_0=n_0(eps) such that, whenever d≥ 3 is an integer, for every graph G with n≥ n_0 vertices and maximum degree at most d, if h(G)≥eps d, then ccl(G)≥β√(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 d/2. The proof combines spectral properties of graphs with an analysis of lazy random walks.
ER -