Commutation Classes of the Reduced Words for the Longest Element of ${\mathfrak S}_n$

Abstract

Using the standard Coxeter presentation for the symmetric group Sn, two re- duced expressions for the same group element w are said to be commutationally equivalent if one expression can be obtained from the other one by applying a nite sequence of commutations. The commutation classes can be seen as the vertices of a graph bG (w), where two classes are connected by an edge if elements of those classes di er by a long braid relation. We compute the radius and diameter of the graph bG (w0), for the longest element w0 in the symmetric group Sn, and show that it is not a planar graph for n > 6. We also describe a family of commutation classes which contains all atoms, that is classes with one single element, and a subfamily of commutation classes whose elements are in bijection with standard Young tableaux of certain moon-polyomino shapes.