Picture of athlete cycling

Open Access research with a real impact on health...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the Physical Activity for Health Group based within the School of Psychological Sciences & Health. Research here seeks to better understand how and why physical activity improves health, gain a better understanding of the amount, intensity, and type of physical activity needed for health benefits, and evaluate the effect of interventions to promote physical activity.

Explore open research content by Physical Activity for Health...

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

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


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.