On cycles in monotone grid classes of permutations
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915574476439552 |
|---|---|
| author | Bevan, David Brignall, Robert Ruškuc, Nik |
| author_facet | Bevan, David Brignall, Robert Ruškuc, Nik |
| contents | We undertake a detailed investigation into the structure of permutations in monotone grid classes whose row-column graphs do not contain components with more than one cycle. Central to this investigation is a new decomposition, called the $M$-sum, which generalises the well-known notions of direct sum and skew sum, and enables a deeper understanding of the structure of permutations in these grid classes. Permutations which are indecomposable with respect to the $M$-sum play a crucial role in the structure of a grid class and of its subclasses, and this leads us to identify coils, a certain kind of permutation which corresponds to repeatedly traversing a chosen cycle in a particular manner.
Harnessing this analysis, we give a precise characterisation for when a subclass of such a grid class is labelled well quasi-ordered, and we extend this to characterise (unlabelled) well quasi-ordering in certain cases. We prove that a large general family of these grid classes are finitely based, but we also exhibit other examples that are not, thereby disproving a conjecture from 2006 due to Huczynska and Vatter. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_05834 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On cycles in monotone grid classes of permutations Bevan, David Brignall, Robert Ruškuc, Nik Combinatorics 05A05, 06A07 We undertake a detailed investigation into the structure of permutations in monotone grid classes whose row-column graphs do not contain components with more than one cycle. Central to this investigation is a new decomposition, called the $M$-sum, which generalises the well-known notions of direct sum and skew sum, and enables a deeper understanding of the structure of permutations in these grid classes. Permutations which are indecomposable with respect to the $M$-sum play a crucial role in the structure of a grid class and of its subclasses, and this leads us to identify coils, a certain kind of permutation which corresponds to repeatedly traversing a chosen cycle in a particular manner. Harnessing this analysis, we give a precise characterisation for when a subclass of such a grid class is labelled well quasi-ordered, and we extend this to characterise (unlabelled) well quasi-ordering in certain cases. We prove that a large general family of these grid classes are finitely based, but we also exhibit other examples that are not, thereby disproving a conjecture from 2006 due to Huczynska and Vatter. |
| title | On cycles in monotone grid classes of permutations |
| topic | Combinatorics 05A05, 06A07 |
| url | https://arxiv.org/abs/2410.05834 |