Stanley–Wilf conjecture

The Stanley–Wilf conjecture, formulated independently by Richard P. Stanley and Herbert Wilf in the late 1980s, states that every permutation pattern defines a set of permutations whose growth rate is singly exponential. It was proved by Adam Marcus and Gábor Tardos (2004) and is no longer a conjecture. Marcus and Tardos actually proved a different conjecture, due to Zoltán Füredi and Péter Hajnal (1992), which had been shown to imply the Stanley–Wilf conjecture by Klazar (2000).

Statement

The Stanley–Wilf conjecture states that for every permutation β, there is a constant C such that the number |S_n(β)| of permutations of length n which avoid β as a permutation pattern is at most Cⁿ. As Arratia (1999) observed, this is equivalent to the convergence of the limit

\lim_{n\to\infty} \sqrt[n]{|S_n(\beta)|}.

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)², where k denotes the length of β, but this conjecture was disproved for the permutation β = 4231 by Albert et al. (2006). Indeed, Fox (2013) has shown that C is, in fact, exponential in k for almost all permutations.

Allowable growth rates

The growth rate (or Stanley–Wilf limit) of a permutation class is defined as

\limsup_{n\to\infty} \sqrt[n]{a_n},

where a_n denotes the number of permutations of length n in the class. Clearly not every positive real number can be a growth rate of a permutation class, regardless of whether it is defined by a single forbidden permutation pattern or a set of forbidden patterns. For example, numbers strictly between 0 and 1 cannot be growth rates of permutation classes.

Kaiser & Klazar (2002) proved that if the number of permutations in a class of length n is ever less than the nth Fibonacci number then the enumeration of the class is eventually polynomial. Therefore, numbers strictly between 1 and the golden ratio also cannot be growth rates of permutation classes. Kaiser and Klazar went on to establish every possible growth constant of a permutation class below 2; these are the largest real roots of the polynomials

x^{k+1}-2x^k+1

for an integer k ≥ 2. This shows that 2 is the least accumulation point of growth rates of permutation classes.

Vatter (2011) later extended the characterization of growth rates of permutation classes up to κ≈2.20, from which it follows that κ is the least accumulation point of accumulation points of growth rates. The growth rates between 2 and κ are also algebraic. Vatter (2010) also proved that every real number at least 2.49 is the growth rate of a permutation class. Bevan (2014) has since improved on that result, showing that every real number at least 2.36 is the growth rate of a permutation class.

Notes

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, MR 2199982 .
Arratia, Richard (1999), "On the Stanley–Wilf conjecture for the number of permutations avoiding a given pattern", Electronic Journal of Combinatorics, 6: N1, MR 1710623 .
Bevan, David (2014), Intervals of permutation class growth rates, arXiv:1410.3679 .
Fox, Jacob (2013), Stanley-Wilf limits are typically exponential, arXiv:1310.8378 .
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, MR 1171777 .
Kaiser, Tomáš; Klazar, Martin (March 2002), "On growth rates of closed permutation classes", Electronic Journal of Combinatorics, 9 (2): Research paper 10, 20, MR 2028280 .
Klazar, Martin (2000), "The Füredi–Hajnal conjecture implies the Stanley–Wilf conjecture", Formal Power Series and Algebraic Combinatorics (Moscow, 2000), Springer, pp. 250–255, MR 1798218 .
Klazar, Martin (2010), "Some general results in combinatorial enumeration", Permutation patterns, London Math. Soc. Lecture Note Ser., 376, Cambridge: Cambridge Univ. Press, pp. 3–40, doi:10.1017/CBO9780511902499.002, MR 2732822 .
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, MR 2063960 .
Vatter, Vincent (2010), "Permutation classes of every growth rate above 2.48188", Mathematika, 56 (1): 182–192, doi:10.1112/S0025579309000503, MR 2604993 .
Vatter, Vincent (2011), "Small permutation classes", Proc. Lond. Math. Soc. (3), 103 (5): 879–921, doi:10.1112/plms/pdr017, MR 2852292 .

External links

This article is issued from Wikipedia - version of the 3/7/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.