×

An improved tableau criterion for Bruhat order. (English) Zbl 0884.05096

Electron. J. Comb. 3, No. 1, Research paper R22, 5p. (1996); printed version J. Comb. 3, No. 1, 311-315 (1996).
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.

MSC:

05E15 Combinatorial aspects of groups and algebras (MSC2010)
20F55 Reflection and Coxeter groups (group-theoretic aspects)
14M15 Grassmannians, Schubert varieties, flag manifolds
PDF BibTeX XML Cite
Full Text: EuDML EMIS