Simple permutations: decidability and unavoidable substructures

2006/09/07 by Robert Brignall, Nik Ruškuc, Brignall, Robert +3 · 1 citation
Mathematics · Computer Science · Engineering · #Advanced Combinatorial Mathematics #semigroups and automata theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.math/0609211

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.

Citations

• Simple permutations and pattern restricted permutations

Cited by

• Wreath Products of Permutation Classes
• Simple permutations and algebraic generating functions

Related

• A Survey of Simple Permutations
• An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
• What Could Be a Simple Permutation?
• Decomposing simple permutations, with enumerative consequences
• Deflatability of Permutation Classes