Geodesic
Growth rates of geometric grid classes of permutations
David Bevan1
1The Open University
The electronic journal of combinatorics, Tome 21 (2014) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/4834
Classification : 05A05, 05A16, 05C31
Mots-clés : permutations, geometric grid classes, matching polynomial, trace monoids

David Bevan  1

1 The Open University 
@article{10_37236_4834,
     author = {David Bevan},
     title = {Growth rates of geometric grid classes of permutations},
     journal = {The electronic journal of combinatorics},
     year = {2014},
     volume = {21},
     number = {4},
     doi = {10.37236/4834},
     zbl = {1305.05002},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4834/}
}
TY  - JOUR
AU  - David Bevan
TI  - Growth rates of geometric grid classes of permutations
JO  - The electronic journal of combinatorics
PY  - 2014
VL  - 21
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4834/
DO  - 10.37236/4834
ID  - 10_37236_4834
ER  - 
%0 Journal Article
%A David Bevan
%T Growth rates of geometric grid classes of permutations
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/4834/
%R 10.37236/4834
%F 10_37236_4834
David Bevan. Growth rates of geometric grid classes of permutations. The electronic journal of combinatorics, Tome 21 (2014) no. 4. doi: 10.37236/4834

Cité par Sources :