Stanley–Wilf conjecture

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

The Stanley–Wilf conjecture states that for every permutation β, there is a constant C such that the number |Sn(β)| of permutations of length n which avoid β as a permutation pattern is at most Cn. 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)2, 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[edit]

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

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

where an 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 number at least 2.36 is the growth rate of a permutation class.

See also[edit]

Notes[edit]

References[edit]

External links[edit]