Simple permutations: decidability and unavoidable substructures
With Robert Brignall and Nik Ruškuc.
Theoretical Computer Science 391 (2008), 150–163.
We prove that it is decidable if a finitely based permutation class contains infinitely many simple permutations, and establish an unavoidable substructure result for simple permutations: every sufficiently long simple permutation contains an alternation or oscillation of length k.
Download the paper:
- download from the journal website (subscription required)
- ps
- source
Related links:
- It turns out that our conjectures were half correct. The “pin class” we discussed at the end of the paper does have a rational generating function, but is not finitely based. See “Enumeration of pin-permutations” by Frédérique Bassino, Mathilde Bouvel, and Dominique Rossin for the details; the enumeration of the pin class is given by sequence A138619 in the OEIS.
- Slides (pdf) for a talk Robert gave about this work at the Fourth International Conference on Permutations Patterns.