Permutation Patterns

Definitions

Consider two permutations $\phi$ on $n$ symbols and $\tau$ on $m$ symbols where $m$ is greater than $n$. 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, $123 \leq 2134$ since the subsequence $234$ (or equivalently $134$) is in the same relative order as $123$ (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 $\mathcal{C}$ and $\phi \leq \tau$ then $\phi$ is also a member of $\mathcal{C}$

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

For example $\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 $n$. We can write $| \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, $\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 $(k − 1)(l − 1) + 1$ must contain either $12 \cdots k$ or $l \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 $231$ and showed that these permutations are also counted by the Catalan numbers, and hence $\mathcal{Av}(123)$ and $\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 $A$ such that $|\mathcal{Av}_n(\beta)| < A^n$. This conjecture is in some sense surprising as the growth rate of permutations in general is $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.

References

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