The Structure of Permutation Classes

点击翻译按钮获取中文摘要

The overarching aim of this project is to expand the structural theory of permutation classes, to unify the disparate strands coming together in this theory, and to test the power of the emerging viewpoint and toolbox by bringing them to bear on problems of exact enumeration and the characterization of growth rates.Historically, the study of permutation classes 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.