Geometric grid classes of permutations
Authors:
Michael H. Albert, M. D. Atkinson, Mathilde Bouvel, Nik Ruškuc and Vincent Vatter
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
Published electronically:
April 25, 2013
MathSciNet review:
3091268
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: A geometric grid class consists of those permutations that can be drawn on a specified set of line segments of slope 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.
- 1. M. H. Albert and M. D. Atkinson, Simple permutations and pattern restricted permutations, Discrete Math. 300 (2005), no. 1-3, 1–15. MR 2170110, https://doi.org/10.1016/j.disc.2005.06.016
- 2. 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, https://doi.org/10.1016/S0304-3975(03)00212-3
- 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, https://doi.org/10.1112/blms/bdr022
- 4. 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.
- 5. M. D. Atkinson, Restricted permutations, Discrete Math. 195 (1999), no. 1-3, 27–38. MR 1663866, https://doi.org/10.1016/S0012-365X(98)00162-9
- 6. 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, https://doi.org/10.1023/A:1016500300436
- 7. 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
- 8. Garrett Birkhoff, Lattice theory, Third edition. American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. MR 0227053
- 9. 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, https://doi.org/10.1017/CBO9780511902499.003
- 10. Robert Brignall, Grid classes and partial well order, J. Combin. Theory Ser. A 119 (2012), no. 1, 99–116. MR 2844085, https://doi.org/10.1016/j.jcta.2011.08.005
- 11. Volker Diekert, Combinatorics on traces, Lecture Notes in Computer Science, vol. 454, Springer-Verlag, Berlin, 1990. With a foreword by Wilfried Brauer. MR 1075995
- 12. Sergi Elizalde, The X-class and almost-increasing permutations, Ann. Comb. 15 (2011), no. 1, 51–68. MR 2785755, https://doi.org/10.1007/s00026-011-0082-9
- 13. Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. MR 2483235
- 14. 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
- 15. Graham Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. (3) 2 (1952), 326–336. MR 0049867, https://doi.org/10.1112/plms/s3-2.1.326
- 16. Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741
- 17. 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
- 18. 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, https://doi.org/10.1016/j.ejc.2006.12.005
- 19. 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
- 20. 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
- 21. 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, https://doi.org/10.1016/j.jcta.2004.04.002
- 22. 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
- 23. Imre Simon, Piecewise testable events, Automata theory and formal languages (Second GI Conf., Kaiserslautern, 1975), Springer, Berlin, 1975, pp. 214–222. Lecture Notes in Comput. Sci., Vol. 33. MR 0427498
- 24. Zvezdelina E. Stankova, Forbidden subsequences, Discrete Math. 132 (1994), no. 1-3, 291–316. MR 1297387, https://doi.org/10.1016/0012-365X(94)90242-9
- 25. Vincent Vatter, Small permutation classes, Proc. Lond. Math. Soc. (3) 103 (2011), no. 5, 879–921. MR 2852292, https://doi.org/10.1112/plms/pdr017
- 26. Vincent Vatter and Steve Waton, On partial well-order for monotone grid classes of permutations, Order 28 (2011), no. 2, 193–199. MR 2819219, https://doi.org/10.1007/s11083-010-9165-1
- 27. Vincent Vatter and Steve Waton, On points drawn from a circle, Electron. J. Combin. 18 (2011), no. 1, Paper 223, 10. MR 2861402
- 28. 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.
Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05A05, 05A15
Retrieve articles in all journals with MSC (2010): 05A05, 05A15
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
Email:
nik@mcs.st-and.ac.uk
Vincent Vatter
Affiliation:
Department of Mathematics, University of Florida, Gainesville, Florida 32611-8105
Email:
vatter@ufl.edu
DOI:
https://doi.org/10.1090/S0002-9947-2013-05804-7
Received by editor(s):
August 31, 2011
Received by editor(s) in revised form:
January 30, 2012
Published electronically:
April 25, 2013
Article copyright:
© Copyright 2013
American Mathematical Society