Natasha Morrison

Spanning trees in pseudorandom graphs via sorting networks

We show that (n,d,λ)-graphs with λ=O(d/log³n) are universal with respect to all bounded degree spanning trees. This significantly improves upon the previous best bound due to Han and Yang, and makes progress towards a problem of Alon, Krivelevich, and Sudakov from 2007. The key new idea in 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, with further applications to the vertex disjoint paths problem.
Joint work with Joseph Hyde, Alp Müyesser, and Matías Pavez-Signé.