Simple permutations poset

2012/01/15 by Adeline Pierrot, Adeline, Pierrot, Dominique Rossin +1
Mathematics · Computer Science · Engineering · #Advanced Combinatorial Mathematics #semigroups and automata theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1201.3119

Abstract

This article studies the poset of simple permutations with respect to the pattern involvement. We specify results on critically indecomposable posets obtained by Schmerl and Trotter to simple permutations and prove that if σ, π are two simple permutations such that π< σ then there exists a chain of simple permutations σ⁽⁰⁾ = σ, σ⁽¹⁾, ..., σ^(k)=π such that |σ⁽ⁱ⁾| - |σ⁽ⁱ⁺¹⁾| = 1 - or 2 when permutations are exceptional- and σ⁽ⁱ⁺¹⁾ < σ⁽ⁱ⁾. This characterization induces an algorithm polynomial in the size of the output to compute the simple permutations in a wreath-closed permutation class.

Related

• A Survey of Simple Permutations
• What Could Be a Simple Permutation?
• Blockwise simple permutations
• A simple proof of a theorem of Schmerl and Trotter for permutations
• Counting (3+1) - Avoiding permutations