Growth rates of permutation grid classes, tours on graphs, and the spectral radius

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

Monotone grid classes of permutations have proven very effective in helping to determine structural and enumerative properties of classical permutation pattern classes. Associated with grid class Grid(M) is a graph, G(M), known as its "row-column" graph. We prove that the exponential growth rate of Grid(M) is equal to the square of the spectral radius of G(M). Consequently, we utilize spectral graph theoretic results to characterise all slowly growing grid classes and to show that for every γ ≥ 2 + √5 there is a grid class with growth rate arbitrarily close to γ. To prove our main result, we establish bounds on the size of certain families of tours on graphs. In the process, we prove that the family of tours of even length on a connected graph grows at the same rate as the family of "balanced" tours on the graph (in which the number of times an edge is traversed in one direction is the same as the number of times it is traversed in the other direction).
LanguageEnglish
Pages5863–5889
Number of pages27
JournalTransactions of the American Mathematical Society
Volume367
Issue number8
Early online date15 Jan 2015
DOIs
Publication statusPublished - 31 Aug 2015

Fingerprint

Spectral Radius
Permutation
Grid
Graph in graph theory
Column graph
Exponential Growth
Class
Connected graph
Monotone
Family

Keywords

  • permutations
  • permutation grid classes
  • tours on graphs
  • spectral radius
  • growth rates

Cite this

@article{2d6da1f76fca4c86aa1fbd7dc4b4261b,
title = "Growth rates of permutation grid classes, tours on graphs, and the spectral radius",
abstract = "Monotone grid classes of permutations have proven very effective in helping to determine structural and enumerative properties of classical permutation pattern classes. Associated with grid class Grid(M) is a graph, G(M), known as its {"}row-column{"} graph. We prove that the exponential growth rate of Grid(M) is equal to the square of the spectral radius of G(M). Consequently, we utilize spectral graph theoretic results to characterise all slowly growing grid classes and to show that for every γ ≥ 2 + √5 there is a grid class with growth rate arbitrarily close to γ. To prove our main result, we establish bounds on the size of certain families of tours on graphs. In the process, we prove that the family of tours of even length on a connected graph grows at the same rate as the family of {"}balanced{"} tours on the graph (in which the number of times an edge is traversed in one direction is the same as the number of times it is traversed in the other direction).",
keywords = "permutations, permutation grid classes, tours on graphs, spectral radius, growth rates",
author = "David Bevan",
year = "2015",
month = "8",
day = "31",
doi = "10.1090/S0002-9947-2015-06280-1",
language = "English",
volume = "367",
pages = "5863–5889",
journal = "Transactions of the American Mathematical Society",
issn = "0002-9947",
number = "8",

}

Growth rates of permutation grid classes, tours on graphs, and the spectral radius. / Bevan, David.

In: Transactions of the American Mathematical Society, Vol. 367, No. 8, 31.08.2015, p. 5863–5889.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Growth rates of permutation grid classes, tours on graphs, and the spectral radius

AU - Bevan, David

PY - 2015/8/31

Y1 - 2015/8/31

N2 - Monotone grid classes of permutations have proven very effective in helping to determine structural and enumerative properties of classical permutation pattern classes. Associated with grid class Grid(M) is a graph, G(M), known as its "row-column" graph. We prove that the exponential growth rate of Grid(M) is equal to the square of the spectral radius of G(M). Consequently, we utilize spectral graph theoretic results to characterise all slowly growing grid classes and to show that for every γ ≥ 2 + √5 there is a grid class with growth rate arbitrarily close to γ. To prove our main result, we establish bounds on the size of certain families of tours on graphs. In the process, we prove that the family of tours of even length on a connected graph grows at the same rate as the family of "balanced" tours on the graph (in which the number of times an edge is traversed in one direction is the same as the number of times it is traversed in the other direction).

AB - Monotone grid classes of permutations have proven very effective in helping to determine structural and enumerative properties of classical permutation pattern classes. Associated with grid class Grid(M) is a graph, G(M), known as its "row-column" graph. We prove that the exponential growth rate of Grid(M) is equal to the square of the spectral radius of G(M). Consequently, we utilize spectral graph theoretic results to characterise all slowly growing grid classes and to show that for every γ ≥ 2 + √5 there is a grid class with growth rate arbitrarily close to γ. To prove our main result, we establish bounds on the size of certain families of tours on graphs. In the process, we prove that the family of tours of even length on a connected graph grows at the same rate as the family of "balanced" tours on the graph (in which the number of times an edge is traversed in one direction is the same as the number of times it is traversed in the other direction).

KW - permutations

KW - permutation grid classes

KW - tours on graphs

KW - spectral radius

KW - growth rates

U2 - 10.1090/S0002-9947-2015-06280-1

DO - 10.1090/S0002-9947-2015-06280-1

M3 - Article

VL - 367

SP - 5863

EP - 5889

JO - Transactions of the American Mathematical Society

T2 - Transactions of the American Mathematical Society

JF - Transactions of the American Mathematical Society

SN - 0002-9947

IS - 8

ER -