Welcome! The CMSA seminar aims to bring together combinatorialists from Australasia and around the world.
The seminar is held roughly every two weeks during spring and autumn, usually at either 11am or 5pm AEDT.
Subscribe: In order to subscribe mail t.lesgourgues@unsw.edu.au and ask to be added to the list. We send announcements and zoom details before every talk.
Current organiser: Thomas Lesgourgues.
Please email with your feedback and suggestions.
Previous talks:
2020
2021
2022
2023
2024
2025
2026 talks:
|
1 April 2026, 11am AEDT
Natasha Morrison (University of Victoria)
|
|
Spanning Trees in Pseudorandom Graphs via Sorting Networks
|
| Abstract:
We show that (n, d, λ)-graphs with λ = O(d/ log^3 n) are universal with respect to all bounded degree spanning trees. This significantly improves upon the previous best bound due to Han and Yang of the form λ = d/ exp (O(√log n)), and makes progress towards a problem of Alon, Krivelevich, and Sudakov from 2007.
Our proof relies on the existence of sorting networks of logarithmic depth, as given by a celebrated construction of Ajtai, Komlós and Szemerédi. Using this construction, we show that the classical vertex-disjoint paths problem can be solved for a set of vertices fixed in advance.
|