Stanley-Wilf limits are typically exponential

Computer Science/Discrete Mathematics Seminar I
Topic:Stanley-Wilf limits are typically exponential
Speaker:Jacob Fox
Affiliation:Massachusetts Institute of Technology
Date:Monday, October 7
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/2013/1007-JacobFox

For a permutation \(p\), let \(S_n(p)\) be the number of permutations on \(n\) letters avoiding \(p\). Stanley and Wilf conjectured that, for each permutation \(p\), \(S_n(p)^{1/n}\) tends to a finite limit \(L(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.