Intervals of permutation class growth rates

David Bevan

Research output: Contribution to journal › Article

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.
LanguageEnglish
Pages279-303
Number of pages25
JournalCombinatorica
Volume38
Issue number2
Early online date1 Mar 2017
DOIs
StatePublished - 30 Apr 2018

Fingerprint

Permutation
Interval
Digit
Theorem
Class
Generalization

Keywords

  • permutation classes
  • growth rates
  • expansions in noninteger bases

Cite this

Bevan, David. / Intervals of permutation class growth rates. In: Combinatorica. 2018 ; Vol. 38, No. 2. pp. 279-303
@article{903614db69e942869f45dac32182e069,
title = "Intervals of permutation class growth rates",
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{\'e}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.",
keywords = "permutation classes, growth rates, expansions in noninteger bases",
author = "David Bevan",
year = "2018",
month = "4",
day = "30",
doi = "10.1007/s00493-016-3349-2",
language = "English",
volume = "38",
pages = "279--303",
journal = "Combinatorica",
issn = "0209-9683",
publisher = "Springer",
number = "2",

}

Bevan, D 2018, 'Intervals of permutation class growth rates' Combinatorica, vol. 38, no. 2, pp. 279-303. DOI: 10.1007/s00493-016-3349-2

Intervals of permutation class growth rates. / Bevan, David.

In: Combinatorica, Vol. 38, No. 2, 30.04.2018, p. 279-303.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Intervals of permutation class growth rates

AU - Bevan,David

PY - 2018/4/30

Y1 - 2018/4/30

N2 - 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.

AB - 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.

KW - permutation classes

KW - growth rates

KW - expansions in noninteger bases

U2 - 10.1007/s00493-016-3349-2

DO - 10.1007/s00493-016-3349-2

M3 - Article

VL - 38

SP - 279

EP - 303

JO - Combinatorica

T2 - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 2

ER -

Bevan D. Intervals of permutation class growth rates. Combinatorica. 2018 Apr 30;38(2):279-303. Available from, DOI: 10.1007/s00493-016-3349-2

Access to Document

    Related content

    Research Output

    On the growth of permutation classes

    Research output: Thesis › Doctoral Thesis

    Datasets

    Calculating intervals of permutation class growth rates

    Dataset