On cycles in monotone grid classes of permutations
Combinatorial Theory · 20.08.2026 · 6 (2)
DOI: 10.5070/c6.68697 ↗Kurz gefasst
Fachartikel in der Zeitschrift Combinatorial Theory, online erschienen am 20.08.2026. Verfasst von David Bevan und 2 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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. Mathematics Subject Classifications: 05A05, 06A07 Keywords: Permutation, permutation classes, grid classes, well quasi-order, labelled well quasi-order
Zitieren
APA
Bevan, D., Brignall, R., & Ruškuc, N. (2026). On cycles in monotone grid classes of permutations. Combinatorial Theory, 6(2). https://doi.org/10.5070/c6.68697
Vancouver
Bevan D, Brignall R, Ruškuc N. On cycles in monotone grid classes of permutations. Combinatorial Theory. 2026;6(2). doi:10.5070/c6.68697
BibTeX
@article{Bevan2026,
author = {Bevan, David and Brignall, Robert and Ruškuc, Nik},
title = {On cycles in monotone grid classes of permutations},
journal = {Combinatorial Theory},
year = {2026},
volume = {6},
number = {2},
doi = {10.5070/c6.68697}
}
EUVIMED