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

We develop a general embedding method based on the Friedman-Pippenger tree embedding technique (1987) and its algorithmic version, essentially due to Aggarwal et al. (1996), enhanced with a roll-back idea allowing to sequentially retrace previously performed embedding steps. This proves to be a powerful tool for embedding graphs of large girth into expander graphs. As an application of this method, we settle two problems: For a graph H, we denote by Hq the graph obtained from H by subdividing its edges with q–1 vertices each. We show that the k-size-Ramsey number Ŗk(Hq) satisfies Ŗk(Hq) = O(qn) for every bounded degree graph H on n vertices and for q = Ω(log n), which is optimal up to a constant factor. This settles a conjecture of Pak (2002). We give a deterministic, polynomial time algorithm for finding vertex-disjoint paths between given pairs of vertices in a strong expander graph. More precisely, let G be an (n, d, λ)-graph with λ = O(d1 – ∊), and let be any collection of at most disjoint pairs of vertices in G for some small constant c, such that in the neighborhood of every vertex in G there are at most d/4 vertices from . Then there exists a polynomial time algorithm which finds vertex-disjoint paths between every pair in , and each path is of the same length . Both the number of pairs and the length of the paths are optimal up to a constant factor; the result answers the offline version of a question of Alon and Capalbo (2007).