Stanley–Wilf conjecture for permutation pattern avoidance

From papers

Let SnS_n denote the set of permutations of [n]={1,2,,n}[n]=\{1,2,\ldots,n\}, and let Sn(τ)S_n(\tau) be the set of permutations avoiding a pattern τS\tau\in S_\ell. Stanley–Wilf conjecture. For any pattern τS\tau\in S_\ell, the limit

limnSn(τ)1n\lim_{n\rightarrow\infty}|S_n(\tau)|^{\frac{1}{n}}

exists and is finite. This conjecture concerns the exponential growth rate of permutation classes defined by pattern avoidance; the supplied text does not state whether it has been resolved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Petter Brändén and Toufik Mansour, “Finite automata and pattern avoidance in words”, arXiv:math/0309269 (2003).

Solutions 0

No solutions have been posted yet.