Stanley–Wilf conjecture
The Stanley–Wilf conjecture, formulated independently by Richard P. Stanley and Herbert Wilf in the late 1980s, was a conjecture in permutation patterns until it was resolved by Adam Marcus and Gábor Tardos in (2004). Marcus and Tardos actually proved a different conjecture, due to Zoltán Füredi and Péter Hajnal from (1992), which had been shown to imply the Stanley-Wilf conjecture by Klazar (2000).
[edit] Statement
The Stanley–Wilf conjecture states that for every permutation β, there is a constant C such that the number |Avn(β)| of permutations of length n which avoid β is at most Cn.
The upper bound given by Marcus and Tardos for C is exponential in the length of β. A stronger conjecture of Arratia (1999) had stated that one could take C to be (k−1)2, where k denotes the length of β, but this conjecture was disproved for the permutation β = 4231 by Albert et al. (2006).
[edit] References
- Albert, Michael H.; Elder, Murray; Rechnitzer, Andrew; Westcott, P.; Zabrocki, Mike (2006), "On the Stanley-Wilf limit of 4231-avoiding permutations and a conjecture of Arratia", Advances in Applied Mathematics 36 (2): 96–105, doi:10.1016/j.aam.2005.05.007, MR2199982.
- Arratia, Richard (1999), "On the Stanley–Wilf conjecture for the number of permutations avoiding a given pattern", Electronic Journal of Combinatorics 6: Note, N1, 4pp, MR1710623, http://www.emis.de/journals/EJC/Volume_6/Abstracts/v6i1n1.html.
- Füredi, Zoltán; Hajnal, Péter (1992), "Davenport-Schinzel theory of matrices", Discrete Mathematics 103 (3): 233–251, doi:10.1016/0012-365X(92)90316-8, MR1171777.
- Klazar, Martin (2000), "The Füredi-Hajnal conjecture implies the Stanley-Wilf conjecture", Formal power series and algebraic combinatorics (Moscow, 2000): 250–255, MR1798218.
- Marcus, Adam; Tardos, Gábor (2004), "Excluded permutation matrices and the Stanley-Wilf conjecture", Journal of Combinatorial Theory. Series A 107 (1): 153–160, doi:10.1016/j.jcta.2004.04.002, MR2063960.
