Higher-Order Pattern Containment

Permutations are orderings of a set of objects, typically positive integers. They can model aspects of many different problems and scenarios, and they are used throughout mathematics. A permutation pattern is a subset of a permutation that appears in a particular order. For example, it might have an increasing subsequence of some length, or it might avoid having a large number followed by two smaller numbers. The presence or absence of particular patterns can be critical to features of the data that the permutation is modeling, which has led to great interest in the analysis of permutation patterns for the past several decades. The goal of this project is to establish a broader context to the traditional study of permutation patterns. Historically, research in this area has been almost entirely in terms of a binary question: does a permutation contain a given pattern or does the permutation avoid it? Recent evidence has shown that the specific number of times that a pattern appears is of great importance, and consequently a more granular notion of pattern containment should be studied. Specifically, the question should instead be: how many times does the permutation contain the pattern? This project will address that higher-order question in several ways, with implications for combinatorics and its connections to algebra, topology, and computer science. The first part of the project will extend what is already known about higher-order containment in a special but important case. A relationship was recently established between individual occurrences of two patterns and repeated letters in reduced decompositions. This is a critical step enabling the study of how pattern occurrences can impact objects like the Bruhat order, the connection between length and reflection length, and the frequency of letters in a reduced decomposition. It also gives a new avenue for enumerating permutations that contain fixed numbers of pattern occurrences. The second phase of the project will bring the perspective of higher-order pattern containment to other pattern sets. Several sets seem especially amenable to this pursuit, and their analysis will pave the way for studying higher-order pattern containment more generally. The main tools throughout this project will be a dictionary translating between permutation patterns and reduced decompositions, and a technique for manipulating reduced decompositions to reveal properties of the permutations that they describe. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.