The Structure of Permutation Classes

排列类的结构

• 批准号: 1301692
• 负责人: Vincent Vatter
• 金额: $ 16万
• 依托单位: University of Florida
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1301692&HistoricalAwards=false
• 关键词: Structure; 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.

这个项目的首要目标是扩展置换类的结构理论，统一这个理论中不同的分支，并通过将它们应用于精确枚举和增长率的表征问题来测试新兴观点和工具箱的能力。历史上，置换类的研究起源于20世纪60年代和70年代的两个独立的流派。一个是组合的性质，并集中在枚举问题的排列与一个小的集合（大小1或2，通常）的短（长度高达4）禁止模式。另一个来自理论计算机科学，关注的是由常见的排序机制及其组合产生的集合。在过去的10年左右，这两条链已经走得更近了，这种相互作用创造了一个新的，快速发展的组合学领域，与理论计算机科学，可计算性和复杂性理论，代数和计算生物学有着重要的相互作用，仅举几例。除了继续感兴趣的排序机制和枚举问题，主要的新的研究领域已经出现，包括类的结构理论，类的渐近行为，广义模式避免，包装密度，算法和可判定性问题，和几何方法。