Reference for: the Bruhat-minimal permutations not less than a fixed permutation pi?

2010-10-11T02:51:04Z

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.

I have a satisfying (to me) answer now, and so I am asking whether this question is addressed in the literature.

My answer: 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 co-essential boxes be the NW corners of the remaining regions, except for the region containing the SE corner. (The usual diagram comes from crossing out weakly 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.

Answer by Alexander Woo for Reference for: the Bruhat-minimal permutations not less than a fixed permutation pi?

2010-10-11T17:40:45Z

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: http://arxiv.org/abs/0809.2981

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.

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.

Reference for: the Bruhat-minimal permutations not less than a fixed permutation pi? - MathOverflow

Reference for: the Bruhat-minimal permutations not less than a fixed permutation pi?

Answer by Alexander Woo for Reference for: the Bruhat-minimal permutations not less than a fixed permutation pi?