Simple permutations: decidability and unavoidable substructures

Abstract

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.

References in corpus (1)

• Decomposing simple permutations, with enumerative consequences

Cited by in corpus (3)

• Simple permutations and algebraic generating functions
• Decomposing simple permutations, with enumerative consequences
• Wreath Products of Permutation Classes