Abstract
Language | English |
---|---|
Pages | 279-303 |
Number of pages | 25 |
Journal | Combinatorica |
Volume | 38 |
Issue number | 2 |
Early online date | 1 Mar 2017 |
DOIs | |
Publication status | Published - 30 Apr 2018 |
Fingerprint
Keywords
- permutation classes
- growth rates
- expansions in noninteger bases
Cite this
}
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 -