Intervals of permutation class growth rates

Bevan, David (2018) Intervals of permutation class growth rates. Combinatorica, 38 (2). pp. 279-303. ISSN 1439-6912 (https://doi.org/10.1007/s00493-016-3349-2)

[thumbnail of Bevan-Combinatorica-2016-Intervals-of-permutations-class-growth]
Preview
 Text. Filename: Bevan_Combinatorica_2016_Intervals_of_permutations_class_growth.pdf
Accepted Author Manuscript
Download (388kB)| Preview

Abstract

We prove that the set of growth rates of permutation classes includes an infinite sequence of intervals whose infimum is θB ≈ 2.35526, and that it also contains every value at least λB ≈ 2.35698. These results improve on a theorem of Vatter, who determined that there are permutation classes of every growth rate at least λA ≈ 2.48187. Thus, we also refute his conjecture that the set of growth rates below λ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ényi 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.

ORCID iDs

Bevan, David ORCID logoORCID: https://orcid.org/0000-0001-7179-2285;
  • Item type:Article
    ID code:57976
    Dates:
    Date
    Event
    30 April 2018
    Published
    1 March 2017
    Published Online
    4 September 2015
    Accepted
    Keywords:permutation classes, growth rates, expansions in noninteger bases, Mathematics, Discrete Mathematics and Combinatorics
    Subjects:Science > Mathematics
    Department:Faculty of Science > Computer and Information Sciences
    Depositing user: Pure Administrator
    Date deposited:28 Sep 2016 14:54
    Last modified:01 Nov 2023 10:44
    URI:https://strathprints.strath.ac.uk/id/eprint/57976
CORE (COnnecting REpositories)