Rolling backwards can move you forward: On embedding problems in sparse expanders

Abstract

We develop a general embedding method based on the Friedman-Pippenger tree embedding technique and its algorithmic version, enhanced with a roll-back idea allowing a sequential retracing of previously performed embedding steps. We use this method to obtain the following results. We show that the size-Ramsey number of logarithmically long subdivisions of bounded degree graphs is linear in their number of vertices, settling a conjecture of Pak [ <italic>Proceedings of the thirteenth annual ACMSIAM symposium on discrete algorithms (SODA’02)</italic> , 2002, pp. 321-328]. We give a deterministic, polynomial time online algorithm for finding vertex-disjoint paths of a prescribed length between given pairs of vertices in an expander graph. Our result answers a question of Alon and Capalbo [ <italic>48th annual IEEE symposium on foundations of computer science (FOCS’07)</italic> , 2007, pp. 518-524]. We show that relatively weak bounds on the spectral ratio <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda slash d"> <mml:semantics> <mml:mrow> <mml:mi> λ </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>d</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\lambda /d</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of <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> -regular graphs force the existence of a topological minor of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K Subscript t"> <mml:semantics> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">K_t</mml:annotation> </mml:semantics> </mml:math> </inline-formula> where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="t equals left-parenthesis 1 minus o left-parenthesis 1 right-parenthesis right-parenthesis d"> <mml:semantics> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>=</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo> − </mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> <mml:mi>d</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">t=(1-o(1))d</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We also exhibit a construction which shows that the theoretical maximum <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="t equals d plus 1"> <mml:semantics> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>=</mml:mo> <mml:mi>d</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">t=d+1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> cannot be attained even if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda equals upper O left-parenthesis StartRoot d EndRoot right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi> λ </mml:mi> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msqrt> <mml:mi>d</mml:mi> </mml:msqrt> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\lambda =O(\sqrt {d})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . This answers a question of Fountoulakis, Kühn and Osthus [Random Structures Algorithms 35 (2009), pp. 444-463].

Topics & Concepts