Picture of person typing on laptop with programming code visible on the laptop screen

World class computing and information science research at Strathclyde...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by University of Strathclyde researchers, including by researchers from the Department of Computer & Information Sciences involved in mathematically structured programming, similarity and metric search, computer security, software systems, combinatronics and digital health.

The Department also includes the iSchool Research Group, which performs leading research into socio-technical phenomena and topics such as information retrieval and information seeking behaviour.

Explore

Intervals of permutation class growth rates

Bevan, David (2016) Intervals of permutation class growth rates. Combinatorica. ISSN 1439-6912 (In Press)

[img]
Preview
Text (Bevan-Combinatorica-2016-Intervals-of-permutations-class-growth)
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.