Minors in small-set expanders

We study large minors in small-set expanders. More precisely, we consider graphs with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> vertices and the property that every set of size at most <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha n slash t"> <mml:semantics> <mml:mrow> <mml:mi> α </mml:mi> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>t</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\alpha n / t</mml:annotation> </mml:semantics> </mml:math> </inline-formula> expands by a factor of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="t"> <mml:semantics> <mml:mi>t</mml:mi> <mml:annotation encoding="application/x-tex">t</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , for some (constant) <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha greater-than 0"> <mml:semantics> <mml:mrow> <mml:mi> α </mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\alpha &gt; 0</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and large <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="t equals t left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>=</mml:mo> <mml:mi>t</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">t = t(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We obtain the following: Improving results of Krivelevich and Sudakov, we show that a small-set expander contains a complete minor of order <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartRoot n t slash log n EndRoot"> <mml:semantics> <mml:msqrt> <mml:mi>n</mml:mi> <mml:mi>t</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>n</mml:mi> </mml:msqrt> <mml:annotation encoding="application/x-tex">\sqrt {n t / \log n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We show that a small-set expander contains every graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H"> <mml:semantics> <mml:mi>H</mml:mi> <mml:annotation encoding="application/x-tex">H</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis n log t slash log n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>t</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(n \log t / \log n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> edges and vertices as a minor. We complement this with an upper bound showing that if an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -vertex graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> has average degree <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"> <mml:semantics> <mml:mi>d</mml:mi> <mml:annotation encoding="application/x-tex">d</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , then there exists a graph with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis n log d slash log n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>d</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(n \log d / \log n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> edges and vertices which is not a minor of <inline-formula content-type="math/mathml">