PreprintCC BY 4.0arXiv
Dense Minors from the Crux
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 Ω(√(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.
Related
- Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
- Prime and Cohen-Macaulay ideals of 2-minors with linear resolution
- Ideals of 2-minors of nearly determinantal matrices
- Extremal function for rooted K5 minors
- Valuated delta matroids and principal minors of Hermitian matrices
BibTeX
@misc{wang2026dense,
title = {{Dense Minors from the Crux}},
author = {Xia Wang and Donglei Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39957},
eprint = {2610.39957},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39957},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Dense Minors from the Crux
AU - Xia Wang
AU - Donglei Yang
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39957
UR - https://arxiv.org/abs/2610.39957
AB - 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 Ω(√(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.
ER -