Spanning trees in pseudorandom graphs via sorting networks

We show that $(n,d,\lambda )$-graphs with $\lambda =O(d\mathrm{/}{\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\mathrm{/}\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.