Abstract
dc:description.abstractOriginally discovered in relation to the simple permutations, the structures known as pin sequences have since appeared in many varied and unexpected places throughout the field of permutation patterns, notably in connection with substitution-closed classes and infinite antichains. Additionally, pin sequences, along with the <i>pin permutation classes</i> they naturally define, have proven to be a very efficient means of producing counterexamples, notably being used recently to construct well-quasi-ordered permutation classes with non-algebraic generating functions. The study of pin classes as objects of interest in their own right, on the other hand, has been somewhat limited, though precedent certainly exists. In this thesis we aim to initiate a more systematic study of pin permutation classes than has previously been attempted.<br></br><br></br> We begin in Chapter 1 with an introductory discussion of permutation classes, placing this field of study in a historical context and mentioning some of the major open problems, before introducing pin sequences in connection with the simple permutations. In Chapter 2 we introduce the notion of a <i>centred permutation</i>: a permutation along with a defined origin point. This will transpire to be the most natural context in which to situate the study of pin classes, chiefly because it will allow us to utilise the ⊞-sum, an operation on the centred permutations. We begin to study pin permutation classes in earnest in Chapter 3, defining pin words and the (centred and uncentred) permutation classes they generate. Our major result here is that every pin permutation class has a proper growth rate; we also describe an effective procedure for determining the growth rate of any given pin class by reducing to a simpler combinatorial problem on words. We conclude our study of pin classes in full generality in Chapter 4 by determining the best possible bounds on the growth rate of a pin class subject to an important characteristic: the number of quadrants its defining pin word visits recurrently.<br></br><br></br> In the second half of this thesis we restrict our focus to a large subfamily of pin classes named <i>V</i>-classes: these are the pin classes contained entirely in the upper half-plane. In Chapter 5 we initiate this programme of study by setting up a correspondence between the <i>V</i>-classes and binary sequences; this will prove to be a vital simplifying step in studying these classes systematically. We make a digression in Chapter 6 to briefly study binary factorial languages: this will equip us with the language and machinery required to describe a large collection of <i>V</i>-classes defined by avoidance, many of which will prove indispensable in constructing the growth rate bounds required in the remaining chapters. In Chapter 7 we examine the finer structure of the so-called <i>recurrent V</i>-classes, demonstrating that the generating functions and bases of the classes in this large collection can be effectively determined subject to solving some combinatorial problems on binary factorial languages. Finally, in Chapter 8 we investigate the structure of the set <b>V</b> of <i>V</i>-class growth rates. We will discover a number of unexpected features of this set, including the existence of both intervals and gaps of <i>V</i>-class growth rates, as well as leaving many interesting open problems for further study.<br></br><br></br> We conclude in Chapter 9 by discussing some possible directions for further research, including a potential application to the classification of small infinite antichains.
Degree
thesis:*- Name dc:type.qualificationname
- phd
- Level dc:type.qualificationlevel
- doctoral
- Grantor dc:publisher.institution
- The Open University
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Jarvis, Ben
Rights
- Language dc:language
- en