On the growth of permutation classes

Research output: ThesisDoctoral Thesis

Abstract

We study aspects of the enumeration of permutation classes, sets of permutations closed downwards under the subpermutation order.

First, we consider monotone grid classes of permutations. We present procedures for calculating the generating function of any class whose matrix has dimensions m × 1 for some m, and of acyclic and unicyclic classes of gridded permutations. We show that almost all large permutations in a grid class have the same shape, and determine this limit shape.

We prove that the growth rate of a grid class is given by the square of the spectral radius of an associated graph and deduce some facts relating to the set of grid class growth rates. In the process, we establish a new result concerning tours on graphs. We also prove a similar result relating the growth rate of a geometric grid class to the matching polynomial of a graph, and determine the effect of edge subdivision on the matching polynomial. We characterise the growth rates of geometric grid classes in terms of the spectral radii of trees.

We then investigate the set of growth rates of permutation classes and establish a new upper bound on the value above which every real number is the growth rate of some permutation class. In the process, we prove new results concerning expansions of real numbers in non-integer bases in which the digits are drawn from sets of allowed values.

Finally, we introduce a new enumeration technique, based on associating a graph with each permutation, and determine the generating functions for some previously unenumerated classes. We conclude by using this approach to provide an improved lower bound on the growth rate of the class of permutations avoiding the pattern 1324. In the process, we prove that, asymptotically, patterns in Łukasiewicz paths exhibit a concentrated Gaussian distribution.
LanguageEnglish
QualificationPhD
Awarding Institution
  • Open University
Supervisors/Advisors
  • Brignall, Robert, Supervisor, External person
Award date1 Jun 2015
Place of PublicationMilton Keynes
Publication statusPublished - 1 Jun 2015

Fingerprint

Permutation
Grid
Matching Polynomial
Spectral Radius
Graph in graph theory
Class
Enumeration
Generating Function
Subdivision
Digit
Gaussian distribution
Deduce
Monotone
Lower bound
Upper bound
Closed
Path

Keywords

  • permutation classes
  • growth rates
  • permutation grid classes

Cite this

@phdthesis{59c60b5b01ac47f08bbb13ac1b87b4bb,
title = "On the growth of permutation classes",
abstract = "We study aspects of the enumeration of permutation classes, sets of permutations closed downwards under the subpermutation order.First, we consider monotone grid classes of permutations. We present procedures for calculating the generating function of any class whose matrix has dimensions m × 1 for some m, and of acyclic and unicyclic classes of gridded permutations. We show that almost all large permutations in a grid class have the same shape, and determine this limit shape.We prove that the growth rate of a grid class is given by the square of the spectral radius of an associated graph and deduce some facts relating to the set of grid class growth rates. In the process, we establish a new result concerning tours on graphs. We also prove a similar result relating the growth rate of a geometric grid class to the matching polynomial of a graph, and determine the effect of edge subdivision on the matching polynomial. We characterise the growth rates of geometric grid classes in terms of the spectral radii of trees.We then investigate the set of growth rates of permutation classes and establish a new upper bound on the value above which every real number is the growth rate of some permutation class. In the process, we prove new results concerning expansions of real numbers in non-integer bases in which the digits are drawn from sets of allowed values.Finally, we introduce a new enumeration technique, based on associating a graph with each permutation, and determine the generating functions for some previously unenumerated classes. We conclude by using this approach to provide an improved lower bound on the growth rate of the class of permutations avoiding the pattern 1324. In the process, we prove that, asymptotically, patterns in Łukasiewicz paths exhibit a concentrated Gaussian distribution.",
keywords = "permutation classes, growth rates, permutation grid classes",
author = "David Bevan",
year = "2015",
month = "6",
day = "1",
language = "English",
school = "Open University",

}

Bevan, D 2015, 'On the growth of permutation classes', PhD, Open University, Milton Keynes.

On the growth of permutation classes. / Bevan, David.

Milton Keynes, 2015.

Research output: ThesisDoctoral Thesis

TY - THES

T1 - On the growth of permutation classes

AU - Bevan, David

PY - 2015/6/1

Y1 - 2015/6/1

N2 - We study aspects of the enumeration of permutation classes, sets of permutations closed downwards under the subpermutation order.First, we consider monotone grid classes of permutations. We present procedures for calculating the generating function of any class whose matrix has dimensions m × 1 for some m, and of acyclic and unicyclic classes of gridded permutations. We show that almost all large permutations in a grid class have the same shape, and determine this limit shape.We prove that the growth rate of a grid class is given by the square of the spectral radius of an associated graph and deduce some facts relating to the set of grid class growth rates. In the process, we establish a new result concerning tours on graphs. We also prove a similar result relating the growth rate of a geometric grid class to the matching polynomial of a graph, and determine the effect of edge subdivision on the matching polynomial. We characterise the growth rates of geometric grid classes in terms of the spectral radii of trees.We then investigate the set of growth rates of permutation classes and establish a new upper bound on the value above which every real number is the growth rate of some permutation class. In the process, we prove new results concerning expansions of real numbers in non-integer bases in which the digits are drawn from sets of allowed values.Finally, we introduce a new enumeration technique, based on associating a graph with each permutation, and determine the generating functions for some previously unenumerated classes. We conclude by using this approach to provide an improved lower bound on the growth rate of the class of permutations avoiding the pattern 1324. In the process, we prove that, asymptotically, patterns in Łukasiewicz paths exhibit a concentrated Gaussian distribution.

AB - We study aspects of the enumeration of permutation classes, sets of permutations closed downwards under the subpermutation order.First, we consider monotone grid classes of permutations. We present procedures for calculating the generating function of any class whose matrix has dimensions m × 1 for some m, and of acyclic and unicyclic classes of gridded permutations. We show that almost all large permutations in a grid class have the same shape, and determine this limit shape.We prove that the growth rate of a grid class is given by the square of the spectral radius of an associated graph and deduce some facts relating to the set of grid class growth rates. In the process, we establish a new result concerning tours on graphs. We also prove a similar result relating the growth rate of a geometric grid class to the matching polynomial of a graph, and determine the effect of edge subdivision on the matching polynomial. We characterise the growth rates of geometric grid classes in terms of the spectral radii of trees.We then investigate the set of growth rates of permutation classes and establish a new upper bound on the value above which every real number is the growth rate of some permutation class. In the process, we prove new results concerning expansions of real numbers in non-integer bases in which the digits are drawn from sets of allowed values.Finally, we introduce a new enumeration technique, based on associating a graph with each permutation, and determine the generating functions for some previously unenumerated classes. We conclude by using this approach to provide an improved lower bound on the growth rate of the class of permutations avoiding the pattern 1324. In the process, we prove that, asymptotically, patterns in Łukasiewicz paths exhibit a concentrated Gaussian distribution.

KW - permutation classes

KW - growth rates

KW - permutation grid classes

UR - https://arxiv.org/pdf/1506.06688

M3 - Doctoral Thesis

CY - Milton Keynes

ER -