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