Richard P. Stanley Seminar in Combinatorics: Spanning trees in pseudorandom graphs via sorting networks

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.

Joint work with Joseph Hyde, Alp M\”{u}yesser, and Matías Pavez-Signé.

For information about the Richard P. Stanley Seminar in Combinatorics, visit… https://math.mit.edu/combin/