Stanley–Wilf conjecture for permutation pattern avoidance

At least 22 years old · documented by

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

lim⁡n→∞∣Sn(τ)∣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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.