Simple permutations poset

Details Simple permutations poset Simple permutations poset

2012-01-15

arxiv.org/abs/1201.3119v1

Computer Science

Discrete Mathematics

15 pages

Scientific paper

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 $\sigma, \pi$ are two simple permutations such that $\pi < \sigma$ then there exists a chain of simple permutations $\sigma^{(0)} = \sigma, \sigma^{(1)}, ..., \sigma^{(k)}=\pi$ such that $|\sigma^{(i)}| - |\sigma^{(i+1)}| = 1$ - or 2 when permutations are exceptional- and $\sigma^{(i+1)} < \sigma^{(i)}$. This characterization induces an algorithm polynomial in the size of the output to compute the simple permutations in a wreath-closed permutation class.

Affiliated with

Also associated with

No associations

Rating

Simple permutations poset does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Simple permutations poset, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simple permutations poset will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-409287