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.
This project explores an unexpected connection between pattern-avoiding permutations and dynamical systems. This connection is based on the fact that for most one-dimensional maps, there are permutations that are never realized by the relative order of the elements of an orbit. These sets of permutations, called forbidden patterns of the map, are closed under consecutive pattern containment, which makes them interesting from a combinatorial perspective. One of the main outcomes of the project is a better understanding of the sets of forbidden patterns of some important dynamical systems, such as shifts, beta-shifts, and signed shifts (which include the logistic map). Understanding these patterns has applications to the design of new and better tests to distinguish deterministic from random sequences. Using combinatorial tools, we characterize and enumerate allowed and forbidden patterns of different maps, and study some of their properties. Other outcomes belong to classical combinatorics, the main one being the proof of the 12-year-old Consecutive Monotone Pattern Conjecture, which states that the number of permutations avoiding the consecutive pattern 12...m grows faster than the number of permutations avoiding any other consecutive pattern of length m The PI has four graduate students (two female) working on topics related to this project.
