Home /  Workshop /  Schedules /  Spanning trees in pseudorandom graphs via sorting networks

Spanning trees in pseudorandom graphs via sorting networks

Connections Workshop: Extremal Combinatorics February 06, 2025 - February 07, 2025

February 06, 2025 (02:15 PM PST - 03:15 PM PST)
Speaker(s): Natasha Morrison (University of Victoria)
Location: SLMath: Eisenbud Auditorium, Online/Virtual
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC
Video

Spanning trees in pseudorandom graphs via sorting networks

Abstract

Zoom Link

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é.

Supplements No Notes/Supplements Uploaded
Video/Audio Files

Spanning trees in pseudorandom graphs via sorting networks

Troubles with video?

Please report video problems to itsupport@slmath.org.

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