Spanning trees in pseudorandom graphs via sorting networks
Connections Workshop: Extremal Combinatorics February 06, 2025 - February 07, 2025
Location: SLMath: Eisenbud Auditorium, Online/Virtual
Primary Mathematics Subject Classification
No Primary AMS MSC
Secondary Mathematics Subject Classification
No Secondary AMS MSC
Spanning trees in pseudorandom graphs via sorting networks
We show that (n,d,λ)-graphs with λ=O(d/log3n) 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é.
Spanning trees in pseudorandom graphs via sorting networks
Please report video problems to itsupport@slmath.org.
See more of our Streaming videos on our main VMath Videos page.