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.



Reference for: the Bruhat-minimal permutations not less than a fixed permutation pi?
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.


