Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

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



Growth rates of permutation grid classes, tours on graphs, and the spectral radius

Author: David Bevan
Journal: Trans. Amer. Math. Soc. 367 (2015), 5863-5889
MSC (2010): Primary 05A05, 05A16, 05C50
Published electronically: January 15, 2015
MathSciNet review: 3347191
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 $ \textup {Grid}(M)$ is a graph, $ G(M)$, known as its ``row-column'' graph. We prove that the exponential growth rate of $ \textup {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 [Enhancements On Off] (What's this?)

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

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
Article copyright: © Copyright 2015 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society