Tight Bounds for Hypercube Minor‐Universality

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.