EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On cycles in monotone grid classes of permutations

David Bevan, Robert Brignall, Nik Ruškuc

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

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →