Complete minors in graphs without sparse cuts

Complete minors in graphs without sparse cuts

-
Michael Krivelevich, Tel Aviv
Fine Hall 224

We show that if G is a graph on n vertices with all degrees comparable to d and without sparse cuts, in an appropriately defined quantitative sense, then G contains a complete minor of order \sqrt{nd/log d}. As a corollary we determine the order of a largest complete minor one can guarantee in d-regular graphs with large eigenvalue gap, in random d-regular graphs, and in jumbled graphs. Joint work with Rajko Nenadov.