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)

Request Permissions   Purchase Content 
 
 

 

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
DOI: https://doi.org/10.1090/S0002-9947-2015-06280-1
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?)

  • [1] M. H. Albert, M. D. Atkinson, and Robert Brignall, The enumeration of permutations avoiding $ 2143$ and $ 4231$, Pure Math. Appl. (PU.M.A.) 22 (2011), no. 2, 87-98. MR 2924740
  • [2] M. H. Albert, M. D. Atkinson, and Robert Brignall, The enumeration of three pattern classes using monotone grid classes, Electron. J. Combin. 19 (2012), no. 3, Paper 20, 34. MR 2967225
  • [3] Michael Albert, Mike Atkinson, and Robert Brignall, Notes on the basis of monotone grid classes, Unpublished, 2010.
  • [4] Michael H. Albert, M. D. Atkinson, Mathilde Bouvel, Nik Ruškuc, and Vincent Vatter, Geometric grid classes of permutations, Trans. Amer. Math. Soc. 365 (2013), no. 11, 5859-5881. MR 3091268, https://doi.org/10.1090/S0002-9947-2013-05804-7
  • [5] Michael H. Albert, M. D. Atkinson, and Vincent Vatter, Inflations of geometric grid classes: three case studies, Australas. J. Combin. 58 (2014), 24-47. MR 3211768
  • [6] M. D. Atkinson, Permutations which are the union of an increasing and a decreasing subsequence, Electron. J. Combin. 5 (1998), Research paper 6, 13 pp.. MR 1490467 (98k:05001)
  • [7] M. D. Atkinson, Restricted permutations, Discrete Math. 195 (1999), no. 1-3, 27-38. MR 1663866 (99i:05004), https://doi.org/10.1016/S0012-365X(98)00162-9
  • [8] David Bevan, Permutation grid classes,
    http://demonstrations.wolfram.com/PermutationGridClasses, Wolfram Demonstrations Project, 2012.
  • [9] David Bevan, Growth rates of geometric grid classes of permutations, Electron. J. Combin. 21 (2014), no. 4, Paper 4.51, 17 pp.
  • [10] A. E. Brouwer and A. Neumaier, The graphs with spectral radius between $ 2$ and $ \sqrt {2+\sqrt {5}}$, Linear Algebra Appl. 114/115 (1989), 273-276. MR 986880 (90f:05094), https://doi.org/10.1016/0024-3795(89)90466-7
  • [11] Andries E. Brouwer and Willem H. Haemers, Spectra of graphs, Universitext, Springer, New York, 2012. MR 2882891
  • [12] Dragoš Cvetković, Michael Doob, and Ivan Gutman, On graphs whose spectral radius does not exceed $ (2+\sqrt {5})^{1/2}$, Ars Combin. 14 (1982), 225-239. MR 683990 (84i:05076)
  • [13] Dragoš Cvetković, Peter Rowlinson, and Slobodan Simić, An introduction to the theory of graph spectra, London Mathematical Society Student Texts, vol. 75, Cambridge University Press, Cambridge, 2010. MR 2571608 (2011g:05004)
  • [14] Jiří Fiala and Jan Kratochvíl, Locally constrained graph homomorphisms--structure, complexity, and applications, Computer Science Review 2 (2008), no. 2, 97-111.
  • [15] Pavol Hell and Jaroslav Nešetřil, Graphs and homomorphisms, Oxford Lecture Series in Mathematics and its Applications, vol. 28, Oxford University Press, Oxford, 2004. MR 2089014 (2005k:05002)
  • [16] Alan J. Hoffman, On limit points of spectral radii of non-negative symmetric integral matrices, Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Springer, Berlin, 1972, pp. 165-172. Lecture Notes in Math., Vol. 303. MR 0347860 (50 #361)
  • [17] Alan J. Hoffman and John Howard Smith, On the spectral radii of topologically equivalent graphs, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), Academia, Prague, 1975, pp. 273-281. MR 0404028 (53 #7834)
  • [18] Sophie Huczynska and Vincent Vatter, Grid classes and the Fibonacci dichotomy for restricted permutations, Electron. J. Combin. 13 (2006), no. 1, Research Paper 54, 14 pp. (electronic). MR 2240760 (2007c:05004)
  • [19] André E. Kézdy, Hunter S. Snevily, and Chi Wang, Partitioning permutations into increasing and decreasing subsequences, J. Combin. Theory Ser. A 73 (1996), no. 2, 353-359. MR 1370138 (96h:05003)
  • [20] P. W. H. Lemmens and J. J. Seidel, Equiangular lines, J. Algebra 24 (1973), 494-512. MR 0307969 (46 #7084)
  • [21] L. Lovász and J. Pelikán, On the eigenvalues of trees, Period. Math. Hungar. 3 (1973), 175-182. Collection of articles dedicated to the memory of Alfréd Rényi, II. MR 0416964 (54 #5026)
  • [22] Adam Marcus and Gábor Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A 107 (2004), no. 1, 153-160. MR 2063960 (2005b:05009), https://doi.org/10.1016/j.jcta.2004.04.002
  • [23] Maximillian M. Murphy and Vincent R. Vatter, Profile classes and partial well-order for permutations, Electron. J. Combin. 9 (2002/03), no. 2, Research paper 17, 30 pp. (electronic). Permutation patterns (Otago, 2003). MR 2028286 (2004i:06004)
  • [24] James B. Shearer, On the distribution of the maximum eigenvalue of graphs, Linear Algebra Appl. 114/115 (1989), 17-20. MR 986863 (90f:05097), https://doi.org/10.1016/0024-3795(89)90449-7
  • [25] Slobodan K. Simić, On the largest eigenvalue of unicyclic graphs, Publ. Inst. Math. (Beograd) (N.S.) 42(56) (1987), 13-19. MR 937447 (89b:05120)
  • [26] Slobodan K. Simić, On the largest eigenvalue of bicyclic graphs, Publ. Inst. Math. (Beograd) (N.S.) 46(60) (1989), 1-6. MR 1060049 (91c:05133)
  • [27] John H. Smith, Some properties of the spectrum of a graph, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), Gordon and Breach, New York, 1970, pp. 403-406. MR 0266799 (42 #1702)
  • [28] Zvezdelina E. Stankova, Forbidden subsequences, Discrete Math. 132 (1994), no. 1-3, 291-316. MR 1297387 (96e:05006), https://doi.org/10.1016/0012-365X(94)90242-9
  • [29] Vincent Vatter, Permutation classes of every growth rate above 2.48188, Mathematika 56 (2010), no. 1, 182-192. MR 2604993 (2011c:05012), https://doi.org/10.1112/S0025579309000503
  • [30] Vincent Vatter, Small permutation classes, Proc. Lond. Math. Soc. (3) 103 (2011), no. 5, 879-921. MR 2852292 (2012j:05022), https://doi.org/10.1112/plms/pdr017
  • [31] Stephen D. Waton, On permutation classes defined by token passing networks, gridding matrices and pictures: Three flavours of involvement, Ph.D. thesis, University of St Andrews, 2007.
  • [32] Wikipedia, Enumerations of specific permutation classes,
    http://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes.
  • [33] Renee Woo and Arnold Neumaier, On graphs whose spectral radius is bounded by $ \frac 32\sqrt 2$, Graphs Combin. 23 (2007), no. 6, 713-726. MR 2365422 (2008k:05137), https://doi.org/10.1007/s00373-007-0745-9
  • [34] J. Yarkony, C. Fowlkes, and A. Ihler, Covering trees and lower-bounds on quadratic assignment, IEEE Conference on Computer Vision and Pattern Recognition, 2010, pp. 887-894.

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

DOI: https://doi.org/10.1090/S0002-9947-2015-06280-1
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