OFFSET
1,3
COMMENTS
The Bruhat graph on S_n is the directed graph with an edge connecting v to w whenever v and w differ by a transposition and w has more inversions than v. A maximal path in the Bruhat graph on S_n is one which goes from the identity element to the longest permutation [n,n-1,..., 2,1] written in one-line notation. Note, the Bruhat graph has more edges than the Hasse diagram for the Bruhat order. For example in S_3, [123] is connected to [321] in the Bruhat graph because they differ by a single transposition.
REFERENCES
Anders Bjorner and Francesco Brenti, "Combinatorics of Coxeter Groups". Graduate Texts in Mathematics, 231. Springer, New York, 2005.
James Carrell, "The Bruhat graph of a Coxeter group, a conjecture of Deodhar, and rational smoothness of Schubert varieties". Proceedings of Symposia in Pure Math., 56 (1994), 53--61.
LINKS
Francesco Brenti, Lattice paths and Kazhdan-Lusztig polynomials, J. Amer. Math. Soc., 11 (1998), 229-259.
CROSSREFS
KEYWORD
hard,nonn
AUTHOR
Sara Billey, Sep 07 2009
STATUS
approved