Permutation Patterns 2011

这笔赠款支持2011年夏天在加州圣路易斯奥比斯波的加州理工州立大学举行的关于排列模式的会议。与以往的会议一样，我们希望吸引更多的研究生和初级研究人员。我们预计总共约有70人参加，约35次会谈。会议的主题是排列模式，更广泛地说，是数学对象中的模式概念，如分区、单词和其他结构，如基因组序列。长度为n的排列是整数1到n的重新排列。如果可以通过删除排列tau中的一些整数并按1到k的顺序重新编号剩余的整数来找到排列sigma，那么我们说sigma涉及tau。对排列模式的研究涉及到理解这种参与关系。参与的定义可以在各种语境中重新表述，例如几何或模型理论。在计算机科学中，在对诸如堆栈、队列和有限网络之类的排序设备的研究中，可以发现在参与下闭合的排列集合。在过去十年左右的时间里，来自组合学和计算机科学的思想汇聚在一起，创造了数学、理论计算机科学、可计算性和复杂性理论以及计算代数等新的和发展中的研究途径。除了对组合学和排序机制问题的持续关注外，一些主要的新方向包括排列模式的结构理论(构造、分解等)、渐近性、变种和推广，如广义模式避免的概念、填充密度、算法和可判断性问题以及几何方法。在过去的几十年里，排列模式的研究已经成为列举组合学的一个重要分支。最近出现了数百篇关于排列模式的论文。该领域的研究人员数量正在增加，自2003年召开排列模式年度会议以来，出席会议的人数一直在稳步增加。研究在北美、欧洲、亚洲和澳大拉西亚都是国际性的。这是一个全球感兴趣的主题。排列模式的主题具有相对较低的数学开销。用于研究排列模式的一些常用工具包括生成函数、算法设计、实验计算；这些工具渗透到组合学和计算机科学中。因此，这个课题对入门级的研究人员来说是可以理解的。我们的会议将为年轻的研究人员提供了解这一理论并开始做出贡献的机会。参加最近两次会议的研究生人数表明，这一主题领域的研究正在增长。

This grant supports a conference on Permutation Patterns in the Summer of 2011 at the California Polytechnic State University in San Luis Obispo, California. As in past conferences, we expect to attract many graduate students and junior researchers. In total, we expect around 70 participants and around 35 talks. The topic of the conference is permutation patterns and, more generally, the concept of pattern in mathematical objects such as partitions, words, and other structures such as genome sequences. A permutation of length n is a rearrangement of the integers 1 through n. If a permutation sigma can be found by erasing some of the integers in a permutation tau and renumbering the remaining integers in sequential order with 1 through k, then we say that sigma is involved in tau. The study of permutation patterns is concerned with understanding this involvement relation.The definition of involvement can be rephrased in a variety of contexts such as geometric or model-theoretic. In computer science, sets of permutations which are closed under involvement are found in the study of sorting devices such as stacks, queues, and finite networks. The past decade or so has seen a confluence of ideas stemming from combinatorics and the computer science, creating new and developing avenues of research in mathematics, theoretical computer science, computability and complexity theory, and computational algebra. In addition to the continuing interest in the combinatorics and sorting mechanism problems, some major new directions include the structural theory of permutation patterns (constructions, decompositions, etc.), asymptotics, variations and generalizations such as the concept of generalized pattern avoidance, packing densities, algorithmic and decidability problems, and geometrical methods.The study of permutation patterns has emerged as a significant branch of enumerative combinatorics over the past couple of decades. Hundreds of papers on permutation patterns have appeared relatively recently. The number of researchers in the area is increasing and the attendance in the annual conference on permutation patterns has steadily grown since its inception in 2003. Research is international across North America, Europe, Asia, and Australasia. This is a subject of global interest.The subject of permutation patterns has a relatively low mathematical overhead. Some of the commonly used tools used to investigate permutation patterns include generating functions, algorithm design, experimental computation; tools which permeate combinatorics and computer science. Therefore, this subject is accessible to entry-level researchers. Our conference will provide opportunities for young researchers to learn about and begin to make contributions to the theory. The number of graduate students who have attended the last two meetings is an indication that research in this subject area is growing.