Growth rates of geometric grid classes of permutations

MaRDI QIDQ490266zbMATHFDO

Authors David Bevan

Publication date 22 January 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.4246

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

permutationsmatching polynomialtrace monoidsgeometric grid classes

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph polynomials (05C31) Asymptotic enumeration (05A16)

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.

Recommendations

• Geometric grid classes of permutations
• Growth rates of permutation grid classes, tours on graphs, and the spectral radius
• Inflations of geometric grid classes of permutations
• Growth rates of permutation classes: from countable to uncountable
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188

Cites work

• scientific article; zbMATH DE number 428989 (Why is no real title available?)
• scientific article; zbMATH DE number 3679828 (Why is no real title available?)
• scientific article; zbMATH DE number 3512165 (Why is no real title available?)
• scientific article; zbMATH DE number 3583866 (Why is no real title available?)
• scientific article; zbMATH DE number 3222645 (Why is no real title available?)
• An introduction to matching polynomials
• An introduction to the theory of graph spectra
• Analytic combinatorics
• Clique polynomials have a unique root of smallest modulus
• Combinatorial problems of commutation and rearrangements
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Geometric grid classes of permutations
• Growth rates of permutation grid classes, tours on graphs, and the spectral radius
• Inflations of geometric grid classes of permutations
• Inflations of geometric grid classes: three case studies
• Matching theory
• Matchings and walks in graphs
• On growth rates of closed permutation classes
• On partial well-order for monotone grid classes of permutations
• On points drawn from a circle
• On the eigenvalues of trees
• On the theory of the matching polynomial
• Small permutation classes
• The X-class and almost-increasing permutations
• The characteristic polynomial of a graph
• The enumeration of permutations avoiding 3124 and 4312
• The enumeration of three pattern classes using monotone grid classes

Cited in

(14)

• Letter graphs and geometric grid classes of permutations
• Asymptotic growth rate of square grids dominating sets: a symbolic dynamics approach
• Growth rates of permutation grid classes, tours on graphs, and the spectral radius
• Rationality for subclasses of 321-avoiding permutations
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• An elementary proof of Bevan's theorem on the growth of grid classes of permutations
• Grid classes and the Fibonacci dichotomy for restricted permutations
• On the centrosymmetric permutations in a class
• Geometric grid classes of permutations
• Bounds on the lettericity of graphs
• scientific article; zbMATH DE number 7559423 (Why is no real title available?)
• Inflations of geometric grid classes of permutations
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Growth Rates and Critical Exponents of Classes of Binary Combinatorial Geometries

Describes a project that uses

Uses Software

• MathOverflow

This page was built for publication: Growth rates of geometric grid classes of permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490266)