2025/03/10 by Krivelevich, Michael, Nenadov, Rajko
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2503.06826
We study large minors in small-set expanders. More precisely, we consider graphs with n vertices and the property that every set of size at most αn / t expands by a factor of t, for some (constant) α> 0 and large t = t(n). We obtain the following: * Improving results of Krivelevich and Sudakov, we show that a small-set expander contains a complete minor of order √(n t / log n). * We show that a small-set expander contains every graph H with O(n log t / log n) edges and vertices as a minor. We complement this with an upper bound showing that if an n-vertex graph G has average degree d, then there exists a graph with O(n log d / log n) edges and vertices which is not a minor of G. This has two consequences: (i) It implies the optimality of our result in the case t = dc for some constant c > 0, and (ii) it shows expanders are optimal minor-universal graphs of a given average degree.