Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Growth rates of permutation grid classes, tours on graphs, and the spectral radius
HTML articles powered by AMS MathViewer

by David Bevan PDF
Trans. Amer. Math. Soc. 367 (2015), 5863-5889 Request permission

Abstract:

Monotone grid classes of permutations have proven very effective in helping to determine structural and enumerative properties of classical permutation pattern classes. Associated with grid class $\mathrm {Grid}(M)$ is a graph, $G(M)$, known as its “row-column” graph. We prove that the exponential growth rate of $\mathrm {Grid}(M)$ is equal to the square of the spectral radius of $G(M)$. Consequently, we utilize spectral graph theoretic results to characterise all slowly growing grid classes and to show that for every $\gamma \geqslant 2+\sqrt {5}$ there is a grid class with growth rate arbitrarily close to $\gamma$. To prove our main result, we establish bounds on the size of certain families of tours on graphs. In the process, we prove that the family of tours of even length on a connected graph grows at the same rate as the family of “balanced” tours on the graph (in which the number of times an edge is traversed in one direction is the same as the number of times it is traversed in the other direction).
References
Similar Articles
  • Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05A05, 05A16, 05C50
  • Retrieve articles in all journals with MSC (2010): 05A05, 05A16, 05C50
Additional Information
  • David Bevan
  • Affiliation: Department of Mathematics and Statistics, The Open University, Milton Keynes MK7 6AA, England
  • Email: David.Bevan@open.ac.uk
  • Received by editor(s): February 12, 2013
  • Received by editor(s) in revised form: September 5, 2013, and September 17, 2013
  • Published electronically: January 15, 2015
  • © Copyright 2015 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Trans. Amer. Math. Soc. 367 (2015), 5863-5889
  • MSC (2010): Primary 05A05, 05A16, 05C50
  • DOI: https://doi.org/10.1090/S0002-9947-2015-06280-1
  • MathSciNet review: 3347191