Growth rates of permutation classes: categorization up to the uncountability threshold

DOI10.1007/S11856-020-1964-5zbMATH Open1439.05009OpenAlexW3000602215WikidataQ126334778 ScholiaQ126334778MaRDI QIDQ2182018FDOQ2182018

Authors Jay Pantone, Vincent Vatter

Publication date 20 May 2020

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.04289

zbMATH Keywords

growthrateconcentraciongeneralized grid classes

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: In the antecedent paper to this it was established that there is an algebraic number $xiapprox2.30522$ such that while there are uncountably many growth rates of permutation classes arbitrarily close to $xi$, there are only countably many less than $xi$. Here we provide a complete characterization of the growth rates less than $xi$. In particular, this classification establishes that $xi$ is the least accumulation point from above of growth rates and that all growth rates less than or equal to $xi$ 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 $xi$ is an accumulation point from above of growth rates of finitely based permutation classes.

Recommendations

• Growth rates of permutation classes: from countable to uncountable
• Small permutation classes
• Permutation classes of polynomial growth
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• Intervals of permutation class growth rates

Cites work

• scientific article; zbMATH DE number 3258862 (Why is no real title available?)
• Analytic combinatorics
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Finding regular insertion encodings for permutation classes
• Growing at a perfect speed
• Growth rates of permutation classes: from countable to uncountable
• Hereditary properties of ordered graphs
• Inflations of geometric grid classes of permutations
• Intervals of permutation class growth rates
• Linear Automaton Transformations
• On growth rates of closed permutation classes
• On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
• On the least exponential growth admitting uncountably many closed permutation classes
• Overview of some general results in combinatorial enumeration
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• Permutation classes
• Permutation reconstruction
• Permutation reconstruction from minors
• Representations for real numbers and their ergodic properties
• Small permutation classes
• The insertion encoding of permutations

Cited in

(7)

• Growth rates of permutation classes: from countable to uncountable
• Growing at a perfect speed
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• Intervals of permutation class growth rates
• Inflations of geometric grid classes of permutations
• A jump to the Narayana number for hereditary properties of ordered 3-uniform hypergraphs
• Two examples of Wilf-collapse

Describes a project that uses

Uses Software

• InsEnc

This page was built for publication: Growth rates of permutation classes: categorization up to the uncountability threshold

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2182018)