The previous talk in the series is here. The next talk in the series is here.
We say that a permutation π of {1,2,…,k} is contained in a permutation σ of {1,2,…,n} if we can find k elements of {1,2,…,n} that are reordered by σ in the way that π reorders {1,2,…,k}. For instance, the permutation 2413 (meaning that 1 goes to 2, 2 goes to 4, 3 goes to 1 and 4 goes to 3) is contained in the permutation 216459387, because of the subsequence 6938 (or if you prefer, 4938 or 4937 or 6937), which is ordered in the same way as 2413. A famous conjecture of Richard Stanley and Herb Wilf stated that for a fixed permutation π, the number of permutations of {1,2,…,n} that do not contain π grows at most exponentially. This was proved by Adam Marcus and Gábor Tardos via a conjecture of Zoltán Füredi and Peter Hajnal that was known to imply it. The proof is very ingenious but also short and elementary (in the sense of needing no prerequisites beyond some basic combinatorial definitions). We state the Stanley-Wilf conjecture, then consider matrix containment and statement of the Füredi-Hajnal conjecture. After, we give Marcus and Tardos’s proof of the Füredi-Hajnal conjecture, and finally look at deducing the Stanley-Wilf conjecture.
This video was produced by Tim Gowers as part of his Part III course at the University of Cambridge. Printed notes for this course are available here.