Algebraic Combinatorics Seminar
####
**
UNIVERSITY OF KENTUCKY **

ALGEBRAIC COMBINATORICS SEMINAR

845 PATTERSON OFFICE TOWER

FALL 2004

####

##
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.