pipette
ESEspañol

Dense Minors from the Crux

Xia Wang, Donglei Yang

Preprint

In the authors' words

Let be a graph with average degree and be the minimum order of a subgraph whose average degree is at least for any fixed . Then has a minor of average degree , which is asymptotically tight up to a constant factor. This reveals a unified mechanism underlying previous results on dense minors in locally sparse graphs.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 12 pages