Conference on Permutation Patterns 2010

2010 年排列模式会议

• 批准号: 1003908
• 负责人: Sergi Elizalde
• 金额: $ 1.45万
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-03-15 至 2011-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1003908&HistoricalAwards=false
• 关键词: Conference; Permutation; Patterns; 2010

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.

本次会议致力于排列模式，即关于参与顺序的排列的研究。用单行表示法编写的排列模式是一个子序列，其条目具有规定的相对顺序。这个定义可以在各种不同的上下文中重新表述，例如几何的，其中排列通过其图来标识，以及模型理论的，其中排列被视为定义有两个线性阶的集合。 特别令人感兴趣的是在参与下封闭的排列集。 这些正是可以通过避免（即不涉及）规定的排列集（“禁止模式”）来定义的排列集。会议主题包括枚举问题、算法问题以及排列模式的应用和概括。从历史上看，排列中模式包含的研究起源于 20 世纪 60 年代和 1970 年代的两个独立流派。其中一个本质上是组合问题，集中于一小组（通常为 1 或 2）短（长度最多 4 个）禁止模式的排列的枚举问题。另一个来自理论计算机科学，关注由常见排序机制及其组合产生的集合。在过去十年左右的时间里，这两条线索更加紧密地结合在一起，这种相互作用创造了一个新的、快速发展的组合数学领域，与理论计算机科学、可计算性和复杂性理论、代数和计算生物学具有重要的相互作用，仅举几例。 除了对排序机制和枚举问题的持续兴趣之外，还出现了主要的新研究领域，包括类的结构理论、类的渐近行为、广义模式避免、包装密度、算法和可判定性问题以及几何方法。