Spanning trees in pseudorandom graphs via sorting networks

Zoom Link

We show that $(n,d,\lambda)$-graphs with $\lambda=O(d/log^3n)$ 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\'{o}s and Szemer\'{e}di, with further applications to the vertex disjoint paths problem. Joint work with Joseph Hyde, Alp M\"{u}yesser, and Matías Pavez-Signé.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.