Stanley-Wilf conjecture
From Wikipedia, the free encyclopedia
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.[1]
Contents |
[edit] Statement
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 σ ∈ Sn with ω as a forbidden pattern satisfies:
- A(ω,n) < Cn for some C = C(ω).
A stronger Arratia's conjecture stated that[2]
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.[3] 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:
[edit] 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.[4]
[edit] Related results
- For patterns ω ∈ S3 the number of ω-avoiding permutations A(ω, n) is the Catalan number.[5]
[edit] References
- ^ A. Marcus and G. Tardos, "Excluded Permutation Matrices and the Stanley-Wilf Conjecture", J. Combin. Theory Ser. A 107 (2004), 153-160.
- ^ R. Arratia, "On the Stanley-Wilf Conjecture for the Number of Permutations Avoiding a Given Pattern" Electronic J. Combinatorics 6, N1, 1999.
- ^ 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.
- ^ N. Alon and E. Friedgut, "On the Number of Permutations Avoiding a Given Pattern", J. Combin. Theory, Ser. A. 89 (2000), 133-140.
- ^ Miklos Bona, Combinatorics of Permutations, Chapman Hall-CRC, 2004. ISBN 1-58488-434-7.