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.

• One question about your terms. $r$ is taking a composition power of pi? – Chad Brewbaker Apr 27 '14 at 15:41
• 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. Apr 28 '14 at 6:55