Computer Science/Discrete Mathematics Seminar I

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.