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)

 
 

 

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

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 $ \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 [Enhancements On Off] (What's this?)

  • 1. Michael H. Albert and M. D. Atkinson, Simple permutations and pattern restricted permutations, Discrete Math. 300 (2005), no. 1-3, 1-15. MR 2170110 (2006d:05007)
  • 2. Michael H. Albert, M. D. Atkinson, and Nik Ruškuc, Regular closed sets of permutations, Theoret. Comput. Sci. 306 (2003), no. 1-3, 85-100. MR 2000167 (2004d:68106)
  • 3. Michael H. Albert, M. D. Atkinson, and Vincent Vatter, Subclasses of the separable permutations, Bull. Lond. Math. Soc. 43 (2011), 859-870. MR 2854557
  • 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. -, Restricted permutations, Discrete Math. 195 (1999), no. 1-3, 27-38. MR 1663866 (99i:05004)
  • 6. M. D. Atkinson, M. M. Murphy, and Nik Ruškuc, Partially well-ordered closed sets of permutations, Order 19 (2002), no. 2, 101-113. MR 1922032 (2003g:06002)
  • 7. -, Pattern avoidance classes and subpermutations, Electron. J. Combin. 12 (2005), no. 1, Research paper 60, 18 pp. MR 2180797 (2006g:05007)
  • 8. Garrett Birkhoff, Lattice theory, Third edition. American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. MR 0227053 (37:2638)
  • 9. Robert Brignall, A survey of simple permutations, Permutation Patterns (Steve Linton, Nik Ruškuc, and Vincent Vatter, eds.), London Mathematical Society Lecture Note Series, vol. 376, Cambridge University Press, 2010, pp. 41-65. MR 2732823
  • 10. -, Grid classes and partial well order, J. Combin. Theory Ser. A 119 (2012), 99-116. MR 2844085 (2012k:06004)
  • 11. Volker Diekert, Combinatorics on traces, Lecture Notes in Computer Science, vol. 454, Springer-Verlag, Berlin, 1990. MR 1075995 (92d:68070)
  • 12. Sergi Elizalde, The $ \mathcal {X}$-class and almost-increasing permutations, Ann. Comb. 15 (2011), 51-68. MR 2785755
  • 13. Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. MR 2483235 (2010h:05005)
  • 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. MR 0069239 (16,1006b)
  • 15. Graham Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. (3) 2 (1952), 326-336. MR 0049867 (14:238e)
  • 16. Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741 (94e:03002)
  • 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 (98e:20059)
  • 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 (2008j:05011)
  • 19. Sophie Huczynska and Vincent Vatter, Grid classes and the Fibonacci dichotomy for restricted permutations, Electron. J. Combin. 13 (2006), Research paper 54, 14 pp. MR 2240760 (2007c:05004)
  • 20. Tomáš Kaiser and Martin Klazar, On growth rates of closed permutation classes, Electron. J. Combin. 9 (2003), no. 2, Research paper 10, 20 pp. MR 2028280 (2004m:05026)
  • 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 (2005b:05009)
  • 22. Maximillian M. Murphy and Vincent Vatter, Profile classes and partial well-order for permutations, Electron. J. Combin. 9 (2003), no. 2, Research paper 17, 30 pp. MR 2028286 (2004i:06004)
  • 23. Imre Simon, Piecewise testable events, Automata theory and formal languages (Second GI Conf., Kaiserslautern, 1975) (Berlin), Lecture Notes in Comput. Sci., vol. 33, Springer, 1975, pp. 214-222. MR 0427498 (55:530)
  • 24. Zvezdelina E. Stankova, Forbidden subsequences, Discrete Math. 132 (1994), no. 1-3, 291-316. MR 1297387 (96e:05006)
  • 25. Vincent Vatter, Small permutation classes, Proc. Lond. Math. Soc. (3) 103 (2011), 879-921. MR 2852292 (2012j:05022)
  • 26. Vincent Vatter and Steve Waton, On partial well-order for monotone grid classes of permutations, Order 28 (2011), 193-199. MR 2819219
  • 27. -, On points drawn from a circle, Electron. J. Combin. 18 (1) (2011), Paper 223, 10 pp. MR 2861402 (2012m:05046)
  • 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.

Similar Articles

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

American Mathematical Society