Pattern avoidance in dynamical systems

Dartmouth College, Hanover NH

Investigators

Abstract

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.