Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: The Skeleton of a Reduced Word and a Correspondence of Edelman and Greene. | The Skeleton of a Reduced Word and a Correspondence of Edelman and Greene Stefan Felsner Freie Universitat Berlin Fachbereich Mathematik und Informatik Takustr. 9 14195 Berlin Germany felsner@ Submitted July 31 2000 Accepted December 29 2000 Abstract Stanley conjectured that the number of maximal chains in the weak Bruhat order of Sn or equivalently the number of reduced decompositions of the reverse of the identity permutation w0 n n 1 n 2 . 2 1 equals the number of standard Young tableaux of staircase shape s n 1 n 2 . 1 . Originating from this conjecture remarkable connections between standard Young tableaux and reduced words have been discovered. Stanley proved his conjecture algebraically later Edelman and Greene found a bijective proof. We provide an extension of the Edelman and Greene bijection to a larger class of words. This extension is similar to the extension of the Robinson-Schensted correspondence to two line arrays. Our proof is inspired by Viennot s planarized proof of the Robinson-Schensted correspondence. As it is the case with the classical correspondence the planarized proofs have their own beauty and simplicity. Key Words. Chains in the weak Bruhat order reduced decompositions Young tableaux bijective proof planarization. Mathematics Subject Classifications 2000 . 05E10 05A15 20F55. 1 Introduction Stanley conjectured in 14 that the number of maximal chains in the weak Bruhat order of Sn or equivalently the number of reduced decompositions of the reverse of the identity permutation Wo n n 1 n 2 . 2 1 equals the number fs of standard Young tableaux An extended abstract of this paper has appered in the proceedings of FPSAC 00 see 3 THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R10 1 of staircase shape s n 1 n 2 . 1 . Evaluating fs with the hook-formula yields n 2 I e wo I 2n 3 2n 5 2 2n 7 3 . 5n-3 3n-2. Originating from this conjecture some remarkable connections between standard Young tableaux and reduced words have been .
