Simple permutations: decidability and unavoidable substructures

Robert Brignall, Nik Ruskuc, Vincent Vatter

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)

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. (C) 2007 Elsevier B.V. All rights reserved.

Original languageEnglish
Pages (from-to)150-163
Number of pages14
JournalTheoretical Computer Science
Volume391
Issue number1-2
DOIs
Publication statusPublished - 4 Feb 2008

Keywords

  • permutation class
  • restricted permutation
  • simple permutation
  • RESTRICTED PERMUTATIONS
  • RELATIONAL STRUCTURES
  • CLOSED-SETS
  • TOURNAMENTS

Fingerprint

Dive into the research topics of 'Simple permutations: decidability and unavoidable substructures'. Together they form a unique fingerprint.

Cite this