pith. sign in

arxiv: 1812.01961 · v2 · pith:LVLQNGXBnew · submitted 2018-12-05 · 🧮 math.CO

Complete minors in graphs without sparse cuts

classification 🧮 math.CO
keywords graphscompletelargestminororderregularsparsewithout
0
0 comments X
read the original 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 \[ \Omega\left( \sqrt{\frac{n d}{\log d}} \right). \] 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 paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.