Intervals of permutation class growth rates

DOI10.1007/S00493-016-3349-2zbMATH Open1413.05001arXiv1410.3679OpenAlexW2155931503MaRDI QIDQ722339FDOQ722339

Authors: David Bevan 

Publication date: 23 July 2018

Published in: Combinatorica (Search for Journal in Brave)

Abstract: We prove that the set of growth rates of permutation classes includes an infinite sequence of intervals whose infimum is $het{a}_{B}approx2.35526$, and that it also contains every value at least $lambd{a}_{B}approx2.35698$. These results improve on a theorem of Vatter, who determined that there are permutation classes of every growth rate at least $lambd{a}_{A}approx2.48187$. Thus, we also refute his conjecture that the set of growth rates below $lambd{a}_A$ is nowhere dense. Our proof is based upon an analysis of expansions of real numbers in non-integer bases, the study of which was initiated by R'enyi in the 1950s. In particular, we prove two generalisations of a result of Pedicini concerning expansions in which the digits are drawn from sets of allowed values.

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

Recommendations

• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• Growth rates of permutation classes: from countable to uncountable
• Growth rates of permutation classes: categorization up to the uncountability threshold
• Small permutation classes
• Permutation classes of polynomial growth

zbMATH Keywords

permutationgrowth ratepattern

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Asymptotic enumeration (05A16)

Cites Work

• Representations for real numbers and their ergodic properties
• Greedy expansions and sets with deleted digits
• Expansions in noninteger bases
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Overview of some general results in combinatorial enumeration
• On growth rates of closed permutation classes
• Grid classes and the Fibonacci dichotomy for restricted permutations
• Inflations of geometric grid classes of permutations
• Small permutation classes
• Growth rates of permutation grid classes, tours on graphs, and the spectral radius
• 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

Cited In (8)

• Growth rates of permutation classes: from countable to uncountable
• An elementary proof of Bevan's theorem on the growth of grid classes of permutations
• Combinatorial specifications for juxtapositions of permutation classes
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• Growth rates of permutation classes: categorization up to the uncountability threshold
• On the growth of merges and staircases of permutation classes
• Two examples of Wilf-collapse
• Growing at a perfect speed

Uses Software

• Mathematica

This page was built for publication: Intervals of permutation class growth rates

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