Today we examine a topic known as combinatorial pattern avoidance. There has been an explosion of interest in this field of late; see, for instance, the international permutation patterns conference, or any recent issues of your favorite discrete mathematics journal. I was first introduced to this field by Bruce Sagan at Michigan State’s SURIEM, an outstanding research program for undergraduate mathematicians.
We start from the ground up. For a positive integer , let . A permutation is a bijection from to itself. So, for instance, we could have with . Writing a permutation in this form is incredibly unwieldy, and hence we will use the one line notation , where . Continuing our example from above, we would have . (Those familiar with these constructs may ask why we are not using the cycle notation; we will be using permutations purely as combinatorial strings and disregarding their group structure, hence the form). Given a permutation , we say that has length .
Now given any string of positive integers , we may standardize to create by replacing the smallest letter in with a , the second smallest letter in with a , and in general the th smallest letter with . For instance, standardizes to . Two words which have the same standardization are said to be order isomorphic or in the same relative ordering, for reasons which become clear upon some thought. (Really what we are doing here is choosing a standard representative for strings based on their relative ordering; for instance, we want all three letter strings which go Small, Big, Medium to be considered the same, as they all standardize to .
We may now define containment and avoidance. Given a permutation of length and a permutation of length , with , we say that contains if there exist indices such that standardizes to . If this is not the case, then we say avoids . When we ask questions such as “does contain ?” we will refer to as the pattern, hence the name of the field.
Let’s have a few examples. Let and . Then I claim contains but avoids . I would encourage you to try and verify this for yourself before reading on. For verification, note that contains the subsequence , which standardizes to . However, does not contain any increasing subsequence of length , and hence cannot contain . There are a couple remarks to be made following this example. First, note that contains several subsequences which standardize to , namely , and . For now, we won’t worry too much about counting how many subsequences standardize to our pattern, and just focus on whether or not the pattern is contained at all. The second pedagogical remark is simply to reinforce that the subsequences taken above need not be adjacent in the original permutation, they just need to be taken in their original ordering. The subject of vincular pattern avoidance deals with placing additional restrictions on the containment, such as forcing the subsequence to be consecutive. But that is a topic for another day.
Now that we have defined the notion of permutation patterns and their containment, I would like to briefly end by listing some questions that are studied in this field, and some reasons for why this field is of interest in the first place. The list is in no particular order. I have denoted reasons of interest by “ROI” and questions by “Q”
- ROI: A stack is a data storage unit studied and used frequently in computer science. One operation you can try to use them for is to sort a string into increasing order; it turns out that the stack sortable permutations are exactly those which avoid the pattern . This is a result due to Knuth, and this result is largely credited for the explosion of interest in this area.
- Q: Fix a permutation of length . As an explicit function of , how many permutations of length avoid ? Remarkably, if is any permutation of length , then the answer is given by the Catalan numbers.
- Q: If we cannot give an explicit formula to the question above, can we give asymptotics? One of the biggest open problems in the field currently is to find a tight growth rate for the number of permutations avoiding the pattern .
- ROI: Permutation patterns are beginning to be used in dynamical modeling. See, for instance, “The Frequence of Pattern Occurrence in Random Walks” by S. Elizalde and M. Martinez.
- Q: What is the computational complexity of determining whether or not a given permutation contains another permutation? What if we restrict the class of permutations we examine?
- Q: Let denote the set of all permutations of any arbitrary (finite) length, and put an ordering on by if and only if contains as a pattern. Then this can readily be checked to be a partially ordered set (poset) known as the permutation pattern poset. This has been an object of intense study recently; a large open problem is finding the Mobius function of this poset.
I think that this is a good list for now. If you are interested in more, here is a decent place to start. Alternatively, come back to my blog in a week or so! I will plan on proving some more results from this area, starting with the Catalan result in the second bullet point above.
As always, thanks for reading!