Graphs of Sets of Reduced Words

Any permutation in the finite symmetric group can be written as a product of simple transpositions $s_i = (i~i+1)$. For a fixed permutation $\sigma \in \mathfrak{S}_n$ the products of minimal length are called reduced decompositions or reduced words, and the collection of all such reduced words is denoted $R(\sigma)$. Any reduced word of $\sigma$ can be transformed into any other by a sequence of commutation moves or long braid moves. One area of interest in these sets are the congruence classes defined by using only braid moves or only commutation moves. This document will present work towards a conjectured relationship between the number of reduced words and the number of braid classes. The set $R(\sigma)$ can be drawn as a graph, $G(\sigma)$, where the vertices are the reduced words, and the edges denote the presence of a commutation or braid move between the words. This paper will present brand new work on subgraph structures in $G(\sigma)$, as well as new formulas to count the number of braid edges and commutation edges in $G(\sigma)$. The permutation $\sigma$ covers $\tau$ in the weak order poset if the length of $\tau$ is one less than the length of $\sigma$, and there exists a simple transposition $s_i$ such that $\sigma = \tau s_i$. This paper will cover new work on the relationships between the size of $R(\sigma)$ and $R(\tau)$, and how this creates a new method of writing reduced decompositions of $\sigma$ as products of permutations $\alpha$ and $\beta$, where both $\alpha$ and $\beta$ have a length greater than one. Finally, this thesis will also discuss how these results help relate the number of reduced words and the number of braid classes in certain cases.