Spanning trees in pseudorandom graphs via sorting networks

Abstract

We show that $(n,d,\lambda )$-graphs with $\lambda =O(d/{\log }^{3}n)$ are universal with respect to all bounded degree spanning trees. This significantly improves upon the previous best bound due to Han and Yang of the form $\lambda =d/\exp (O(\sqrt{\log n}))$, and makes progress towards a problem of Alon, Krivelevich, and Sudakov from 2007. Our proof relies on the existence of sorting networks of logarithmic depth, as given by a celebrated construction of Ajtai, Komlós and Szemerédi. Using this construction, we show that the classical vertex-disjoint paths problem can be solved for a set of vertices fixed in advance.

15 pages, 3 figures