*** Welcome to piglix ***

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).

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

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.

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

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.


...
Wikipedia

...