Picture of neon light reading 'Open'

Discover open research at Strathprints as part of International Open Access Week!

23-29 October 2017 is International Open Access Week. The Strathprints institutional repository is a digital archive of Open Access research outputs, all produced by University of Strathclyde researchers.

Explore recent world leading Open Access research content this Open Access Week from across Strathclyde's many research active faculties: Engineering, Science, Humanities, Arts & Social Sciences and Strathclyde Business School.

Explore all Strathclyde Open Access research outputs...

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

[img]
Preview
Text (Bevan-EJC-2014-Growth-rates-of-geometric-grid-classes-of-permutations)
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.