Complete Minors in Graphs Without Sparse Cuts. (20th May 2019) - Krivelevich, Michael; Nenadov, Rajko
Abstract: We show that if G is a graph on n vertices, with all degrees comparable to some d = d(n), and without a sparse cut, for a suitably chosen notion of sparseness, then it contains a complete minor of order equation* Ω( n dd ). equation* As a corollary we determine the order of a largest complete minor one can guarantee in d -regular graphs for which the 2nd largest eigenvalue is bounded away from d/2, in (d/n, o(d)) -jumbled graphs, and in random d -regular graphs, for almost all d = d(n) .