Reference for: the Bruhat-minimal permutations not less than a fixed permutation pi? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T04:48:04Z http://mathoverflow.net/feeds/question/41742 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41742/reference-for-the-bruhat-minimal-permutations-not-less-than-a-fixed-permutation Reference for: the Bruhat-minimal permutations not less than a fixed permutation pi? Allen Knutson 2010-10-11T02:51:04Z 2010-10-20T06:17:58Z <p>Let $\pi\in S_n$. I recently needed to understand the permutations $\rho$ such that $\rho\not\leq\pi$ in Bruhat order. Since there are $O(n!)$ of those I really wanted a description of the $O(n^2)$ minimal such.</p> <p>I have a satisfying (to me) answer now, and so I am asking whether this question is addressed in the literature.</p> <p><em>My answer:</em> It is easy to prove that the minimal $\rho$ are biGrassmannian, i.e. of the form $$1...r\ \ a+1...b\ \ r+1...a\ \ b+1...$$ for some $(r,a,b)$. In $\pi$'s permutation matrix, make a diagram by crossing out strictly North and West of each $1$. Let the <strong>co-essential boxes</strong> be the NW corners of the remaining regions, except for the region containing the SE corner. (The usual diagram comes from crossing out <em>weakly</em> South and East, and Fulton's "essential set" is the SE corners of what remains.) For each such box, let $r$ be the number of $1$s weakly NW of it, and $(r+b-a,a)$ its position, i.e. use those to define $(r,a,b)$. Then the biGrassmannian above is a minimal $\rho$, and they all arise this way, corresponding to the co-essential boxes.</p> http://mathoverflow.net/questions/41742/reference-for-the-bruhat-minimal-permutations-not-less-than-a-fixed-permutation/41814#41814 Answer by Alexander Woo for Reference for: the Bruhat-minimal permutations not less than a fixed permutation pi? Alexander Woo 2010-10-11T17:40:45Z 2010-10-20T06:17:58Z <p>Vic Reiner, Alex Yong, and I spell this out in Sections 4.1 and 4.2 of our paper on the cohomology rings of Schubert varieties: <a href="http://arxiv.org/abs/0809.2981" rel="nofollow">http://arxiv.org/abs/0809.2981</a></p> <p>This is not really original to us: for type A we refer back to Lascoux and Schutzenberger's paper Trellis et bases des groupes de Coxeter, Elect J. Combin. 3, no. 2 R27, though perhaps they don't state things exactly in this form.</p> <p>Note for Allen: The rest of our paper might not be as irrelevant to you as it might seem at first glance. Jim Carrell started a line of work back in the 80s relating cohomology rings of Schubert varieties to their local equations at the identity. Interestingly, their strongest results are only for type A.</p>