Stanley-Wilf conjecture

The Stanley-Wilf conjecture, named after Richard P. Stanley and Herbert Wilf, was a conjecture in the combinatorics of permutations. The conjecture was resolved by Gabor Tardos and Adam Marcus in 2004. [ A. Marcus and G. Tardos, [http://www.math.gatech.edu/~adam/papers/permmat/MarcusTardos_permmat.pdf "Excluded Permutation Matrices and the Stanley-Wilf Conjecture"] , "J. Combin. Theory Ser. A" 107 (2004), 153-160.]

tatement

A permutation σ written in the one-line notation is said to "contain the pattern" (shorter permutation) ω if there exists a subsequence of entries of σ that has the same relative order as ω. Otherwise, ω is called a "forbidden pattern" in σ (alternatively, σ "avoids" ω).

Note that subsequence of σ does not have to consist of consecutive entries. For example, permutation σ = (4,1,5,2,3) contains pattern ω = (3,1,2) and avoids ω = (3,2,1).

The Stanley-Wilf conjecture states that for every fixed pattern ω, the number "A"(ω, "n") of permutations σ ∈ "S"_"n" with ω as a forbidden pattern satisfies:

: $$A(omega,n) < C^n ext{ for some }C=C(omega).

A stronger Arratia's conjecture stated that [R. Arratia, [http://www.combinatorics.org/Volume_6/PDF/v6i1n1.pdf "On the Stanley-Wilf Conjecture for the Number of Permutations Avoiding a Given Pattern"] "Electronic J. Combinatorics" 6, N1, 1999.]

: $$C=C(omega) le (k-1)^2 ext{ for all }omega in S_k.

While a result of Regev shows that this bound is tight for the identity pattern permutation, Arratia's conjecture was disproved in 2005 by Michael Albert et al. [M. H. Albert, M. Elder, A. Rechnitzer, P. Westcott, and M. Zabrocki, "On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia", "Adv. in Appl. Math." 36 (2006), 96-105.] A counterexample is provided by the pattern 4231. Whether "C"(ω) is polynomial in "k" remains open. The Marcus-Tardos upper bound is doubly exponential in "k":

: $$C=C(omega) le 15^{2 k^4 inom{k^2}{k ext{ for all }omega in S_k.

History

While the exact time when the conjecture was formulated is uncertain, it is safe to say that the conjecture was open for at least 15 years. Herb Wilf and Richard Stanley formulated their conjectures independently. Gabor Tardos and Adam Marcus proved it indirectly by proving another conjecture, formulated earlier by Zoltan Furedi and Peter Hajnal. Martin Klazar showed in 2000 that the Furedi-Hajnal conjecture implied the Stanley-Wilf conjecture. Previously, the Stanley-Wilf conjecture had been established in special cases and up to the inverse Ackermann function factor. [N. Alon and E. Friedgut, [http://www.math.tau.ac.il/~nogaa/PDFS/permut9.pdf "On the Number of Permutations Avoiding a Given Pattern"] , "J. Combin. Theory, Ser. A." 89 (2000), 133-140.]

Related results

* For patterns ω ∈ "S"₃ the number of ω-avoiding permutations "A"(ω, "n") is the Catalan number. [Miklos Bona, "Combinatorics of Permutations", Chapman Hall-CRC, 2004. ISBN 1-58488-434-7.]

References

External links

* [http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/paramath.pdf A Description of The Stanley-Wilf Conjecture] – by Doron Zeilberger.
*