Speaker
Natasha Morrison, University of Victoria
Abstract
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é.