Growth Rates of Permutation Classes: Categorization Up to the Uncountability Threshold

Authors

Jay Pantone, Marquette UniversityFollow
Vincent Vatter, University of Florida

Document Type

Article

Publication Date

2020

Publisher

Springer

Source Publication

Israel Journal of Mathematics

Source ISSN

0021-2172

Original Item ID

DOI: 10.1007/s11856-020-1964-5

Abstract

In the antecedent paper to this it was established that there is an algebraic number ξ ≈ 2.30522 such that while there are uncountably many growth rates of permutation classes arbitrarily close to ξ, there are only countably many less than ξ. Here we provide a complete characterization of the growth rates less than ξ. In particular, this classification establishes that ξ is the least accumulation point from above of growth rates and that all growth rates less than or equal to ξ are achieved by finitely based classes. A significant part of this classification is achieved via a reconstruction result for sum indecomposable permutations. We conclude by refuting a suggestion of Klazar, showing that ξ is an accumulation point from above of growth rates of finitely based permutation classes.

Comments

Israel Journal of Mathematics, Vol. 236 (2020): 1-43. DOI.

Recommended Citation

Pantone, Jay and Vatter, Vincent, "Growth Rates of Permutation Classes: Categorization Up to the Uncountability Threshold" (2020). Mathematical and Statistical Science Faculty Research and Publications. 127.
https://epublications.marquette.edu/math_fac/127