MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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:

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.