Conference on Permutation Patterns 2010

Dartmouth College, Hanover NH

Investigators

Abstract

This conference is devoted to permutation patterns, i.e., the study of permutations with respect to the involvement order. A pattern in a permutation written in one-line notation is a subsequence whose entries have a prescribed relative order. This definition can be re-phrased in various different contexts, e.g. geometrical, where a permutation is identified with its plot, and model-theoretic, where a permutation is taken to be a set with two linear orders defined on it. Of particular interest are the sets of permutations which are closed under involvement. These are precisely the sets of permutations which can be defined by avoiding (i.e. not involving) prescribed sets of permutations ("forbidden patterns"). The conference topics include enumeration questions, algorithmic problems, and applications and generalizations of permutation patterns. Historically, the study of pattern containment in permutations arose from two independent streams in 1960s and 1970s. One was combinatorial in nature, and concentrated on the enumeration problems for permutations with a small set (size 1 or 2, typically) of short (length up to 4) forbidden patterns. The other was coming from Theoretical Computer Science, and was concerned with sets arising from common sorting mechanisms and their combinations. In the past 10 years or so these two strands have come much closer together, and this interaction has created a new, fast developing area of combinatorics, with significant interactions with Theoretical Computer Science, the Theory of Computability and Complexity, Algebra, and Computational Biology, to name only a few. Apart from the continued interest in sorting mechanisms and enumeration problems, major new strands of research have emerged including the structural theory of classes, the asymptotic behavior of classes, generalized pattern avoidance, packing densities, algorithmic and decidability problems, and geometrical methods.