Pattern avoidance in dynamical systems

该提案由组合学项目和EPSCoR共同资助。PI提出探索模式回避和动力系统之间的新联系。这种意想不到的联系的来源是基于以下想法。给定一个从完全有序集合到自身的映射，考虑从不同的初始点开始迭代映射得到的有限序列（轨道）。轨道上的点的相对顺序决定了排列。事实证明，在一维区间上的分段单调映射中，有一些排列在任何轨道上都不会发生。这些被称为禁忌模式。如果一个模式被禁止用于给定的映射，那么任何包含它作为连续模式的更长的排列也被禁止。这一性质将映射的禁止模式的研究与避免连续模式的排列研究联系起来，这是一个在组合学文献中受到关注的主题，包括PI的几篇论文。这种从组合角度研究动态系统的新方法的目标之一是更好地理解映射的禁止模式集，包括其属性如何与映射的属性相关，每个给定长度有多少模式，如何通过算法找到这些模式，以及哪些模式集可以成为映射的禁止模式。PI已经通过回答上述移位系统和逻辑图的一些问题，在实现这一目标方面取得了一些进展。

This proposal is being cofunded by the Combinatorics Program and EPSCoR.The PI proposes to explore a novel connection between pattern avoidance and dynamical systems. The source of this unexpected connection is based on the following idea. Given a map from a totally ordered set to itself, consider the finite sequences (orbits) that are obtained by iterating the map, starting from di®erent initial points. The relative order of the points in the orbit determines a permutation. It turns out that, in the case of piecewise monotone maps on one-dimensional intervals, there are some permutations that do not occur in any orbit. These are called forbidden patterns. If a pattern is forbidden for a given map, then any longer permutation that contains it as a consecutive pattern is forbidden as well. This property relates the study of forbidden patterns of maps to the study of permutations avoiding consecutive patterns, a subject that has received attention in the combinatorics literature, including several papers by the PI. One of the goals of this new approach to study dynamical systems from a combinatorial perspective is to better understand the set of forbidden patterns of a map, including how its properties are related to the properties of the map, how many patterns there are of each given length, how to algorithmically find these patterns, and which sets of patterns can be forbidden patterns of a map. The PI has already made some progress towards this goal by answering some of the above questions for shift systems and logistic maps.