Pin classes II: Small pin classes
Robert Brignall, Ben Jarvis · 2024
Read Pin classes II: Small pin classes by Robert Brignall, Ben Jarvis (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-03525.txt.
Introduction
Robert Brignall and Ben Jarvis study pin classes of permutations in a 2024 math paper, the second in a series. A pin permutation is an endless pattern whose finite pieces form a class. Such classes matter for the structure of pattern free permutations and for counting results that grow from them.
The authors find a sharp threshold near a growth rate of three point two eight. Below that rate, only countably many pin classes exist, and each rests on a periodic pattern. At that exact rate, uncountably many distinct classes appear. They also classify all growth rates up to the threshold. The result draws a clean line in a field where class counts can explode.
Catalog record
| CREATOR | Robert Brignall, Ben Jarvis |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 176 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-03525
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pin classes II: Small pin classes Robert Brignall, Ben Jarvis Abstract Pin permutations play an important role in the structural study of permutation classes, most notably in relation to simple permutations and well-quasi-ordering, and in enumerative consequences arising from these. In this paper, we continue our study of pin classes , which are permutation classes that comprise all the finite subpermutations contained in an infinite pin permutation. We show that there is a phase transition at μ ≈ 3.28277 \mu\approx 3.28277 : there are uncountably many different pin classes whose growth rate is equal to μ \mu , yet only countably many below μ \mu . Furthermore, by showing that all pin classes with growth rate less than μ \mu are essentially defined by pin permutations that possess a periodic structure, we classify the set of growth rates of pin classes up to μ \mu . † † dmtcs-publicationdata: Volume vol. 27:1, Permutation Patterns 2024 (2026), #11, doi:10.46298/dmtcs.14896 1 Introduction This paper continues the study of pin classes started in Jarvis (2024) . Here, we investigate the spectrum of ‘small’ growth rates of such classes, up to growth rate \mu\approx 3.28277 . This work follows the line of enquiry undertaken by several papers – for example Huczynska and Vatter (2006) ; Kaiser and Klazar (2003) and Vatter (2010) ; Vatter (2011) ; Vatter (2019) – which explored the spectrum of growth rates in general permutation classes. Of special note are Pantone and Vatter (2020) who established a complete characterisation of the real numbers up to \xi\approx 2.30522 that are permutation class growth rates, and Bevan (2018) who showed that every real number greater than \lambda\approx 2.35526 is the growth rate of some permutation class. Many of the features of the spectrum of growth rates up to \xi and from \lambda are driven by a single underpinning object: the oscillations . These objects govern several phase transitions in the possible growth rates and number of distinct classes, most notably at \kappa\approx 2.20557 (the largest real root of z^{3}-2z^{2}-1 ) which represents the smallest growth rate for which there exist uncountably many distinct permutation classes – see Vatter (2011) . Oscillations are one type of pin permutation (for full definitions, see Section 2 ), which were originally introduced by Brignall, Huczynska, and Vatter (2008a) as a tool in a Ramsey-theoretic study of simple permutations. Since then, they have been studied from a number of viewpoints: Bassino, Bouvel, Pierrot, and Rossin (2015) describe an efficient decision procedure to determine whether a given permutation class contains arbitrarily long pin permutations, while Bassino, Bouvel, and Rossin (2011) showed that the permutation class formed of all pin permutations and their subpermutations has a rational generating function. More recently, Brignall and Vatter (2026) used pin permutations to construct uncountably many well-quasi-ordered permutation classes with distinct enumerations, thereby disproving a conjecture of Vatter (2015) . Finally, Chudnovsky, Kim, Oum, and Seymour (2016) use the term chain to describe an analogous object in the study of hereditary classes of graphs. Given an (infinite) pin permutation, the pin class is formed by taking all finite subpermutations that are contained in it. In the previous paper by Jarvis (2024) , it was shown (among other results) that pin classes always have growth rates. In this paper, we consider the pin classes with smallest growth rate, and establish a phase transition at growth rate \mu\approx 3.28277 , the largest real zero of z^{5}-4z^{4}+3z^{3}-2z^{2}-z+2 . Specifically: Theorem 5.2 There are uncountably many pin classes \mathcal{C} with growth rate equal to \mu . Theorem 6.3 Any pin class \mathcal{C} for which \mathrm{gr}(\mathcal{C})<\mu is defined by a pin permutation whose structure is ultimately periodic, and has growth rate equal either to \kappa or to \nu_{\ell} for some \ell\geq 1 , defined to be the largest real zero of z^{2\ell}-4z^{2\ell-1}+3z^{2\ell-2}-2z^{2\ell-3}-z^{2\ell-4}+2z^{2\ell-5}+1. It has been known for some time that \kappa is the least growth rate of a pin class (thanks to the appearance of infinite oscillations established by Vatter (2011) ). One interesting observation arising from our work is that the second least growth rate of a pin class is not reached until \nu=\nu_{1}\approx 3.06918 . Also of note is that, among the uncountable collection of pin classes identified that have growth rate \mu\approx 3.28277 , there exist classes whose defining pin sequence is not eventually recurrent (Proposition 5.3 ), even though all pin classes with smaller growth rates must be defined by a periodic or eventually periodic sequence. The rest of this paper is organised as follows. In Section 2 , we cover some basic definitions and results, including those concerning growth rates, the ‘box sum’ decomposition, pin sequences and pin permutations, and the combinatorics of words. Section 3 develops some theory for pin permutations and begins the process of restricting which pin permutations need to be considered when working below growth rate \mu . Sections 4 and 6 together fully classify the pin classes whose growth rate is less than \mu , while the intervening Section 5 exhibits various pin classes that occur at growth rate \mu . 2 Preliminaries We refer the reader to Bevan (2015) for background information and basic definitions concerning permutations and permutation classes. The following definition is derived from the study of permutation classes, but here note that we present it in fuller generality. Let (s_{n}) be a sequence of non-negative integers. The upper and lower growth rates are defined, respectively, to be \overline{\mathrm{gr}}((s_{n}))=\limsup_{n\to\infty}\sqrt[n]{s_{n}},\quad\text{ and }\quad\underline{\mathrm{gr}}((s_{n}))=\liminf_{n\to\infty}\sqrt[n]{s_{n}}, when these quantities exist. If \overline{\mathrm{gr}}((s_{n}))=\underline{\mathrm{gr}}((s_{n})) , then the sequence has an actual growth rate , typically denoted \mathrm{gr}((s_{n})) . We will frequently abuse this notation, for example if we are given some collection \mathcal{C} of combinatorial objects, then \overline{\mathrm{gr}}(\mathcal{C}) and \underline{\mathrm{gr}}(\mathcal{C}) are defined using the sequence (|\mathcal{C}_{n}|) that counts the number of objects in \mathcal{C} of each size n . If \mathcal{C} is a proper permutation class, for example, then this recovers the standard notions of growth rates for permutation classes. Similarly, if we are given a generating function f(z) , then we can also use the term \mathrm{gr}(f(z)) to refer to the growth rate of the sequence of coefficients in the Taylor expansion of f(z) , or, equivalently (by standard analytic combinatorics), the reciprocal of the radius of convergence of the formal power series f(z) . Recall that the plot of a permutation \pi is the points (i,\pi(i)) in the Euclidean plane. Consider a set \mathcal{L} of horizontal and vertical lines drawn in this plane – we refer to this as a gridded plane . For a permutation \pi and a collection \mathcal{L} of lines defining a gridded plane, the gridded permutation \pi^{\sharp} is the pair (\pi,\mathcal{L}) . Such an object is typically regarded as a division of the plot of \pi into a grid of rectangular cells. For enumerative purposes, the length of a gridded permutation is the same as its underlying ungridded version. However, two griddings \pi^{\sharp} and \pi^{\natural} of the same underlying permutation \pi are only regarded as equal if they have the same number of vertical and horizontal lines, and if each rectangular cell of one gridding contains exactly the same points of \pi as the corresponding rectangular cell of the other. Given a permutation class \mathcal{C} and