Stanley-Wilf conjecture

From Wikipedia, the free encyclopedia

The Stanley-Wilf conjecture is 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).

Stanley-Wilf conjecture states that for every fixed pattern ω, the number A(ω,n) of permutations \sigma \in S_n with ω as a forbidden pattern satisfies:

A(ω,n) < Cn for some C = C(ω).

A stronger (still open) Arratia's conjecture states that [2]

C=C(\omega) \le (k-1)^2 \ for all \omega \in S_k.

A result of Regev shows that this bound is tight for the identity pattern permutation. The Marcus-Tardos upper bound is doubly exponential in k:

C=C(\omega) \le 15^{2 k^4 \binom{k^2}{k}}\ for all \omega \in S_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 conjecture was established in special cases and up to the inverse Ackermann function factor.[3]

[edit] Related results

  • For patterns \omega \in S_3 the number of ω-avoiding permutations A(ω,n) is the Catalan number.[4]

[edit] References

  1. ^ A. Marcus and G. Tardos, "Excluded Permutation Matrices and the Stanley-Wilf Conjecture", J. Combin. Theory Ser. A 107 (2004), 153-160.
  2. ^ R. Arratia, "On the Stanley-Wilf Conjecture for the Number of Permutations Avoiding a Given Pattern" Electronic J. Combinatorics 6, N1, 1999.
  3. ^ N. Alon and E. Friedgut, "On the Number of Permutations Avoiding a Given Pattern", J. Combin. Theory, Ser. A. 89 (2000), 133-140.
  4. ^ Miklos Bona, Combinatorics of Permutations, Chapman Hall-CRC, 2004. ISBN 1-58488-434-7.

[edit] External links

Retrieved from "http://en.wikipedia.org../../../s/t/a/Stanley-Wilf_conjecture_8071.html"