Gareth Andrew


Permutation Patterns


Consider two permutations ϕ\phi on nn symbols and τ\tau on mm symbols where mm is greater than nn. In the study of permutation patterns we say that ϕ\phi is contained (or involved) in τ\tau if there is some subsequence of τ\tau which is in the same relative order as the symbols in ϕ\phi and is written as ϕτ\phi \leq \tau

For example, 1232134123 \leq 2134 since the subsequence 234234 (or equivalently 134134) is in the same relative order as 123123 (ie. strictly increasing)

If ϕ\phi is not contained in τ\tau, then we say that τ\tau avoids ϕ\phi.

A Permutation Class is the set of all permutations closed downwards under the containment order i.e. if τ\tau is a member of C\mathcal{C} and ϕτ\phi \leq \tau then ϕ\phi is also a member of C\mathcal{C}

The most common Permutation Class in the study of Permutation Patterns in the the Avoidance Class Avn(ϕ)\mathcal{Av}_n(\phi) of all permutations on nn or less symbols which avoid ϕ\phi.

For example Av(12)\mathcal{Av}(12) is the set of strictly decreasing permutations, i.e. 21, 321, 4321, \ldots

A widely studied feature of Permutation classes is how the size of the class increases with nn. We can write Av(ϕ)| \mathcal{Av}(\phi) | for the size of the class as a function of n, if two different classes have the same growth rate then they are Wilf-equivalent.

Early Results

123-avoiding permutations (Percy MacMahon 1921)

In probably the first result in the field. MacMahon showed that the permutations that can be split into two decreasing sequences i.e. the 123-avoiding permutations, Av(123)\mathcal{Av}(123) are counted by the Catalan numbers.

Erdos-Szekeres theorem (1935)

A theorem due to Erdos and Szekeres can be interpreted in terms of permutation patterns, as every permutation of length at least (k1)(l1)+1(k − 1)(l − 1) + 1 must contain either 12k12 \cdots k or l21l \cdots 21.

231-avoiding permutations (Don Knuth 1968)

In The Art of Computer Programming, Don Knuth considers which permutations can be sorted by stacks, he showed that this is equivalent to the permutations that avoid 231231 and showed that these permutations are also counted by the Catalan numbers, and hence Av(123)\mathcal{Av}(123) and Av(231)\mathcal{Av}(231) are Wilf-equivalent.

Stanley-Wilf conjecture

Richard Stanley and Herb Wilf independently conjectured that all proper pattern avoidance classes have a growth rate which is at most exponential, that is for all permutations there exists some constant AA such that Avn(β)<An|\mathcal{Av}_n(\beta)| < A^n. This conjecture is in some sense surprising as the growth rate of permutations in general is n!n! which is faster than exponential.

This conjecture was proved by Adam Marcus and Gabor Tardos in 2004 and is hence a theory rather than a conjecture. Doron Zeilberger (who rarely disappoints) has a lovely talk "How Adam Marcus and Gabor Tardos Divided and Conquered the Stanley-Wilf Conjecture (An Etude in Paramathematics)" which is also an example of what he calls Para-mathematics which is the fusion of story-telling and mathematics.


I've been reading An introduction to structural methods in permutation patterns by Michael Albert

Another good survery article which is available on Arxiv is Vince Vatter's Permutation Classes