Skip to main content
MathOverflow

Return to Question

Bounty Ended with Vince Vatter's answer chosen by Henning Arnór Úlfarsson
Bounty Started worth 100 reputation by Henning Arnór Úlfarsson
Post Made Community Wiki
Source Link
Henning Arnór Úlfarsson
Henning Arnór Úlfarsson
  • 1.2k
  • 9
  • 19

Properties of permutations with unknown pattern avoidance descriptions

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):

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