Combinatorial Theory

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