The Open UniversitySkip to content

Simple permutations: Decidability and unavoidable substructures

Brignall, Robert; Ruškuc, Nik and Vatter, Vincent (2008). Simple permutations: Decidability and unavoidable substructures. Theoretical Computer Science, 391(1-2) pp. 150–163.

DOI (Digital Object Identifier) Link:
Google Scholar: Look up in Google Scholar


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.

Item Type: Journal Article
Copyright Holders: 2007 Elsevier B.V
ISSN: 0304-3975
Keywords: permutation class; restricted permutation; simple permutation
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Mathematics, Computing and Technology
Item ID: 23471
Depositing User: Robert Brignall
Date Deposited: 13 Oct 2010 15:51
Last Modified: 15 Jan 2016 14:58
Share this page:


Scopus Citations

▼ Automated document suggestions from open access sources

Actions (login may be required)

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340