Abstract
| Original language | English |
|---|---|
| Pages (from-to) | 5863–5889 |
| Number of pages | 27 |
| Journal | Transactions of the American Mathematical Society |
| Volume | 367 |
| Issue number | 8 |
| Early online date | 15 Jan 2015 |
| DOIs | |
| Publication status | Published - 31 Aug 2015 |
Fingerprint
Keywords
- permutations
- permutation grid classes
- tours on graphs
- spectral radius
- growth rates
Cite this
}
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 journal › Article
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
JF - Transactions of the American Mathematical Society
SN - 0002-9947
IS - 8
ER -