An improved tableau criterion for Bruhat order (Q1379164)

Summary: To decide whether two permutations are comparable in Bruhat order of \(S_n\) with the well-known tableau criterion requires \(\binom{n}{2}\) comparisons of entries in certain sorted arrays. We show that to decide whether \(x\leq y\) only \(d_1+d_2+\cdots+d_k\) of these comparisons are needed, where \(\{d_1,d_2,\dots,d_k\} = \{i\mid x(i)>x(i+1)\}\). This is obtained as a consequence of a sharper version of Deodhar's criterion, which is valid for all Coxeter groups.