Dense Minors from the Crux
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.
Authors
- Donglei Yang (ORCID: https://orcid.org/0000-0002-4992-6555)
- Xia Wang
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-10-29
- DOI
- https://doi.org/10.48550/arxiv.2610.39957
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint