Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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
Published electronically: April 25, 2013
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?)


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: http://dx.doi.org/10.1090/S0002-9947-2013-05804-7
PII: S 0002-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