Stanley–Wilf Conjecture
   HOME

TheInfoList



OR:

The Stanley–Wilf conjecture, formulated independently by Richard P. Stanley and
Herbert Wilf Herbert Saul Wilf (June 13, 1931 – January 7, 2012) was an American mathematician, specializing in combinatorics and graph theory. He was the Thomas A. Scott Professorship of Mathematics, Thomas A. Scott Professor of Mathematics in Combinatori ...
in the late 1980s, states that the growth rate of every proper
permutation class In the study of permutations and permutation patterns, a permutation class is a set C of permutations for which every pattern within a permutation in C is also in C. In other words, a permutation class is a hereditary property of permutations, or a ...
is singly exponential. It was proved by and is no longer a conjecture. Marcus and Tardos actually proved a different conjecture, due to , which had been shown to imply the Stanley–Wilf conjecture by .


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 In combinatorial mathematics and theoretical computer science, a (classical) permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of entries representing the result of a ...
is at most ''C''''n''. As observed, this is equivalent to the convergence of the limit :\lim_ \sqrt The upper bound given by Marcus and Tardos for ''C'' is
exponential Exponential may refer to any of several mathematical topics related to exponentiation, including: * Exponential function, also: **Matrix exponential, the matrix analogue to the above *Exponential decay, decrease at a rate proportional to value * Ex ...
in the length of ''β''. A stronger conjecture of had stated that one could take ''C'' to be , where ''k'' denotes the length of ''β'', but this conjecture was disproved for the permutation by . Indeed, has shown that ''C'' is, in fact, exponential in ''k'' for
almost all In mathematics, the term "almost all" means "all but a negligible quantity". More precisely, if X is a set (mathematics), set, "almost all elements of X" means "all elements of X but those in a negligible set, negligible subset of X". The meaning o ...
permutations.


Allowable growth rates

The growth rate (or Stanley–Wilf limit) of a permutation class is defined as :\limsup_ \sqrt 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 pattern or a set of forbidden patterns. For example, numbers strictly between 0 and 1 cannot be growth rates of permutation classes. proved that if the number of permutations in a class of length ''n'' is ever less than the ''n''th
Fibonacci number In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...
then the enumeration of the class is eventually polynomial. Therefore, numbers strictly between 1 and the
golden ratio In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their summation, sum to the larger of the two quantities. Expressed algebraically, for quantities and with , is in a golden ratio to if \fr ...
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^-2x^k+1 for an integer ''k'' ≥ 2. This shows that 2 is the least accumulation point of growth rates of permutation classes. 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. 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. 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, proved that every real number at least 2.49 is the growth rate of a permutation class. That result was later improved by , 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 In the study of permutation patterns, there has been considerable interest in enumerating specific permutation classes, especially those with relatively few basis elements. This area of study has turned up unexpected instances of Wilf equivalence, w ...
for the growth rates of specific permutation classes.


Notes


References

*. *. *. *. *. *. *. *. *. *. *. *. *.


External links


How Adam Marcus and Gabor Tardos divided and conquered the Stanley–Wilf conjecture
– by
Doron Zeilberger Doron Zeilberger (; born 2 July 1950) is an Israeli-American mathematician, known for his work in combinatorics. Education and career He received his doctorate from the Weizmann Institute of Science in 1976, under the direction of Harry Dym, w ...
. * {{DEFAULTSORT:Stanley-Wilf conjecture Enumerative combinatorics Theorems in discrete mathematics Permutation patterns