Geometric grid classes of permutations
HTML articles powered by AMS MathViewer
- by Michael H. Albert, M. D. Atkinson, Mathilde Bouvel, Nik Ruškuc and Vincent Vatter PDF
- Trans. Amer. Math. Soc. 365 (2013), 5859-5881 Request permission
Abstract:
A geometric grid class consists of those permutations that can be drawn on a specified set of line segments of slope $\pm 1$ arranged in a rectangular pattern governed by a matrix. Using a mixture of geometric and language theoretic methods, we prove that such classes are specified by finite sets of forbidden permutations, are partially well ordered, and have rational generating functions. Furthermore, we show that these properties are inherited by the subclasses (under permutation involvement) of such classes, and establish the basic lattice theoretic properties of the collection of all such subclasses.References
- M. H. Albert and M. D. Atkinson, Simple permutations and pattern restricted permutations, Discrete Math. 300 (2005), no. 1-3, 1–15. MR 2170110, DOI 10.1016/j.disc.2005.06.016
- M. H. Albert, M. D. Atkinson, and N. Ruškuc, Regular closed sets of permutations, Theoret. Comput. Sci. 306 (2003), no. 1-3, 85–100. MR 2000167, DOI 10.1016/S0304-3975(03)00212-3
- Michael H. Albert, M. D. Atkinson, and Vincent Vatter, Subclasses of the separable permutations, Bull. Lond. Math. Soc. 43 (2011), no. 5, 859–870. MR 2854557, DOI 10.1112/blms/bdr022
- 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.
- M. D. Atkinson, Restricted permutations, Discrete Math. 195 (1999), no. 1-3, 27–38. MR 1663866, DOI 10.1016/S0012-365X(98)00162-9
- M. D. Atkinson, M. M. Murphy, and N. Ruškuc, Partially well-ordered closed sets of permutations, Order 19 (2002), no. 2, 101–113. MR 1922032, DOI 10.1023/A:1016500300436
- M. D. Atkinson, M. M. Murphy, and N. Ruškuc, Pattern avoidance classes and subpermutations, Electron. J. Combin. 12 (2005), Research Paper 60, 18. MR 2180797, DOI 10.37236/1957
- Garrett Birkhoff, Lattice theory, 3rd ed., American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. MR 0227053
- Robert Brignall, A survey of simple permutations, Permutation patterns, London Math. Soc. Lecture Note Ser., vol. 376, Cambridge Univ. Press, Cambridge, 2010, pp. 41–65. MR 2732823, DOI 10.1017/CBO9780511902499.003
- Robert Brignall, Grid classes and partial well order, J. Combin. Theory Ser. A 119 (2012), no. 1, 99–116. MR 2844085, DOI 10.1016/j.jcta.2011.08.005
- Volker Diekert, Combinatorics on traces, Lecture Notes in Computer Science, vol. 454, Springer-Verlag, Berlin, 1990. With a foreword by Wilfried Brauer. MR 1075995, DOI 10.1007/3-540-53031-2
- Sergi Elizalde, The X-class and almost-increasing permutations, Ann. Comb. 15 (2011), no. 1, 51–68. MR 2785755, DOI 10.1007/s00026-011-0082-9
- Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. MR 2483235, DOI 10.1017/CBO9780511801655
- Roland Fraïssé, Sur l’extension aux relations de quelques propriétés des ordres, Ann. Sci. Ecole Norm. Sup. (3) 71 (1954), 363–388 (French). MR 0069239, DOI 10.24033/asens.1027
- Graham Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. (3) 2 (1952), 326–336. MR 49867, DOI 10.1112/plms/s3-2.1.326
- Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741, DOI 10.1017/CBO9780511551574
- John M. Howie, Fundamentals of semigroup theory, London Mathematical Society Monographs. New Series, vol. 12, The Clarendon Press, Oxford University Press, New York, 1995. Oxford Science Publications. MR 1455373
- Sophie Huczynska and Nik Ruškuc, Pattern classes of permutations via bijections between linearly ordered sets, European J. Combin. 29 (2008), no. 1, 118–139. MR 2368620, DOI 10.1016/j.ejc.2006.12.005
- 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. MR 2240760
- Tomá Kaiser and Martin Klazar, On growth rates of closed permutation classes, Electron. J. Combin. 9 (2002/03), no. 2, Research paper 10, 20. Permutation patterns (Otago, 2003). MR 2028280
- 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, DOI 10.1016/j.jcta.2004.04.002
- 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. Permutation patterns (Otago, 2003). MR 2028286
- Imre Simon, Piecewise testable events, Automata theory and formal languages (Second GI Conf., Kaiserslautern, 1975), Lecture Notes in Comput. Sci., Vol. 33, Springer, Berlin, 1975, pp. 214–222. MR 0427498
- Zvezdelina E. Stankova, Forbidden subsequences, Discrete Math. 132 (1994), no. 1-3, 291–316. MR 1297387, DOI 10.1016/0012-365X(94)90242-9
- Vincent Vatter, Small permutation classes, Proc. Lond. Math. Soc. (3) 103 (2011), no. 5, 879–921. MR 2852292, DOI 10.1112/plms/pdr017
- Vincent Vatter and Steve Waton, On partial well-order for monotone grid classes of permutations, Order 28 (2011), no. 2, 193–199. MR 2819219, DOI 10.1007/s11083-010-9165-1
- Vincent Vatter and Steve Waton, On points drawn from a circle, Electron. J. Combin. 18 (2011), no. 1, Paper 223, 10. MR 2861402
- Steve Waton, On permutation classes defined by token passing networks, gridding matrices and pictures: Three flavours of involvement, Ph.D. thesis, Univ. of St Andrews, 2007.
Additional Information
- Michael H. Albert
- Affiliation: Department of Computer Science, University of Otago, Dunedin, New Zealand
- Email: malbert@cs.otago.ac.nz
- M. D. Atkinson
- Affiliation: Department of Computer Science, University of Otago, Dunedin, New Zealand
- Email: mike@cs.otago.ac.nz
- Mathilde Bouvel
- Affiliation: CNRS, LaBRI, Université Bordeaux 1, Bordeaux, France
- Email: mathilde.bouvel@labri.fr
- Nik Ruškuc
- Affiliation: School of Mathematics and Statistics, University of St. Andrews, St. Andrews, Scotland
- MR Author ID: 337959
- ORCID: 0000-0003-2415-9334
- Email: nik@mcs.st-and.ac.uk
- Vincent Vatter
- Affiliation: Department of Mathematics, University of Florida, Gainesville, Florida 32611-8105
- Email: vatter@ufl.edu
- Received by editor(s): August 31, 2011
- Received by editor(s) in revised form: January 30, 2012
- Published electronically: April 25, 2013
- © Copyright 2013 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 365 (2013), 5859-5881
- MSC (2010): Primary 05A05, 05A15
- DOI: https://doi.org/10.1090/S0002-9947-2013-05804-7
- MathSciNet review: 3091268