Properties of permutations with unknown pattern avoidance descriptions

Question

Background

Many properties of permutations can be stated in terms of classical patterns. For example:

• a permutation is stack-sortable if and only if it avoids 231 (Knuth 1975)
• a permutation corresponds to a smooth Schubert variety if and only if it avoids 1324 and 2143 (Lakshmibai and Sandhya 1990)

For other properties we need a stronger notion of a pattern, e.g., the mesh patterns introduced by Brändén and Claesson (2011). For example:

• a permutation corresponds to a factorial Schubert variety if and only if it avoids 1324 and (2143,{(2,2)}) (These are the so-called forest-like permutations, Bousquet-Mélou and Butler 2007)
• a permutation is sortable in two passes through a stack if and only if it avoids 2341 and (3241,{(1,4)}) (These are the so-called West-2-stack-sortable permutations, West 1990)

There are also properties which have not been translated into patterns (to my knowledge):

• meander permutations (http://theory.cs.uvic.ca/inf/perm/StampFolding.html)
• the involutions in the symmetric group
• ...

The Question

What permutation properties do you know that have not been described by the avoidance of patterns

Motivation

I recently wrote an algorithm that given a finite set of permutations outputs the mesh patterns that the permutations avoid. This algorithm is called BiSC (derived from the last names of three people that inspired me to write the algorithm) and can conjecture the descriptions given in the first two lists above. It is available at http://staff.ru.is/henningu/programs/bisc/bisc.html and described in the paper http://arxiv.org/abs/1211.7110.

This is a community wiki question since it there is obviously not a single best answer

Answer 1

Here's one idea. For every permutation $\pi$ of length $n$, there are $n^2+1$ permutation of length $n+1$ containing $\pi$. However, once you look at permutations of length $n+2$, this quantity depends on $\pi$. In their paper "Posets of matrices and permutations with forbidden subsequences", Ray and West gave a proof that for $\pi$ of length $n$ the number of permutations of length $n+2$ containing $\pi$ is $$ (n^4+2n^3+n^2+4n+4-2j)/2, $$ where $0\le j\le n-1$ depends on $\pi$. Perhaps you could give a description of this statistic in terms of patterns of $\pi$?

Answer 2

Derangements. More generally, properties that allow superexponentially many permutations.

Answer 3

I hope I understood the question correctly. I have a feeling that questions on permutations of algebraic as opposed to combinatorial nature, could be candidates.

Lakshmibai and Sandhya's theorem is a geometric question and it is a significant theorem because it reduces geometry to combinatorics. With this understanding of your question let me attempt to give four examples:

(1) A permutation being of specific order $m$ .

Suppose we attempt pattern avoidance like: for any $k$ relatively prime to $m$ it should not have a length $k$ cycle. A permutation of order, for example $m^2$, will also satisfy that criterion and will be accepted wrongly.

(2) Permutation being even. (avoidance criterion may not work: because presence of an even number of cycles of any particular length, as opposed odd number of them, will be ok)

(3) Some irreducible character vanishing in it. This is conjugacy class question. Can be argued similarly

(4) Commuting with another specific permutation.

Answer 4

A source of interesting examples may come from infinite groups with finite presentation, possibly extending your methods to words instead of just permutations (i.e. allowing repetitions). Given a set of generators $\{x,y,\dots,z\}$ of the group $G$, which words in the alphabets of $\{x,\, x^{-1},y,\, y^{-1},\dots z,\, z^{-1}\}$ correspond to minimal length presentations of elements of $G$? In this generality, of course, the problem is intractable, but in principle one optimal answer could be given (and actually is, in some concrete cases) precisely in terms of avoidance of a list of patterns (starting, of course, from avoiding $xx^{-1}$). Clearly, an algorithm as yours may prove very useful to formulate conjecture about patterns.

Answer 5

Recall that a permutation $\pi$ is vexillary if its Rothe diagram can be transformed to a Young diagram shape via some permutation of rows and columns. Lascoux and Schützenberger showed that this is equivalent to $\pi$ being 2143-avoiding. Let us call a permutation $\pi$ "skew vexillary" if its Rothe diagram can be transformed to a skew Young diagram shape via some permutation of rows and columns. (This is not such an unreasonable thing to consider: if $\pi$ is skew vexillary then its Stanley symmetric function $F_{\pi}$ is equal to a skew Schur function- and I don't know any examples of $\pi$ with $F_{\pi}$ equal to a skew Schur function which are not skew vexillary.)

I do not know of a pattern avoidance criteria describing the set of skew vexillary permutations. As mentioned in Remark 3.8 of https://arxiv.org/abs/1811.02404, I doubt there is a description using classical pattern avoidance because all permutations in $S_5$ are skew vexillary, but only 682 of the 720 patterns in $S_6$ are skew vexillary, so it would have to involve the avoidance of at least 38 patterns of length 6. On the other hand, perhaps this condition can be described by one of the generalizations of classical pattern avoidance.