Michael Albert

Growth Rates of Pattern Classes.

Abstract:

A pattern class is a set of permutations closed under the natural combinatorial notion of subpermutation. The study of pattern classes, and in particular their enumeration has been an active area of research; spurred initially by the observation of strange coincidences in their enumerative sequences. The resolution, early this century, by Marcus and Tardos of the Stanley-Wilf conjecture ([6]) has focused attention on the exponential growth rates of these classes.

In addition to the question of which growth rates can occur (following [5] and [7]), it seems natural to follow the plan of [4] and investigate circumstances under which the enumeration of a pattern
class can be accomplished "automatically", typically owing to some natural underlying correspondence with a regular or context-free language.

We will introduce, survey, and look ahead to the future of this area.

References:

[1] M.H. Albert, M.D. Atkinson, N. Ruskuc: Regular closed sets of permutations, Theoretical Computer Science 306 (2003), 85-100.

[2] M. H. Albert, N. Ruskuc, S. A. Linton: The insertion encoding, Electronic J. Combinatorics 12(1) Paper R47 (31 pages).

[3] M.H. Albert, M. Elder, A. Rechnitzer, P. Westcott and M. Zabrocki: On the Stanley-Wilf limit of 4231-avoiding permutations and a conjecture of Arratia, Advances in Applied Mathematics, Volume 36, Issue 2, February 2006, Pages 96-105.

[4] Mireille Bousquet-Mélou, Rational and algebraic series in combinatorial enumeration, http://arxiv.org/abs/0805.0588

[5] T. Kaiser, M. Klazar, On growth rates of closed permutation classes, Electron. J. Combin. 9 (2) (2003) R10, 20.

[6] A. Marcus, G. Tardos, Excluded Permutation Matrices and the Stanley-Wilf Conjecture, J. Combin. Theory Ser. A 107 (2004), no. 1, 153-160.

[7] Vince Vatter, Small Permutation Classes,
http://turnbull.mcs.st-and.ac.uk/~vince/publications/small-classes/