Tight Bounds for Hypercube Minor‐Universality

Journal article

A graph G $G$ is m $m$ ‐minor‐universal if every graph H $H$ with at most m $m$ edges and no isolated vertices is contained as a minor in G $G$ . Recently, Benjamini, Kalifa and Tzalik proved that there is an absolute constant c > 0 $c\gt 0$ such that the d $d$ ‐dimensional hypercube Q d ${Q}_{d}$ is ( c ⋅ 2 d / d $c\cdot {2}^{d}/d$ )‐minor‐universal, while there is an absolute constant K > 0 $K\gt 0$ such that Q d ${Q}_{d}$ is not ( K ⋅ 2 d / d ) $(K\cdot {2}^{d}/\sqrt{d})$ ‐minor‐universal. We show that Q d ${Q}_{d}$ does not contain 3‐uniform expander graphs with C ⋅ 2 d / d $C\cdot {2}^{d}/d$ edges as minors. This matches the lower bound up to a constant factor and answers one of their questions.

Authors: Hogan, E; Michel, L; Scott, A; Tamitegama, Y; Tan, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Wiley
• Journal: Journal of Graph Theory
• Article number: jgt.70035
• Publication date: 2026-04-10
• Acceptance date: 2026-03-27
• DOI: 10.1002/jgt.70035
• EISSN: 1097-0118
• ISSN: 0364-9024
• Language: English