Properties of permutations with unknown pattern avoidance descriptions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T18:22:18Z http://mathoverflow.net/feeds/question/115636 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115636/properties-of-permutations-with-unknown-pattern-avoidance-descriptions Properties of permutations with unknown pattern avoidance descriptions Henning Arnór Úlfarsson 2012-12-06T19:37:13Z 2012-12-18T23:21:23Z <h2>Background</h2> <p>Many properties of permutations can be stated in terms of <em>classical patterns</em>. For example:</p> <ul> <li>a permutation is <em>stack-sortable</em> if and only if it avoids 231 (Knuth 1975)</li> <li>a permutation corresponds to a <em>smooth</em> Schubert variety if and only if it avoids 1324 and 2143 (Lakshmibai and Sandhya 1990)</li> </ul> <p>For other properties we need a stronger notion of a pattern, e.g., the <em>mesh patterns</em> introduced by Brändén and Claesson (2011). For example:</p> <ul> <li>a permutation corresponds to a factorial Schubert variety if and only if it avoids 1324 and (2143,{(2,2)}) (These are the so-called <em>forest-like permutations</em>, Bousquet-Mélou and Butler 2007)</li> <li>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 <em>West-2-stack-sortable permutations</em>, West 1990)</li> </ul> <p>There are also properties which have not been translated into patterns (to my knowledge):</p> <ul> <li><em>meander</em> permutations (http://theory.cs.uvic.ca/inf/perm/StampFolding.html)</li> <li>the <em>involutions</em> in the symmetric group</li> <li>...</li> </ul> <h2>The Question</h2> <blockquote> <p>What permutation properties do you know that have not been described by the avoidance of patterns</p> </blockquote> <h2>Motivation</h2> <p>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 <a href="http://staff.ru.is/henningu/programs/bisc/bisc.html" rel="nofollow">http://staff.ru.is/henningu/programs/bisc/bisc.html</a> and described in the paper <a href="http://arxiv.org/abs/1211.7110" rel="nofollow">http://arxiv.org/abs/1211.7110</a>.</p> <p>This is a community wiki question since it there is obviously not a single best answer</p> http://mathoverflow.net/questions/115636/properties-of-permutations-with-unknown-pattern-avoidance-descriptions/116506#116506 Answer by P Vanchinathan for Properties of permutations with unknown pattern avoidance descriptions P Vanchinathan 2012-12-16T02:49:32Z 2012-12-16T02:49:32Z <p>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.</p> <p>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:</p> <p>(1) A permutation being of specific order $m$ .</p> <p>Suppose we attempt pattern avoidance like: <em>for any $k$ relatively prime to $m$ it should not have a length $k$ cycle.</em> A permutation of order, for example $m^2$, will also satisfy that criterion and will be accepted wrongly.</p> <p>(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)</p> <p>(3) Some irreducible character vanishing in it. This is conjugacy class question. Can be argued similarly</p> <p>(4) Commuting with another specific permutation.</p> http://mathoverflow.net/questions/115636/properties-of-permutations-with-unknown-pattern-avoidance-descriptions/116684#116684 Answer by Rodrigo A. Pérez for Properties of permutations with unknown pattern avoidance descriptions Rodrigo A. Pérez 2012-12-18T05:43:38Z 2012-12-18T05:43:38Z <p>Derangements. More generally, properties that allow superexponentially many permutations.</p> http://mathoverflow.net/questions/115636/properties-of-permutations-with-unknown-pattern-avoidance-descriptions/116699#116699 Answer by Pietro Majer for Properties of permutations with unknown pattern avoidance descriptions Pietro Majer 2012-12-18T13:01:30Z 2012-12-18T13:01:30Z <p>A source of interesting examples may come from infinite groups with finite presentation, possibly extending your methods to <em>words</em> instead of just <em>permutations</em> (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.</p> http://mathoverflow.net/questions/115636/properties-of-permutations-with-unknown-pattern-avoidance-descriptions/116742#116742 Answer by Vince Vatter for Properties of permutations with unknown pattern avoidance descriptions Vince Vatter 2012-12-18T23:21:23Z 2012-12-18T23:21:23Z <p>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$?</p> <p>References and a bit more discussion can be found in this paper: <a href="http://www.math.ufl.edu/~vatter/publications/pp2007-problems/" rel="nofollow">http://www.math.ufl.edu/~vatter/publications/pp2007-problems/</a></p>