Embedding dense minors via crux

arXiv:2610.39957 · math.CO · Submitted 2026-10-29 · Read on arXiv

math.CO

Submitted: 2026-10-29

Updated: 2026-11-16

Comments: 12 pages

Code: https://github.com/openai/math

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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.

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.

Sources

Related papers