Permutation class

In the study of permutations and permutation patterns, a permutation class is a set ${\displaystyle C}$ of permutations such that every pattern within a permutation in ${\displaystyle C}$ is also in ${\displaystyle C}$. That is, it is a downset in the permutation pattern order.[1] A permutation class may also be known as a pattern class, closed class, or simply class of permutations.

Every permutation class can be defined by the minimal permutations which do not lie inside it, its basis.[2] A principal permutation class is a class whose basis consists of only a single permutation. Thus, for instance, the stack-sortable permutations form a principal permutation class, defined by the forbidden pattern 231. However, some other permutation classes have bases with more than one pattern or even with infinitely many patterns.

A permutation class that does not include all permutations is called proper. In the late 1980s, Richard Stanley and Herbert Wilf conjectured that for every proper permutation class ${\displaystyle C}$, there is some constant ${\displaystyle K}$ such that the number ${\displaystyle |C_{n}|}$ of length-${\displaystyle n}$ permutations in the class is upper bounded by ${\displaystyle K^{n}}$. This was known as the Stanley–Wilf conjecture until it was proved by Adam Marcus and Gábor Tardos.[3] However although the limit

${\displaystyle \lim _{n\to \infty }|C_{n}|^{1/n}}$

(a tight bound on the base of the exponential growth rate) exists for all principal permutation classes, it is open whether it exists for all other permutation classes.[4]

Two permutation classes are called Wilf equivalent if, for every ${\displaystyle n}$, both have the same number of permutations of length ${\displaystyle n}$. Wilf equivalence is an equivalence relation and its equivalence classes are called Wilf classes. They are the combinatorial classes of permutation classes. The counting functions and Wilf equivalences among many specific permutation classes are known.

References

1. Kitaev, Sergey (2011), Patterns in permutations and words, Monographs in Theoretical Computer Science, Heidelberg: Springer, p. 59, doi:10.1007/978-3-642-17333-2, ISBN 978-3-642-17332-5, MR 3012380
2. Kitaev (2011), Definition 8.1.3, p. 318.
3. 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.
4. Albert, Michael (2010), "An introduction to structural methods in permutation patterns", Permutation patterns, London Math. Soc. Lecture Note Ser., 376, Cambridge Univ. Press, Cambridge, pp. 153–170, doi:10.1017/CBO9780511902499.008, MR 2732828