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.

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

Re your question 1: Guillemot and Marx, "Finding small patterns in permutations in linear time", 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).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.