# 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.