# Doctoral Dissertation

### Patterns in Permutations and Involutions, a Structurual and Enumerative Approach

### Abstract:

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.