2018/12/05 by Krivelevich, Michael, Nenadov, Rajko · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1812.01961
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 Ω( √((n d)/(log d)) ). As a corollary we determine the order of a largest complete minor one can guarantee in d-regular graphs for which the second 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).