Simple permutations: Decidability and unavoidable substructures

https://doi.org/10.1016/j.tcs.2007.10.037Get rights and content
Under an Elsevier user license
open archive

Abstract

We prove that it is decidable whether 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.

Keywords

Permutation class
Restricted permutation
Simple permutation

Cited by (0)

1

Present address: University of Bristol, Department of Mathematics, Bristol, BS8 1UJ, UK