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

Richard Arratia

The electronic journal of combinatorics, Tome 6 (1999)

Résumé

Consider, for a permutation $\sigma \in {\cal S}_k$, the number $F(n,\sigma)$ of permutations in ${\cal 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 {\cal 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.

Détail

DOI : 10.37236/1477

Classification : 05A05, 05A16
Mots-clés : Stanley-Wilf conjecture, pattern, Alon conjecture, permutation