Geometric grid classes of permutations

Albert, Michael; Atkinson, M.; Bouvel, Mathilde; Ruškuc, Nik; Vatter, Vincent

doi:10.1090/S0002-9947-2013-05804-7

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 $\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.

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.