Properties of permutations with unknown pattern avoidance descriptions - MathOverflow

Properties of permutations with unknown pattern avoidance descriptions

2012-12-06T19:37:13Z

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 by P Vanchinathan for Properties of permutations with unknown pattern avoidance descriptions

2012-12-16T02:49:32Z

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 by Rodrigo A. Pérez for Properties of permutations with unknown pattern avoidance descriptions

2012-12-18T05:43:38Z

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

Answer by Pietro Majer for Properties of permutations with unknown pattern avoidance descriptions

2012-12-18T13:01:30Z

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 by Vince Vatter for Properties of permutations with unknown pattern avoidance descriptions

2012-12-18T23:21:23Z

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$. 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 k-1$ depends on $\pi$. Perhaps you could give a description of this statistic in terms of patterns of $\pi$?

References and a bit more discussion can be found in this paper: http://www.math.ufl.edu/~vatter/publications/pp2007-problems/