- Series
- Combinatorics Seminar
- Time
- Friday, December 4, 2020 - 3:00pm for 1 hour (actually 50 minutes)
- Location
- https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
- Speaker
- Xiaoyu He – Stanford University
- Organizer
- Lutz Warnke

It is a classical fact that for any c > 0, a random permutation of length n = (1+c)k^2/4 typically contains a monotone subsequence of length k. As a far-reaching generalization, Alon conjectured that for this same n, a typical n-permutation is k-universal, meaning that it simultaneously contains every k-pattern. He also gave a simple proof for the fact that if n is increased to Ck^2 log k, then a typical n-permutation is k-universal. Our main result is that the same statement holds for n = Ck^2 log log k, getting almost all of the way to Alon's conjecture.

In this talk we give an overview of the structure-vs-randomness paradigm which is a key ingredient in the proof, and a sketch of the other main ideas. Based on joint work with Matthew Kwan.