  For a permutation $\pi$, let $S_{n}(\pi)$ be the number of permutations on
$n$ letters avoiding $\pi$. Marcus and Tardos proved the celebrated
Stanley-Wilf conjecture that $L(\pi)= \lim_{n \to \infty} S_n(\pi)^{1/n}$
exists and is finite. Backed by numerical evidence, it has been conjectured by
many researchers over the years that $L(\pi)=\Theta(k^2)$ for every permutation
$\pi$ on $k$ letters. We disprove this conjecture, showing that
$L(\pi)=2^{k^{\Theta(1)}}$ for almost all permutations $\pi$ on $k$ letters.
