Jacob Fox: Combinatorics of Permutations

For a permutation p, let S_n(p) be the number of permutations on letters avoiding p. A decade ago, Marcus and Tardos proved the celebrated Stanley-Wilf conjecture that, for each permutation p, S_n(p)^{1/n} tends to a finite limit L(p). Backed by numerical evidence, it has been conjectured by various researchers over the years that L(p) is on the order of k^2 for every permutation p on k letters. We disprove this conjecture, showing that L(p) is exponential in a power of k for almost all permutations p on k letters. The proof uses ideas from extremal and probabilistic combinatorics.