Complete minors in graphs without sparse cuts

DOI10.1093/IMRN/RNZ086MaRDI QIDQ6310750arXivWikidataFDO

Authors Michael Krivelevich, Rajko Nenadov

Publication date 5 December 2018

Published in arXiv

Full work available at URL https://doi.org/10.1093/IMRN/RNZ086

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph minors (05C83) Combinatorial probability (60C05)

arXiv classification

math.CO

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 [ Omegaleft( sqrt{frac{n d}{log d}} ight). ] 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)$.

This page was built for publication: Complete minors in graphs without sparse cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6310750)