Tight Bounds for Hypercube Minor‐Universality
Abstract
ABSTRACT A graph is ‐minor‐universal if every graph with at most edges and no isolated vertices is contained as a minor in . Recently, Benjamini, Kalifa and Tzalik proved that there is an absolute constant such that the ‐dimensional hypercube is ()‐minor‐universal, while there is an absolute constant such that is not ‐minor‐universal. We show that does not contain 3‐uniform expander graphs with edges as minors. This matches the lower bound up to a constant factor and answers one of their questions.
Fields of Study & Subjects
Interconnection Networks and Systems
Advanced Graph Theory Research
Optimization and Search Problems
Publication details
- Journal / source
- Journal of Graph Theory
- Volume
- 112
- Issue
- 4
- Pages
- 433–437
- Publication date
- 10 April 2026
- Language
- EN