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

Abstract

We develop a general embedding method based on the FriedmanPippenger 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. center dot 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 [Proceedings of the thirteenth annual ACMSIAM symposium on discrete algorithms (SODA'02), 2002, pp. 321328]. center dot 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 [48th annual IEEE symposium on foundations of computer science (FOCS'07), 2007, pp. 518-524]. center dot We show that relatively weak bounds on the spectral ratio lambda/d of dregular graphs force the existence of a topological minor of Kt where t = (1 - o(1))d. We also exhibit a construction which shows that the theoretical maximum t = d + 1 cannot be attained even if lambda = O( d). This answers a question of Fountoulakis, Ku spacing diaeresis hn and Osthus [Random Structures Algorithms 35 (2009), pp. 444-463].