Paperlane

no. 16 · Tuesday 17 November 2026

Embedding dense minors via crux

Xia Wang and Donglei Yang

math.CO · v2 · 13 pp

Abstract

Let $G$ be a graph with average degree $d>0$ and $C_α(G)$ be the minimum order of a subgraph whose average degree is at least $αd$ for any fixed $0<α<1$. Then $G$ has a minor of average degree $Ω(\sqrt{d\,C_α(G)})$, which is asymptotically tight up to a constant factor. This reveals a unified mechanism underlying previous results on dense minors in locally sparse graphs.

comments
13 pages
fields
Combinatorics
pdf ↗ page arXiv:2610.39957 ↗