On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern (Q1305174)

Summary: Consider, for a permutation \(\sigma \in {\mathcal S}_k\), the number \(F(n,\sigma)\) of permutations in \({\mathcal S}_n\) which avoid \(\sigma\) as a subpattern. The conjecture of Stanley and Wilf is that for every \(\sigma\) there is a constant \(c(\sigma)< \infty\) such that for all \(n\), \(F(n,\sigma) \leq c(\sigma)^n\). All the recent work on this problem also mentions the ``stronger conjecture'' that for every \(\sigma\), the limit of \(F(n,\sigma)^{1/n}\) exists and is finite. In this short note we prove that the two versions of the conjecture are equivalent, with a simple argument involving subadditivity. We also discuss \(n\)-permutations, containing all \(\sigma \in {\mathcal S}_k\) as subpatterns. We prove that this can be achieved with \(n=k^2\), we conjecture that asymptotically \(n \sim (k/e)^2\) is the best achievable, and we present Noga Alon's conjecture that \(n \sim (k/2)^2\) is the threshold for random permutations.