<p>Re your question 1: Guillemot and Marx, "<a href="http://www.cs.iastate.edu/~sguillem/papers/SODA14.pdf">Finding small patterns in permutations in linear time</a>", SODA 2014 solves these problems in linear time, and more generally gives a linear time recognition algorithm for every fixed permutation class with a finite basis.</p>

<p>I don't know of an answer for question 2 (when the subpattern may be variable in size).</p>

CC BY-SA 3.0
2014-04-28T07:31:59.720Z
2014-04-28T07:31:59.720Z
David Eppstein
<p>I'm interested in permutations classes defined by one or several excluded patterns of length 4. In particular, the following classes seem interesting but not so-well studied algorithmically.</p>

<ol>
<li><p>the <em>skew-merged permutations</em> consist of the permutations that can be partitioned in an increasing and a decreasing subsequence; their basis is $\{3412, 2143\}$.</p></li>
<li><p>the <em>vexillary permutations</em> have basis $\{2143\}$; they have been introduced by Lascoux and Schützenberger in connection with Schubert calculus ('Schubert polynomials and the Littlewood–Richardson rule', Letters in Mathematical Physics 10(2), 111-124).</p></li>
</ol>

<p>By the basis definition, it is immediate that a permutation $\pi$ is skew-merged iff both $\pi$ and $\pi^r$ are vexillary; this suggests some possible link between these two classes. I am interested in the following algorithmic questions:</p>

<ol>
<li><p>Are there linear-time recognition algorithms for these classes? By the previous remark, an algorithm for class 2 would immediately yield an algorithm for class 1, although I suspect a more direct algorithm to exist in that case.</p></li>
<li><p>What is the complexity of the subpattern problem for two skew-merged or two vexillary permutations? The subpattern problem is known to be polynomial for separable and 2-increasing permutations, and these classes seem the next to study.</p></li>
</ol>

CC BY-SA 3.0
2014-04-27T15:41:50.693Z
One question about your terms. $r$ is taking a composition power of pi?
Chad Brewbaker
CC BY-SA 3.0
2014-04-28T06:55:41.427Z
Can you pick a better title?  I suggest titles that help convey the essence of the problem, and make it easy for others who might be interested to quickly judge what the question is about.
D.W.
<ds.algorithms><co.combinatorics><permutations>
More questions about permutations
NisaiVloot
# More questions about permutations

(Asked by: username_0 on 2014-04-27)

I'm interested in permutations classes defined by one or several excluded patterns of length 4. In particular, the following classes seem interesting but not so-well studied algorithmically.

1. the *skew-merged permutations* consist of the permutations that can be partitioned in an increasing and a decreasing subsequence; their basis is $\{3412, 2143\}$.
2. the *vexillary permutations* have basis $\{2143\}$; they have been introduced by Lascoux and Schützenberger in connection with Schubert calculus ('Schubert polynomials and the Littlewood–Richardson rule', Letters in Mathematical Physics 10(2), 111-124).

By the basis definition, it is immediate that a permutation $\pi$ is skew-merged iff both $\pi$ and $\pi^r$ are vexillary; this suggests some possible link between these two classes. I am interested in the following algorithmic questions:

1. Are there linear-time recognition algorithms for these classes? By the previous remark, an algorithm for class 2 would immediately yield an algorithm for class 1, although I suspect a more direct algorithm to exist in that case.
2. What is the complexity of the subpattern problem for two skew-merged or two vexillary permutations? The subpattern problem is known to be polynomial for separable and 2-increasing permutations, and these classes seem the next to study.

**Tags:** ds.algorithms, co.combinatorics, permutations
> **Comments:**
> **username_1**: One question about your terms. $r$ is taking a composition power of pi?  
> **username_2**: Can you pick a better title?  I suggest titles that help convey the essence of the problem, and make it easy for others who might be interested to quickly judge what the question is about.  

---

## 1 answers

### Answer by username_3 on 2014-04-28. Score: 7

Re your question 1: Guillemot and Marx, "[Finding small patterns in permutations in linear time](http://www.cs.iastate.edu/~sguillem/papers/SODA14.pdf)", SODA 2014 solves these problems in linear time, and more generally gives a linear time recognition algorithm for every fixed permutation class with a finite basis.

I don't know of an answer for question 2 (when the subpattern may be variable in size).


---

