 |
 |
|
|
| HAL: hal-00640059, version 1 |
| arXiv: 1108.6319 |
| Detailed view |  Export this paper |
 |
| Transactions of the American Mathematical Society (2012) à paraitre |
|
|
|
|
| Geometric grid classes of permutations |
|
|
| Michael H. Albert 1M. D. Atkinson 1 |
|
|
| (2012) |
|
|
|
| A geometric grid class consists of those permutations that can be drawn on a specified set of line segments of slope \pm1 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: | Department of Computer Science, Otago University |
|
|
|
Otago University |
|
|
| 2: | Laboratoire Bordelais de Recherche en Informatique (LaBRI) |
|
|
|
CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II |
|
|
| 3: | School of Mathematics and Statistics, University of St Andrews |
|
|
|
University of Saint Andrews |
|
|
| 4: | Department of Mathematics [Gainesville] |
|
|
|
University of Florida |
|
|
|
|
|
|
|
|
|
| Subject | : | Mathematics/Combinatorics |
|
|
| Fulltext link: |
|
| http://fr.arXiv.org/abs/1108.6319 |
| hal-00640059, version 1 | |
| http://hal.archives-ouvertes.fr/hal-00640059 | |
| oai:hal.archives-ouvertes.fr:hal-00640059 | |
| From: Mathilde Bouvel | |
| Submitted on: Thursday, 10 November 2011 15:38:54 | |
| Updated on: Monday, 2 July 2012 11:30:20 | |
