tailieunhanh - Báo cáo toán học: "An improved tableau criterion for Bruhat order"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: An improved tableau criterion for Bruhat order. | An improved tableau criterion for Bruhat order Anders Bjorner and Francesco Brenti Matematiska Institutionen Kungl. Tekniska Hogskolan S-100 44 Stockholm Sweden bjorner@ Dipartimento di Matematica Universita degli Studi di Perugia I-061 23 Perugia Italy brenti@ Submitted March 26 1996 Accepted July 12 1996. Abstract To decide whether two permutations are comparable in Bruhat order of Sn with the well-known tableau criterion requires 2 comparisons of entries in certain sorted arrays. We show that to decide whether x y only d1 d2 . dk of these comparisons are needed where d1 d2 . dk i 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. 1 Introduction The classical tableau criterion for Bruhat order on Sn says that x y if and only if xi k yi k for all 1 i k n 1 where xi k is the i-th entry in the increasing rearrangement of x1 x2 . xk and similarly for yi k. For instance 21435 53412 is checked by cellwise comparisons in the arrays 1991 Mathematics Subject Classification. Primary 05E15 20F55 Secondary 14M15. Research supported by the Volkswagen-Stiftung RiP-program at Oberwolfach and by EC grant No. CHRX-CT93-0400. 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 3 1996 R22 2 12 3 4 1 3 4 5 1 2 4 3 4 5 12 3 5 2 5 These are actually tableaux rows and columns are increasing hence the name of the criterion. This characterization of Bruhat order in the geometric version was found by Ehres-mann E to describe cell decompositions of ag manifolds. The construction but not the characterization also appears in Lehmann L for purposes in statistics. Similar tableau criteria were given for the other classical finite groups by Proctor P and for certain affine Weyl groups by Bjorner and Brenti BB and by Eriksson and Eriksson HE EE . In 1977 Deodhar D published a characterization of Bruhat order on any Coxeter group in terms of the induced order on minimal length coset representatives .