Growth rates of geometric grid classes of permutations
Bevan, David (2014) Growth rates of geometric grid classes of permutations. The Electronic Journal of Combinatorics, 21 (4). pp. 1-17. ISSN 1077-8926
Preview |
Text.
Filename: Bevan_EJC_2014_Growth_rates_of_geometric_grid_classes_of_permutations.pdf
Final Published Version Download (343kB)| Preview |
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.
ORCID iDs
Bevan, David ORCID: https://orcid.org/0000-0001-7179-2285;-
-
Item type: Article ID code: 58505 Dates: DateEvent4 December 2014Published22 November 2014AcceptedSubjects: Science > Mathematics Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 09 Nov 2016 11:54 Last modified: 26 Oct 2024 10:29 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/58505