NB: A PDF version of this announcement (suitable for posting) is also available.

Pattern avoidance and regular languages

Mike Zabrocki
University of York

Thursday, May 19, 2005
L02 Carson Hall, 4 pm
Tea 3:30 pm, Math Lounge

Abstract: The problem of enumerating classes of permutation which avoid certain patterns is not new to algebraic combinatorics but very few general techniques exist for attacking this problem. I will present a proof that permutations which avoid any given pattern and have a fixed number of descents are regular and show how this can be used to generalize the standard notion of pattern avoidance and containment. This will also give a procedure for determining the generating function for patterns which avoid a pattern and have a fixed number of descents.

This is joint work with M. H. Albert, M. Elder, A. Rechnitzer and P. Westcott.

This talk will be accessible to graduate students.