Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-27T05:49:32.873Z Has data issue: false hasContentIssue false
  • English
  • Français

An Elementary Proof of Bevan's Theorem on the Growth of Grid Classes of Permutations

Part of: Combinatorics

Published online by Cambridge University Press:  11 March 2019

Michael Albert  and
Vincent Vatter
Michael Albert
Affiliation:
Department of Computer Science, University of Otago, Dunedin, New Zealand
Vincent Vatter
Affiliation:
Department of Mathematics, University of Florida, Gainesville, FL, USA ([email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Bevan established that the growth rate of a monotone grid class of permutations is equal to the square of the spectral radius of a related bipartite graph. We give an elementary and self-contained proof of a generalization of this result using only Stirling's formula, the method of Lagrange multipliers, and the singular value decomposition of matrices. Our proof relies on showing that the maximum over the space of n × n matrices with non-negative entries summing to one of a certain function of those entries, parametrized by the entries of another matrix Γ of non-negative real numbers, is equal to the square of the largest singular value of Γ and that the maximizing point can be expressed as a Hadamard product of Γ with the tensor product of singular vectors for its greatest singular value.

Keywords

grid classesgrowth ratespermutation patternssingular values

MSC classification

Primary: 05A05: Permutations, words, matrices
Secondary: 05A16: Asymptotic enumeration
Type
Research Article
Information
Proceedings of the Edinburgh Mathematical Society , Volume 62 , Issue 4 , November 2019 , pp. 975 - 984
Copyright
Copyright © Edinburgh Mathematical Society 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1Albert, M., Pantone, J. and Vatter, V., On the growth of merges and staircases of permutation classes, Rocky Mountain J. Math., to appear. arXiv:1608.06969.Google Scholar
2Bevan, D., Growth rates of permutation grid classes, tours on graphs, and the spectral radius, Trans. Amer. Math. Soc. 367 (2015), 5863–5889.Google Scholar
3Bevan, D., On the growth of permutation classes, PhD thesis, Open University (2015).Google Scholar
4Marcus, A. and Tardos, G., Excluded permutation matrices and the Stanley–Wilf conjecture, J. Combin. Theory Ser. A 107 (2004), 153–160.Google Scholar
5Pantone, J. and Vatter, V., Growth rates of permutation classes: categorization up to the uncountability threshold, Israel J. Math., to appear. arXiv:1605.04289.Google Scholar
6Stankova, Z., Forbidden subsequences, Discrete Math. 132 (1994), 291–316.Google Scholar
7Vatter, V., Growth rates of permutation classes: from countable to uncountable, Proc. Lond. Math. Soc. (3), to appear. arXiv:1605.04297.Google Scholar
8Vatter, V., Small permutation classes, Proc. Lond. Math. Soc. (3) 103 (2011), 879–921.Google Scholar
9Vatter, V., Permutation classes, In Handbook of enumerative combinatorics (ed. Bóna, M.), pp. 754–833 (CRC Press, Boca Raton, FL, 2015).Google Scholar