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.