Cheyne Homberger

Doctoral Dissertation

Patterns in Permutations and Involutions, a Structurual and Enumerative Approach


This dissertation presents a multifaceted look into the structural decomposition of permutation classes. The theory of permutation patterns is a rich and varied field, and is a prime example of how an accessible and intuitive definition leads to increasingly deep and significant line of research. The use of geometric structural reasoning, coupled with analytic and probabilistic techniques, provides a concrete framework from which to develop new enumerative techniques and forms the underlying foundation to this study.

This work is divided into five chapters. The first chapter introduces these techniques through working examples, both motivating the use of structural decomposition and showcasing the utility of their combination with analytic and probabilistic methods. The remaining chapters apply these concepts to separate aspects of permutation classes, deriving new enumerative, statistical, and structural results. These chapters are largely independent, but build from the same foundation to construct an overarching theme of building structure upon disorder.

The main results of this study are as follows. Chapter~\ref{chap:expat} investigates the average number of occurrences of patterns with permutation classes, and proves that the total number of 231-patterns is the same in the classes of 132- and 123-avoiding permutations. Chapter~\ref{chap:involutions} applies structural decomposition to enumerate pattern avoiding involutions. Chapter~\ref{chap:polyclass} uses the theory of grid classes to develop an algorithm to enumerate the so-called polynomial permutation classes, and applies this to the biological problem of genetic evolutionary distance. Finally, we end in Chapter~\ref{chap:fixpat} with an exploration of pattern-packing, and determine the probability distribution for the number of distinct large patterns contained in a permutation.