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

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

Authors: Jay Pantone, Vincent Vatter 

Publication date: 20 May 2020

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

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.

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

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

zbMATH Keywords

growthrateconcentraciongeneralized grid classes

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

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

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)