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.