Growth rates of geometric grid classes of permutations

zbMATH Open1305.05002arXiv1306.4246MaRDI QIDQ490266FDOQ490266

David Bevan

Publication date: 22 January 2015

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

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.

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

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

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

zbMATH Keywords

permutationsmatching polynomialtrace monoidsgeometric grid classes

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• Geometric grid classes of permutations
• Title not available (Why is that?)
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• On the centrosymmetric permutations in a class
• Growth rates of permutation grid classes, tours on graphs, and the spectral radius
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Bounds on the lettericity of graphs
• Growth Rates and Critical Exponents of Classes of Binary Combinatorial Geometries
• Asymptotic growth rate of square grids dominating sets: a symbolic dynamics approach
• Rationality for subclasses of 321-avoiding permutations
• Grid classes and the Fibonacci dichotomy for restricted permutations

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)