Jacob Fox (Stanford)
Combinatorics of Permutations

Abstract: A fundamental question in enumerative combinatorics asks: how
many permutations on n letters avoid a given permutation? The famous
Stanley-Wilf conjecture states that the answer grows exponentially in n.
Marcus and Tardos proved this conjecture a decade ago with a remarkably
simple argument. It was widely believed that the exponential constant,
known as the Stanley-Wilf limit, grows quadratically in the size of the
given permutation. We disprove this conjecture, showing that it grows
exponentially in a power of the permutation size for almost all
permutations. The proof utilizes tools from extremal and probabilistic
combinatorics and new concepts including dyadic random matrices and
interval minors.