Complete Minors in Graphs Without Sparse Cuts. (20th May 2019)

• Record Type: Journal Article
• Authors: Krivelevich, Michael; Nenadov, Rajko
• Is Part Of: International mathematics research notices. Volume 2021:Number 12(2021)
• Page Start: 8996
• Page End: 9015
• Publication Date: 2019-05-20
• Subjects: Mathematics -- Periodicals; 510
• DOI: 10.1093/imrn/rnz086
• Languages: English
• ISSNs: 1073-7928

Abstract

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 $$\begin{equation*} \Omega\left( \sqrt{\frac{n d}{\log d}} \right). \end{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)$ .