Stanley–Wilf conjecture

Template:Short description The Stanley–Wilf conjecture, formulated independently by Richard P. Stanley and Herbert Wilf in the late 1980s, states that the growth rate of every proper permutation class is singly exponential. It was proved by Template:Harvs and is no longer a conjecture. Marcus and Tardos actually proved a different conjecture, due to Template:Harvs, which had been shown to imply the Stanley–Wilf conjecture by Template:Harvtxt.

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 Template:Harvtxt observed, this is equivalent to the convergence of the limit

$\underset{n\to \mathrm{\infty }}{\lim }\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 Template:Harvtxt had stated that one could take C to be Template:Nowrap, where k denotes the length of β, but this conjecture was disproved for the permutation Template:Nowrap by Template:Harvtxt. Indeed, Template:Harvtxt 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

$\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\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 pattern or a set of forbidden patterns. For example, numbers strictly between 0 and 1 cannot be growth rates of permutation classes.

Template:Harvtxt 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.

Template:Harvtxt later extended the characterization of growth rates of permutation classes up to a specific algebraic number κ≈2.20. From this characterization, it follows that κ is the least accumulation point of accumulation points of growth rates and that all growth rates up to κ are algebraic numbers. Template:Harvtxt established that there is an algebraic number ξ≈2.31 such that there are uncountably many growth rates in every neighborhood of ξ, but only countably many growth rates below it. Template:Harvtxt characterized the (countably many) growth rates below ξ, all of which are also algebraic numbers. Their results also imply that in the set of all growth rates of permutation classes, ξ is the least accumulation point from above.

In the other direction, Template:Harvtxt proved that every real number at least 2.49 is the growth rate of a permutation class. That result was later improved by Template:Harvtxt, who proved that every real number at least 2.36 is the growth rate of a permutation class.

See also

• Enumerations of specific permutation classes for the growth rates of specific permutation classes.

References

• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.

External links

• How Adam Marcus and Gabor Tardos divided and conquered the Stanley–Wilf conjecture – by Doron Zeilberger.
• Template:Mathworld