Rhombic tilings of polygons and classes of reduced words in Coxeter groups.

Abstract

In the standard Coxeter presentation, the symmetric group $S\sb{n}$ is generated by the adjacent transpositions (1,2), (2,3), ..., $(n - 1,n).$ For any given permutation, we consider all minimal-length factorizations thereof as a product of the generators. Any two transpositions $(i,i+1)$ and $(j,j+1)$ commute if the numbers i and j are not consecutive; thus, in any factorization, their order can be switched to obtain another factorization of the same permutation. Extending this to an equivalence relation, we study the resulting equivalence classes, and establish a bijection between those classes and rhombic tilings of a certain 2n-gon determined by the permutation. We also study the graph structure induced on the set of tilings by other Coxeter relations. For a special case, we use lattice-path diagrams to prove an enumerative conjecture by G. Kuperberg, as well as a q-analogue thereof. Finally, we give similar constructions for two other families of finite Coxeter groups, namely those of types B and D.