Walks in the positive quadrant and pattern avoidance in permutations

Sergey Kitaev

Monday, October 18, 2004
3:00 pm, 845 Patterson Office Tower

Abstract:

We write permutations as words, whose letters are distinct and usually consist of the integers 1,2,...,n. A pattern is a permutation. An occurrence of a pattern p in a permutation P is "classically" defined as a subsequence in P (of the same length as p) whose letters are in the same relative order as those in p. For example, the permutation 31425 has three occurrences of the pattern 123, namely the subsequences 345, 145, and 125.

Studying patterns in permutations is a very young, but rapidly growing branch of combinatorics with its roots in the work of Rotem, Rogers, and Knuth in the 1970s and early 1980s. The concept of occurrences of patterns in permutations was generalized by Babson and Steingrimsson to occurrences of "generalized patterns," and more recently by Kitaev, to occurrences of "partially ordered generalized patterns," in permutations. Intriguingly, in the case of any type of patterns mentioned above we have a connection to certain walks in the positive quadrant, such as Dyck paths, Motzkin paths, and arbitrary walks on lattice points starting from the origin and remaining in the positive quadrant.