Growth rates of geometric grid classes of permutations

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

Geometric grid classes of permutations have proven to be key in investigations of classical permutation pattern classes. By considering the representation of gridded permutations as words in a trace monoid, we prove that every geometric grid class has a growth rate which is given by the square of the largest root of the matching polynomial of a related graph. As a consequence, we characterise the set of growth rates of geometric grid classes in terms of the spectral radii of trees, explore the influence of "cycle parity" on the growth rate, compare the growth rates of geometric grid classes against those of the corresponding monotone grid classes, and present new results concerning the effect of edge subdivision on the largest root of the matching polynomial.
LanguageEnglish
Pages1-17
Number of pages17
JournalThe Electronic Journal of Combinatorics
Volume21
Issue number4
Publication statusPublished - 4 Dec 2014

Fingerprint

Permutation
Grid
Matching Polynomial
Polynomials
Roots
Spectral Radius
Monoid
Subdivision
Parity
Class
Monotone
Trace
Cycle
Graph in graph theory

Keywords

  • permutations
  • permutation grid classes
  • matching polynomial
  • growth rates

Cite this

@article{db69f0bc97ec46189159fe62cc0a4bae,
title = "Growth rates of geometric grid classes of permutations",
abstract = "Geometric grid classes of permutations have proven to be key in investigations of classical permutation pattern classes. By considering the representation of gridded permutations as words in a trace monoid, we prove that every geometric grid class has a growth rate which is given by the square of the largest root of the matching polynomial of a related graph. As a consequence, we characterise the set of growth rates of geometric grid classes in terms of the spectral radii of trees, explore the influence of {"}cycle parity{"} on the growth rate, compare the growth rates of geometric grid classes against those of the corresponding monotone grid classes, and present new results concerning the effect of edge subdivision on the largest root of the matching polynomial.",
keywords = "permutations, permutation grid classes, matching polynomial, growth rates",
author = "David Bevan",
year = "2014",
month = "12",
day = "4",
language = "English",
volume = "21",
pages = "1--17",
journal = "The Electronic Journal of Combinatorics",
issn = "1077-8926",
number = "4",

}

Growth rates of geometric grid classes of permutations. / Bevan, David.

In: The Electronic Journal of Combinatorics, Vol. 21, No. 4, 04.12.2014, p. 1-17.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Growth rates of geometric grid classes of permutations

AU - Bevan, David

PY - 2014/12/4

Y1 - 2014/12/4

N2 - Geometric grid classes of permutations have proven to be key in investigations of classical permutation pattern classes. By considering the representation of gridded permutations as words in a trace monoid, we prove that every geometric grid class has a growth rate which is given by the square of the largest root of the matching polynomial of a related graph. As a consequence, we characterise the set of growth rates of geometric grid classes in terms of the spectral radii of trees, explore the influence of "cycle parity" on the growth rate, compare the growth rates of geometric grid classes against those of the corresponding monotone grid classes, and present new results concerning the effect of edge subdivision on the largest root of the matching polynomial.

AB - Geometric grid classes of permutations have proven to be key in investigations of classical permutation pattern classes. By considering the representation of gridded permutations as words in a trace monoid, we prove that every geometric grid class has a growth rate which is given by the square of the largest root of the matching polynomial of a related graph. As a consequence, we characterise the set of growth rates of geometric grid classes in terms of the spectral radii of trees, explore the influence of "cycle parity" on the growth rate, compare the growth rates of geometric grid classes against those of the corresponding monotone grid classes, and present new results concerning the effect of edge subdivision on the largest root of the matching polynomial.

KW - permutations

KW - permutation grid classes

KW - matching polynomial

KW - growth rates

UR - http://www.combinatorics.org/

M3 - Article

VL - 21

SP - 1

EP - 17

JO - The Electronic Journal of Combinatorics

T2 - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

SN - 1077-8926

IS - 4

ER -