Hypercube minor-universality

Itai Benjamini, Or Kalifa, Elad Tzalik

A graph $G$ is $m$-minor-universal if every graph with at most $m$ edges (and no isolated vertices) is a minor of $G$. We prove that the $d$-dimensional hypercube, $Q_d$, is $Ω\lef…