Growth rates of permutation classes: from countable to uncountable

DOI10.1112/PLMS.12250MaRDI QIDQ4973647zbMATH OpenOpenAlexWikidataFDO

Authors Vincent Vatter

Publication date 28 November 2019

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

concentraciongeneralized grid classes

Mathematics Subject Classification ID

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

Abstract: We establish 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$. Central to the proof are various structural notions regarding generalized grid classes and a new property of permutation classes called concentration. The classification of growth rates up to $xi$ is completed in a subsequent paper.

Recommendations

• Growth rates of permutation classes: categorization up to the uncountability threshold
• Small permutation classes
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• Inflations of geometric grid classes of permutations
• Intervals of permutation class growth rates

Cited in

(21)

• On growth rates of permutations, set partitions, ordered graphs and other objects
• On growth rates of closed permutation classes
• On the growth of merges and staircases of permutation classes
• Deciding atomicity of subword-closed languages
• Growth rates of permutation classes: categorization up to the uncountability threshold
• Inflations of geometric grid classes of permutations
• Grid classes and the Fibonacci dichotomy for restricted permutations
• Large infinite antichains of permutations
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• Growing at a perfect speed
• Growth rates of geometric grid classes of permutations
• Labelled well-quasi-order for permutation classes
• scientific article; zbMATH DE number 7559423 (Why is no real title available?)
• On the centrosymmetric permutations in a class
• An elementary proof of Bevan's theorem on the growth of grid classes of permutations
• Growth rates of permutation grid classes, tours on graphs, and the spectral radius
• A jump to the Narayana number for hereditary properties of ordered 3-uniform hypergraphs
• Deciding atomicity of subword-closed languages
• Generalized coloring of permutations
• Intervals of permutation class growth rates
• Pin classes. II: Small pin classes

This page was built for publication: Growth rates of permutation classes: from countable to uncountable

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