Labelled Well-Quasi-Order in Juxtapositions of Permutation Classes

Brignall, Robert (2024). Labelled Well-Quasi-Order in Juxtapositions of Permutation Classes. The Electronic Journal of Combinatorics, 31(2), article no. P2.21.



The $\textit{juxtaposition}$ of permutation classes $\mathcal{C}$ and $\mathcal{D}$ is the class of all permutations formed by concatenations $\sigma\tau$, such that $\sigma$ is order isomorphic to a permutation in $\mathcal{C}$, and $\tau$ to a permutation in $\mathcal{D}$. We give simple necessary and sufficient conditions on the classes $\mathcal{C}$ and $\mathcal{D}$ for their juxtaposition to be labelled well-quasi-ordered (lwqo): namely that both $\mathcal{C}$ and $\mathcal{D}$ must themselves be lwqo, and at most one of $\mathcal{C}$ or $\mathcal{D}$ can contain arbitrarily long zigzag permutations. We also show that every class without long zigzag permutations has a growth rate which must be integral.

Viewing alternatives

Download history


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions