Stanley-Wilf Limits are Typically Exponential

Monday, September 29, 2014 - 11:30am - 12:20pm
Keller 3-180
Jacob Fox (Massachusetts Institute of Technology)
For a permutation p, let S_n(p) be the number of permutations on n letters avoiding p. Stanley and Wilf conjectured that S_n(p)^{1/n} tends to a finite limit L(p) for each permutation p. Marcus and Tardos proved the Stanley-Wilf conjecture by a remarkably simple argument. 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 tools from probabilistic and extremal combinatorics.
MSC Code: