Embedding dense minors via crux
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality