Rolling backwards can move you forward: On embedding problems in sparse expanders
Nemanja Draganić, Michael Krivelevich, Rajko Nenadov · Transactions of the American Mathematical Society · 2022
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 [ Proceedings of the thirteenth annual ACMSIAM symposium on discrete algorithms (SODA’02) , 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 [ 48th annual IEEE symposium on foundations of computer science (FOCS’07) , 2007, pp. 518-524]. We show that relatively weak bounds on the spectral ratio λ / d \lambda /d of d d -regular graphs force the existence of a topological minor of K t K_t where t = ( 1 − o ( 1 ) ) d t=(1-o(1))d . We also exhibit a construction which shows that the theoretical maximum t = d + 1 t=d+1 cannot be attained even if λ = O ( d ) \lambda =O(\sqrt {d}) . This answers a question of Fountoulakis, Kühn and Osthus [Random Structures Algorithms 35 (2009), pp. 444-463].