RHOMBIC TILINGS OF POLYGONS AND CLASSES OF REDUCED WORDS IN
COXETER GROUPS

Serge Elnitsky

In the standard Coxeter presentation, the symmetric group S_{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 and J. Propp, 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.

Doctoral Committee:

Associate Professor John R. Stembridge, Chair
Professor John E. Fornaess
Professor Robert L. Griess, Jr.
Assistant Professor William Jockusch
Professor Michael B. Woodroofe