2025/02/10 by Hogan, Emma, Michel, Lukas, Scott, Alex +3 · 1 citation
#05C83 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2502.06629
Benjamini, Kalifa and Tzalik recently proved that there is an absolute constant c>0 such that any graph with at most c⋅2d/d edges and no isolated vertices is a minor of the d-dimensional hypercube Qd, while there is an absolute constant K > 0 such that Qd is not (K⋅2d/√(d))-minor-universal. We show that Qd does not contain 3-uniform expander graphs with C⋅2d/d edges as minors. This matches the lower bound up to a constant factor and answers one of their questions.