# On Graphs of Sets of Reduced Words

Jennifer Elder  Department of Computer Science, Math & Physics. Missouri
Western State University, 4525 Downs Drive, St. Joseph, MO 64507
<EMAIL_ADDRESS>
###### Abstract.

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 $\mathcal{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 or only commutation relations. The set
$\mathcal{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 presents 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)$. We also include work on
bounds for the number of braid and commutation classes in
$\mathcal{R}(\sigma)$.

###### Key words and phrases:

Permutation, reduced word, graph, the weak order lattice, recursive formula

###### 1991 Mathematics Subject Classification:

Primary: 05A05, Secondary, 05C12

##  1\. Introduction

Permutations are extremely useful and complex combinatorial objects, which has
led to extensive study of their properties. This study spans general
permutation statistics [5, 10], which include patterns [14, 13] or descent and
ascent properties [2, 4], to decomposition into cycles and related structures
[8, 12, 15]. Specifically, the decomposition of permutations into products of
cycles called _simple transpositions_.

######  Definition 1.1.

Let $[n]:=\\{1,2,\ldots n\\}$, and denote the symmetric group on this set as
$\mathfrak{S}_{n}$. A permutation $\sigma\in\mathfrak{S}_{n}$ is written in
one line notation as $\sigma=[\sigma_{1}~{}\sigma_{2}~{}\ldots~{}\sigma_{n}]$,
where $\sigma(i)=\sigma_{i}$.

We define the descent set of $\sigma$ as
$\text{Des}(\sigma)=\\{i\in[n]\mid\sigma_{i}>\sigma_{i+1}\\}$

The group $\mathfrak{S}_{n}$ can be generated by a set of functions called
simple transpositions: $s_{i}=(i~{}i+1)$ for $1\leq i\leq n-1$.

These generators also have specific relationships:

$\displaystyle s_{i}^{2}$ $\displaystyle=e,$ (1) $\displaystyle s_{i}s_{j}$
$\displaystyle=s_{j}s_{i},\mbox{ for }|i-j|>1,$ (2) $\displaystyle
s_{i}s_{i+1}s_{i}$ $\displaystyle=s_{i+1}s_{i}s_{i+1},\mbox{ for }|i-j|=1.$
(3)

The second relation, labeled (2), is called a commutation relation, while the
third relation, labeled (3), is called a braid relation.

A minimal sequence of generators that produces $\sigma\in\mathfrak{S}_{n}$ is
called a reduced decomposition. For example, in $\mathfrak{S}_{5}$, the
permutation $\sigma=[42315]$ can be written as the product of length 5:
$s_{1}s_{2}s_{3}s_{2}s_{1}=(1~{}2)(2~{}3)(3~{}4)(2~{}3)(1~{}2)$. For a
permutation $\sigma$, we say that $s_{j}$ is in the support of $\sigma$ if
$s_{j}$ is a present in a reduced decomposition of $\sigma$. For example,
$s_{1}$ is in the support of $[42315]$.

For simplicity, we often write $\sigma$ as a reduced word created from the
indices of a reduced decomposition of $\sigma$. In the previous example, we
would produce the reduced word 12321.

Once we have a reduced word, we wish to find all reduced words for $\sigma$.
We denote the set of all reduced words as $\mathcal{R}(\sigma)$ The letters of
these words obey commutation relations and braid relations. These relations
between reduced words, structures found in the sets $\mathcal{R}(\sigma)$ and
the congruence classes they produce, have been studied extensively [9, 12,
15]. As the sets become large, they become harder to study simply as sets. In
the previous example, there are six reduced words for $\sigma$. This is why we
create graphs of sets of reduced words. For example,

Figure 1 shows the graph $G([42315])$.

$12321$$13231$$31231$$13213$$31213$$32123$$G([42315])=$ Figure 1. The graph
$G([42315])$, where solid edges denote commutation relations, and dashed edges
denote braid relations.

Studying properties of graphs of sets of reduced words is a way to further
understand the structure of $\mathcal{R}(\sigma)$. For example, if you are
interested in better understanding the congruence classes in
$\mathcal{R}(\sigma)$ produced by the braid and commutation relations, the
graphs are a good place to start. In Figure 1, you can see the braid classes,
$\mathcal{B}(\sigma)$, by deleting the solid edges and studying the remaining
connected components.

Our motivating question is as follows: is there an upper bound on the ratio
$|\mathcal{B}(\sigma)|/|\mathcal{R}(\sigma)|$ for arbitrary $\sigma$?

As we pursued an answer to this question, we looked for results that would
allow us to break our graphs into smaller pieces. This led to the development
of new families of subgraphs for $G(\sigma)$, new methods of breaking $\sigma$
into smaller pieces based on its descent set, and bounds for the ratio for
certain classes of permutations.

In Section 2, we give the standard definitions related to
$\mathcal{R}(\sigma)$, the weak order lattice, existing work on the size of
$\mathcal{R}(\sigma)$, and properties of $G(\sigma)$ that we use throughout
the paper. In Section 3, we provide new definitions for when we will call two
permutations $\sigma$ and $\tau$ equivalent, as well as new notation for
specific families of equivalent permutations. Our results include the
following:

  1. (1)

In Section 4:

    1. (a)

We create a subgraph partition of $G(\sigma)$ into the subgraphs related to
$\sigma s_{i}$, for $i\in~{}\text{Des}(\sigma)$, (Theorem 4.4).

    2. (b)

We produce new recursive formulas for the number of braid and commutation
edges in $G(\sigma)$, (Corollaries 4.9 and 4.11).

  2. (2)

In Section 5:

    1. (a)

We provide results on writing reduced decompositions of $\sigma$ given
consecutive elements in $\text{Des}(\sigma)$ (Lemma 5.2).

    2. (b)

We characterization for the permutations with a fixed descent set with minimal
length (Theorem 5.3, Corollary 5.4).

  3. (3)

In Section 6:

    1. (a)

We create a partition of $V(G(\sigma))$ into subsets related to
$\tau^{-1}\sigma$, where $\tau\leq_{W}\sigma$, and $\tau^{-1}\sigma$ has a
descent set containing only consecutive elements, (Theorem 6.5).

    2. (b)

We provide characterizations for when these graphs have “nice” structures
(Corollary 6.9).

  4. (4)

In Section 7:

    1. (a)

We discuss the motivating problem that led to these families of subgraphs.

    2. (b)

We prove bounds for the ratio $|\mathcal{B}(\sigma)|/|\mathcal{R}(\sigma)|$ in
the special case where $\sigma$ is the longest permutation, $w_{0}$ (Theorem
7.3).

    3. (c)

We prove cases of the motivating problem using the subgraph structures (Lemma
7.4, Theorem 7.5).

We conclude in Section 8 with a discussion of future directions for this
research.

##  2\. Preliminaries

In Definition 1.1, we defined the symmetric group, descents, and the simple
transpositions.

######  Definition 2.1.

An inversion is any pair in the one line notation of $\sigma$ such that
$\sigma_{i}>\sigma_{j}$ where $i<j$. The number of inversions of $\sigma$ is
the length of $\sigma$, denoted $\ell(\sigma)$.

The identity $e=[1~{}2~{}\ldots~{}n]$ has the shortest length with zero
inversions, while the permutation $w_{0}~{}=~{}[n~{}n-1~{}\ldots 2~{}1]$ has
the maximum length with $\frac{n(n-1)}{2}$ inversions.

In fact, it is known that the length of any reduced decomposition of $\sigma$
be equal to $\ell(\sigma)$. For example, $\sigma=[4~{}2~{}3~{}1~{}5]$ has five
inversions, and as we saw earlier, the length of a reduced decomposition of
$\sigma$ was also five.

######  Definition 2.2.

Let $\sigma=[\sigma_{1}\cdots\sigma_{n}]\in\mathfrak{S}_{n}$. A _descent_
occurs in position $i$ whenever $\sigma_{i}>\sigma_{i+1}$. We denote the set
of all such indices $i$ as $\text{Des}(\sigma)$. An _ascent_ occurs in
position $j$ whenever $\sigma_{j}<\sigma_{j+1}$. We denote the set of all such
indices $j$ as $\text{Asc}(\sigma)$

###  2.1. The weak order

The generating relations for $\mathfrak{S}_{n}$ can also be used to produce
the lattice for the weak order poset of $\mathfrak{S}_{n}$.

######  Definition 2.3.

The right weak order poset is a partial order defined on $\mathfrak{S}_{n}$,
denoted $W(\mathfrak{S}_{n})$. $W(\mathfrak{S}_{n})$ is a bounded lattice for
all $n\geq 2$. The minimal element in this lattice is the identity, while the
maximal element is $w_{0}=[n~{}n-1~{}\ldots 2~{}1]$.

The cover relations are defined on the addition or removal of a single simple
transposition on the right hand side. That is, $\tau\lessdot\sigma$ if and
only if $\tau s_{i}=\sigma$ for some $i\in\text{Des}(\sigma)$. Then
$\ell(\tau)=\ell(\sigma)-1$.

In general, if $\tau\leq\sigma$, then there exists a collection of simple
transpositions such that $\tau s_{i_{1}}\ldots s_{i_{k}}=\sigma$, where
$\ell(\tau)=\ell(\sigma)-k$.

For $\sigma\in\mathfrak{S}_{n}$, the set $\text{Des}(\sigma)$ gives us all the
elements that $\sigma$ covers in $W(\mathfrak{S}_{n})$. That is, the set of
all elements covered by a permutation $\sigma$ is $\\{\sigma s_{i}\mid
i\in\text{Des}(\sigma)\\}$.

Much work has been done on subposet structures in this lattice. For example,
the number of 4-cycles in $W(\mathfrak{S}_{n})$ is known (OEIS A317487). In
Figure 2, we have the weak order of $\mathfrak{S}_{4}$, with one such 4-cycle
highlighted.

Figure 2.  The right weak order lattice for $\mathfrak{S}_{4}$.

Similarly, the number of 6-cycles in $W(\mathfrak{S}_{n})$ is well known (OEIS
A317486). These results are unsurprising, as a 4-cycle is produced whenever
$i,j\in\text{Des}(\sigma)$ are such that $|i-j|>$, and a 6-cycle is produced
whenever $i,i+1\in\text{Des}(\sigma)$.

In [16], Tenner uses poset intervals to discuss properties of permutations and
the related subposets in $W(\mathfrak{S}_{n})$. For example,

######  Theorem 2.4 ([16], Corollary 4.4).

Let $[v,w]$ be in interval in the weak order. Then $[v,w]$ is a Boolean poset
if and only if $v^{-1}w$ is equal to a product of commuting generators.

###  2.2. Sets of reduced words

The following recursions are well known results for sets of reduced words and
braid classes.

######  Theorem 2.5.

For $\sigma\in\mathfrak{S}_{n}$,

$|\mathcal{R}(\sigma)|=\sum_{i\in\text{Des}(\sigma)}|\mathcal{R}(\sigma
s_{i})|.$

######  Theorem 2.6.

For $\sigma\in\mathfrak{S}_{n}$,

$|\mathcal{B}(\sigma)|=\left(\sum_{i\in\text{Des}(\sigma)}|\mathcal{B}(\sigma
s_{i})|\right)-\sum_{i,i+1\in\text{Des}(\sigma)}|\mathcal{B}(\sigma
s_{i}s_{i+1}s_{i})|.$

There is a similar recursion for $|\mathcal{C}(\sigma)|$ due to Elnitsky [6],
but we do not use that result in this paper.

Additional work has been done by Stanley [12] which relates the size of
$R(\sigma)$ to the number of standard Young tableaux of a certain size.

######  Theorem 2.7 ([12], Corollary 3.1).

Let $\sigma\in\mathfrak{S}_{n}$. Then there exist integers $a_{\lambda}\geq 0$
such that

$|R(\sigma)|=\sum_{\lambda\vdash\ell(\sigma)}a_{\lambda}f^{\lambda}$

If $\sigma$ is _vexillary_ , that is, 2143 pattern avoiding, there is a
$\lambda\vdash\ell(\sigma)$ such that

$|R(\sigma)|=f^{\lambda}$

The following result from Fishel, Milićević, Patrias, and Tenner is used
repeatedly in Section 7, as it gives a relationship between
$\mathcal{R}(\sigma)$ and the sets of congruence classes.

######  Theorem 2.8 ([7], Theorem 3.6).

For any permutation $\sigma$,

$|\mathcal{B}(\sigma)|+|\mathcal{C}(\sigma)|-1\leq|\mathcal{R}(\sigma)|\leq|\mathcal{B}(\sigma)|\cdot|\mathcal{C}(\sigma)|.$

This theorem is what allows us to form Conjectures 7.1 and 7.2, and is used
throughout the proof of Lemma 7.4 and Theorem 7.5.

###  2.3. Graphs of sets of reduced words

First, we give the formal definition of the graph $G(\sigma)$.

######  Definition 2.9.

Let $\sigma\in\mathfrak{S}_{n}$. We produce an undirected graph whose vertex
set is $\mathcal{R}(\sigma)$. If two words are associated by commutation
moves, we give a solid edge in the graph, and if they are associated by braid
moves, we give a dashed edge. We call this graph $G(\sigma)$.

These edges give us straight forward methods of seeing the commutation and
braid classes in the set $\mathcal{R}(\sigma)$.

######  Definition 2.10.

Let $r_{1},r_{2}\in\mathcal{R}(\sigma)$ for some $\sigma\in\mathfrak{S}_{n}$.
We say that $r_{1}$ and $r_{2}$ are in the same commutation class if we can
perform a series of commutation moves on $r_{1}$ to produce $r_{2}$, and vice
versa. We denote the collection of commutation classes of $\sigma$ as
$\mathcal{C}(\sigma)$. Similarly, we say that $r_{1}$ and $r_{2}$ are in the
same braid class if we can perform a series of braid moves on $r_{1}$ to
produce $r_{2}$, and vice versa. We denote the collection of braid classes of
$\sigma$ as $\mathcal{B}(\sigma)$.

We are also interested in graphs constructed from these congruence classes, so
we need some notation for those as well.

######  Definition 2.11.

Let $\sigma\in\mathfrak{S}_{n}$, and consider $G(\sigma)$.

  1. (1)

The graph $G^{\prime}_{\mathcal{B}}(\sigma)$ is defined on the vertex set
$V(G(\sigma))$ and the edge set, denoted $E_{\mathcal{B}}$, is formed from the
braid edges of $G(\sigma)$.

  2. (2)

The graph $G^{\prime}_{\mathcal{C}}(\sigma)$ is defined on the vertex set
$V(G(\sigma))$ and the edge set, denoted $E_{\mathcal{C}}$, is formed from the
commutation edges of $G(\sigma)$.

Note that these are not the same as the traditional congruence class graphs,
where the vertices are the classes, which are formed from graph theoretic
contraction and deletion procedures.

The following result from Reiner gives a relationship between the number of
braid edges in $G(\sigma)$ and the size of the set $\mathcal{R}(\sigma)$.

######  Theorem 2.12 ([8], Theorem 1).

Let $d_{\mathcal{B}}(v)$ be the number of braid edges incident to the vertex
$v$ in $G(\sigma)$. For $\sigma=w_{0}\in\mathfrak{S}_{n}$,

$\sum_{v\in G(\sigma)}d_{\mathcal{B}}(v)=|\mathcal{R}(\sigma)|.$

Theorem 2.12 was used by Tenner in [15] to find the average number of
commutation edges incident to any vertex in $G(w_{0})$. And Schilling et al.
[11] used this result to find the average number of braid edges that are
incident to the connected components in $G(w_{0})$ once the braid edges are
deleted. We use this result to provide bounds on the number of braid edges in
$G(\sigma)$ for more general classes of permutations.

##  3\. New notation related to equivalence of graphs

Throughout the paper, we look at isomorphic graphs that are produced by
distinct permutations. We characterize these permutations as being equivalent.

######  Definition 3.1.

Let $\sigma,\tau\in\mathfrak{S}_{n}$ be such that $\ell(\sigma)=\ell(\tau)=l$.
Let $s_{i_{1}}s_{i_{2}}\ldots s_{i_{l}}$ be a reduced decomposition of
$\sigma$. We say that $\sigma$ and $\tau$ are equivalent if there exists a
reduced decomposition of $\tau$, $s_{j_{1}}s_{j_{2}}\ldots s_{j_{l}}$ such
that $i_{a}-i_{a+1}=j_{a}-j_{a+1}$ for all $1\leq a<l$. The existence of one
such pair of matched decompositions means that there is a way to match both
sets of reduced words with each other, and that this equivalence is on the
sets of reduced words for the two permutations.

For example, $\tau=[321456]$ and $\sigma=[123654]$ are equivalent permutations
because we can match 5 with 2 and 4 with 1 in order to get a matching between
the reduced decompositions $s_{2}s_{1}s_{2}$ and $s_{5}s_{4}s_{5}$. This also
extends to the other elements in $\mathcal{R}(\tau)$ and
$\mathcal{R}(\sigma)$. Alternately, we can see that they are equivalent
permutations by viewing their graphs in Figure 3.

$121$$212$$454$$545$ Figure 3. The graphs of $G([321456])$ and $G([123654])$.

We are particularly interested in the longest element in $\mathfrak{S}_{n}$,
and the family of permutations that are equivalent to the longest elements in
some $\mathfrak{S}_{k}$. We define this family of permutations next.

######  Definition 3.2.

Let $w_{0}^{(k,i)}$ be defined as follows

$w_{0}^{(k,i)}=\left(\begin{array}[]{cccccccccc}1&\ldots&i-1&i&i+1&\ldots&i+k-1&i+k&\ldots
n\\\ 1&\ldots&i-1&i+k-1&i+k-2&\ldots&i&i+k&\ldots n\end{array}\right)$

Note that $w_{0}^{(k,i)}\in\mathfrak{S}_{n}$ is equivalent to $w_{0}$ in
$\mathfrak{S}_{k}$, where $k\leq n$. We are allowed to say these are
equivalent in $\mathfrak{S}_{n}$ because $\mathfrak{S}_{k}$ is a subgroup of
$\mathfrak{S}_{n}$ for all $2\leq k\leq n$. We also note that $s_{i}$ is the
transposition with the smallest index in the reduced decomposition for
$w_{0}^{(k,i)}$. This tells us that the descent set is
$\\{i,i+1\ldots,i+k-2\\}$, which we sometimes refer to using the interval
notation $[i,i+k-2]$.

For example, $s_{1}s_{2}s_{1}\in\mathfrak{S}_{6}$ and
$s_{4}s_{5}s_{4}\in\mathfrak{S}_{6}$ are both equivalent to
$w_{0}\in\mathfrak{S}_{3}$, but we would write them as

$w_{0}^{(3,1)}=[321456],\mbox{ and }w_{0}^{(3,4)}=[123654].$

Much of our work relies on $\sigma$ and $\sigma s_{i}$ for
$i\in\text{Des}(\sigma)$. To conclude this section, we discuss when one of
these permutations is covered by, or equivalent to, $w_{0}^{(k,i)}$.

######  Proposition 3.3.

Let $\sigma\in\mathfrak{S}_{n}$ be such that $\sigma$ is not equivalent to a
$w_{0}^{(k,i)}$, for $k>2$. Further suppose that it is not covered by a
permutation equivalent to $w_{0}^{(k,i)}$ for any $i$. The permutations
covered by $\sigma$ are $\\{\sigma s_{j}\mid j\in\text{Des}(\sigma)\\}$. There
exists $k,i$ such that $\sigma s_{j}$ is equivalent to $w_{0}^{(k,i)}$ for at
most one $j$.

###### Proof.

This comes from the descent sets for each $\sigma s_{j}$, and the lattice
structure of $W(\mathfrak{S}_{n})$. We consider $\sigma s_{x}$ and $\sigma
s_{y}$ for $x,y\in\text{Des}(\sigma)$. Let $\ell(\sigma)=l$.

Suppose that $\sigma s_{x}=w_{0}^{(k_{x},i)}$ and $\sigma
s_{y}=w_{0}^{(k_{y},j)}$. Since these permutations each have the same length,
$l-1$, $k_{x}=k_{y}$ while the minimum index $i$ and $j$ could be distinct.

Consider $\sigma s_{x}$ first. We can draw part of the weak order lattice
containing $\sigma$ and $\sigma s_{x}$ in order to get an idea of what the
descent sets must look like.

$\sigma$$\sigma s_{x}=w_{0}^{(k,i)}$$\sigma
s_{y}=w_{0}^{(k,j)}$$w_{0}^{(k,i)}s_{i+k-2}$$\ldots$$w_{0}^{(k,i)}s_{i}$
Figure 4. Proposition 3.3 subposet

We write $\text{Des}(\sigma s_{x})=\\{i,i+1,\ldots,i+k-2\\}$. Let
$A\subset[n]$ such that $x\in A$, $A\cap[i,i+k-2]=\emptyset$ and
$\\{i-1,i+k-1\\}\subset A$. We note that $x$ could be $i-1$ or $i+k-1$, and we
could end up with $\text{Des}(\sigma)=[i,i+k-3]\cup\\{x\\}$, or
$\text{Des}(\sigma)=[i+1,i+k-2]\cup\\{x\\}$. However, in both of these cases,
$y\in\text{Des}(\sigma)$ would be such that $\text{Des}(\sigma
s_{y})\neq\text{Des}(w_{0}^{(k,i)})$ for any $i,k$.

Since $\text{Des}(\sigma s_{y})$ only contains consecutive elements, this
tells us two things: (i) $x$ must be either $i-1$ or $i+k-1$, and (ii)
$\text{Des}(\sigma)=\text{Des}(\sigma s_{x})\cup\\{x\\}$.

Similar reasoning tells us that in order for $\text{Des}(\sigma s_{x})$ to
only contain consecutive elements then $y$ must either equal $x$, or one of
the following: if $x=i+k-1$, then $y=i$ and if $x=i-1$, then $y=i+k-2$.
Without loss of generality, consider
$\text{Des}(\sigma)=\\{x=i-1,i,i+1,\ldots,i+(k-2)=y\\}$.

Then since we claim both $\sigma s_{x}$ and $\sigma s_{y}$ are equivalent to
$w_{0}^{(k,j)}$ for some $j$, we have that $\sigma s_{x}=w_{0}^{(k,i)}$ and
$\sigma s_{y}=w_{0}^{(k,i-1)}$. This also means we know two different reduced
decompositions for $\sigma$ using decompositions for the $w_{0}^{(k,j)}$’s
that we discussed in Chapter 1: $(s_{x}s_{i}\ldots s_{i+k-3}\ldots
s_{x}s_{i}s_{x})s_{y}$ and $(s_{i}s_{i+1}\ldots s_{y}\ldots
s_{i}s_{i+1}s_{i})s_{x}$.

But this means

$\sigma=\left(\begin{array}[]{cccccccccc}1&\ldots&i-1&i&i+1&\ldots&i+k-2&i+k-1&\ldots
n\\\ 1&\ldots&i+k-1&i+k-3&i+k-4&\ldots&i-1&i+k-2&\ldots n\end{array}\right),$

and

$\sigma=\left(\begin{array}[]{cccccccccc}1&\ldots&i-1&i&i+1&\ldots&i+k-2&i+k-1&\ldots
n\\\ 1&\ldots&i&i+k-1&i+k-2&\ldots&i+1&i-1&\ldots n\end{array}\right),$

which are not equivalent permutations. In fact, the only way we could have
both reduced decompositions for $\sigma$ is if $k=2$, and $\sigma=s_{x}s_{y}$.
Since we assume $k>2$, $\sigma$ can only cover at most one permutation
equivalent to $w_{0}^{(k,i)}$ for some $i$. ∎

##  4\. Subgraphs using the Descent set of a permutation

The main motivation for this section is the graph seen in Figure 5.

$(12132)1$$(12312)1$$(12321)2$$(13231)2$$(13213)2$$(31231)2$$(31213)2$$(32123)2$$(32132)3$$(32312)3$$(21232)1$$(21323)1$$(23123)1$$(21321)3$$(23121)3$$(23212)3$
Figure 5. The graph $G(w_{0})$ for $w_{0}\in\mathfrak{S}_{4}$.

This graph is large, and this is only in $\mathfrak{S}_{4}$. In this section,
we produce a family of induced subgraphs that allows us to partition
$G(w_{0})$ into smaller parts, which is useful when $n>4$.

######  Definition 4.1.

An induced subgraph $H$ of $G$ is such that $V(H)\subset V(G)$ and $E(H)$ is
defined as the subset of $E(G)$ that have both end points in $V(H)$. We denote
this subgraph relation in the standard way: $H\leq G$.

######  Proposition 4.2.

Let $\sigma,\tau\in\mathfrak{S}_{n}$, $n\geq 2$ such that $\tau\lessdot\sigma$
in the weak order lattice. Then $G(\tau)$ is an induced subgraph of
$G(\sigma)$.

###### Proof.

If $\tau\lessdot\sigma$ in the weak order lattice, then there is some
$i\in\text{Des}(\sigma)$ such that $\tau s_{i}=\sigma$. Let
$t\in\mathcal{R}(\tau)$. Then $ti\in\mathcal{R}(\sigma)$. This is how we
consider $\mathcal{R}(\tau)$ as a subset of $\mathcal{R}(\sigma)$.

In fact, this is also how we can consider $G(\tau)$ as a subgraph of
$G(\sigma)$. If there is a commutation edge from $t_{1}$ to $t_{2}$ in
$G(\tau)$, then there is a commutation edge from $t_{1}i$ to $t_{2}i$ in
$G(\sigma)$. The same applies for braid edges in $G(\tau)$. Thus we can map
edges from $G(\tau)$ into $G(\sigma)$.

Additionally, we can look at $V(G(\tau))$ as a subset of $V(G(\sigma))$, and
consider an edge in $G(\sigma)$ incident to two vertices contained in
$V(G(\tau))$. This edge must already be contained in $G(\tau)$, because any
commutation or braid move is happening between words in $\mathcal{R}(\tau)$,
since these vertices are of the form $\tau_{1}s_{i}$ and $\tau_{2}s_{i}$.

Therefore, $G(\tau)$ is an induced subgraph of $G(\sigma)$. ∎

######  Corollary 4.3.

Let $\sigma,\tau\in\mathfrak{S}_{n}$, $n\geq 2$ such that $\tau\leq\sigma$ in
the weak order lattice. Then,

  1. (1)

$G(\tau)$ is an induced subgraph of $G(\sigma)$,

  2. (2)

$G(\tau)$ is an induced subgraph of $G(w_{0})$.

###### Proof.

Consider the chain in the weak order lattice:

$\tau\lessdot\tau_{1}\lessdot\tau_{2}\lessdot\ldots\lessdot\tau_{k}\lessdot\sigma,$

where each element in the chain covers the previous element. We know such a
chain exists because $\tau\leq\sigma$. Note that every element in
$W(\mathfrak{S}_{n})$ is comparable to $w_{0}$, so for any $\tau$, we could
set $\sigma=w_{0}$.

From the previous proposition, we can construct the following chain of induced
subgraphs:

$G(\tau)\leq G(\tau_{1})\leq G(\tau_{2})\leq\ldots\leq G(\tau_{k})\leq
G(\sigma).$

So we have that $G(\tau)\leq G(\sigma)$, as desired. ∎

We wish to combine our previous results into a method of partitioning the
vertex set of $G(\sigma)$.

######  Theorem 4.4.

Let $\sigma\in\mathfrak{S}_{n}$. Then the set $V(G(\sigma))$ may be
partitioned into disjoint subsets of the form $V(G(\sigma s_{i}))$ for
$i\in\text{Des}(\sigma s_{i})$.

###### Proof.

As noted in Theorem 2.5, the set $\mathcal{R}(\sigma)$ can be partitioned into
$\mathcal{R}(\sigma s_{i})$ for $i\in\text{Des}(\sigma)$. We simply apply the
labeling of the subgraphs $G(\sigma s_{i})$ to the vertex set of $G(\sigma)$
as in Proposition 4.2, and we have our partition of the vertex set. ∎

Using this partition of subgraphs, we wish to study the degree of vertices in
$G(\sigma)$.

######  Definition 4.5.

Let $\sigma\in\mathfrak{S}_{n}$. For $G(\sigma)$, we define
$d_{\mathcal{B}}(v)$ to be the braid edge degree of a vertex $v$. That is,
$d_{\mathcal{B}}(v)$ counts the number of braid edges incident to $v$ in the
graph $G(\sigma)$.

Similarly, we define $d_{\mathcal{C}}(v)$ to be the commutation edge degree of
a vertex $v$. That is, $d_{\mathcal{C}}(v)$ counts the number of commutation
edges incident to $v$ in the graph $G(\sigma)$.

######  Example 4.6.

Consider again $w_{0}\in\mathfrak{S}_{4}$. The graph $G(w_{0})$ has been drawn
in Figure 6, and the vertices of $G(w_{0})$ have been partitioned.

$(12132)1$$(12312)1$$(12321)2$$(13231)2$$(13213)2$$(31231)2$$(31213)2$$(32123)2$$(32132)3$$(32312)3$$(21232)1$$(21323)1$$(23123)1$$(21321)3$$(23121)3$$(23212)3$
Figure 6. The graph $G(w_{0})$ for $w_{0}\in\mathfrak{S}_{4}$, with induced
subgraphs highlighted.

The induced subgraphs highlighted in different colors: $G(w_{0}s_{1})$ is
drawn black with the 1 in the right most position in the reduced words,
$G(w_{0}s_{2})$ in blue with a 2 in the right most position, and
$G(w_{0}s_{3})$ in red with a three in the right most position. There are also
four edges in green that only appear in $G(w_{0})$ connecting those subgraphs.

The edges between subgraphs are what we are particularly interested in. Note
that the braid edge degree of the vertex $\overline{u}=(32132)3$ is different
depending on whether we view it as $u\in V(G([4312]))$ or $\overline{u}=u3\in
V(G(w_{0}))$. From this observation, we can now produce results for the braid
edge degree of a vertex in $G(\sigma)$.

######  Proposition 4.7.

Let $\sigma\in\mathfrak{S}_{n}$, and $i,j\in\text{Des}(\sigma)$. Suppose that
$ws_{i},us_{j}\in\mathcal{R}(\sigma)$, where $w\in\mathcal{R}(\alpha)$,
$u\in\mathcal{R}(\beta)$ and $\alpha,\beta\lessdot\sigma$. Suppose that
$(ws_{i})-(us_{j})$ is an edge in the graph $G(\sigma)$.

  1. (1)

If $u\neq w$, but $i=j$, then $\alpha=\beta$ and the edge appears in the
induced subgraph $G(\alpha)$.

  2. (2)

If $i\neq j$, then the vertices appear in two disjoint subgraphs of
$G(\sigma)$, and so this edge is not properly contained in any induced
subgraph.

###### Proof.

Case 1 was already proven in Proposition 4.2. For Case 2, if $i\neq j$, then
$ws_{i}$ appears in $\mathcal{R}(\sigma s_{i})$, which is disjoint from
$\mathcal{R}(\sigma s_{j})$ which contains $us_{j}$. This means that the two
vertices appear in disjoint induced subgraphs. Thus the edge
$(ws_{i})-(us_{j})$ connects the two subgraphs in $G(\sigma)$, but is not
properly contained in either one. ∎

Now that we have a better idea of what edges appear only in $G(\sigma)$ and
not in any of the induced subgraphs, we have the following proposition:

######  Proposition 4.8.

Let $\sigma,\tau\in\mathfrak{S}_{n}$, $n\geq 2$ such that $\tau\lessdot\sigma$
in the weak order lattice. Suppose that $\tau s_{i}=\sigma$, where
$i\in\text{Des}(\sigma)$.

  1. (1)

If $i-1,~{}i,~{}i+1\in\text{Des}(\sigma)$, then there are $|\mathcal{R}(\sigma
s_{i}s_{i+1}s_{i})|+|\mathcal{R}(\sigma s_{i}s_{i-1}s_{i})|$ braid edges
incident to the vertices of $G(\tau)$ that are not contained in the induced
subgraph $G(\tau)$.

  2. (2)

If only $i,~{}i+1\in\text{Des}(\sigma)$, (or $i-1,i\in\text{Des}(\sigma)$),
then there are $|\mathcal{R}(\sigma s_{i}s_{i+1}s_{i})|$ braid edges incident
to the vertices of $G(\tau)$ that are not contained in the induced subgraph
$G(\tau)$.

  3. (3)

If neither of these cases is true, then the only braid edges incident to the
vertices of $G(\tau)$ are the braid edges that are incident to two vertices
from $G(\tau)$.

###### Proof.

Consider $\sigma,\tau\in\mathfrak{S}_{n}$ such that $\tau\lessdot\sigma$, and
suppose that $i,i+1\in\text{Des}(\sigma)$ and $\sigma s_{i}=\tau$.

Note that since $i,i+1\in\text{Des}(\sigma)$, then $\sigma=[a_{1}\ldots
a_{n}]$ is such that $a_{i}>a_{i+1}>a_{i+2}$. We can consider $\sigma
s_{i}=[\ldots a_{i+1}a_{i}a_{i+2}\ldots]$, and $\sigma s_{i+1}=[\ldots
a_{i}a_{i+2}a_{i+1}\ldots]$. We note that $i\in\text{Des}(\sigma s_{i+1})$ and
$i+1\in\text{Des}(\sigma s_{i})$. We can continue in this manner to get the
portion of weak order lattice in Figure 7.

$\sigma$$\sigma s_{i}$$\sigma s_{i+1}$$\sigma s_{i}s_{i+1}$$\sigma
s_{i}s_{i+1}s_{i}$$\sigma s_{i+1}s_{i}$ Figure 7. When
$i,i+1\in\text{Des}(\sigma)$, we have this subposet in $W(\mathfrak{S}_{n})$

Let $\alpha=\sigma s_{i}s_{i+1}s_{i}$ so that $\sigma=\alpha
s_{i}s_{i+1}s_{i}$. Equivalently, we have that $\sigma=\alpha
s_{i+1}s_{i}s_{i+1}$.

We want to be able to count the number of reduced words of $\sigma$ that have
a braid move in those last three positions that use the letters $i$ and $i+1$.
This means we really need to count the number of ways we can write $\alpha$.
And in fact, there are $|\mathcal{R}(\sigma s_{i}s_{i+1}s_{i})|$ ways to write
$\alpha$.

We note that all vertices that end in the letters $i,~{}i+1,~{}i$ are
contained in the subgraph $G(\sigma s_{i})$, where $\tau=\sigma s_{i}$. All
vertices that end in the letters $i+1,~{}i,~{}i+1$ are contained in the
subgraph $G(\sigma s_{i+1})$. Then the number of braid edges between these
subgraphs are equal to $|\mathcal{R}(\sigma s_{i}s_{i+1}s_{i})|$.

The same reasoning allows us to conclude that if
$i-1,~{}i,~{}i+1\in\text{Des}(\sigma)$, there are $|\mathcal{R}(\sigma
s_{i}s_{i+1}s_{i})|+|\mathcal{R}(\sigma s_{i}s_{i-1}s_{i})|$ “new” braid edges
incident to vertices in $G(\tau)$.

Similarly, if we cannot write $\sigma=\alpha s_{i}s_{i\pm 1}s_{i}$ for this
particular $i$, then the only possible braid edges that can be incident to the
vertices of $G(\tau)$ must be fully contained in the induced subgraph. ∎

The following recursive formula is an immediate consequence of Proposition
4.8.

######  Corollary 4.9.

Let $\sigma\in\mathfrak{S}_{n}$. Then

$\sum_{v\in
G(\sigma)}d_{\mathcal{B}}(v)=\left(\sum_{i\in\text{Des}(\sigma)}\sum_{u\in
G(\sigma
s_{i})}d_{\mathcal{B}}(u)\right)+2\cdot\sum_{i,i+1\in\text{Des}(\sigma)}|\mathcal{R}(\sigma
s_{i}s_{i+1}s_{i})|,$

where we consider $d_{\mathcal{B}}(u)$ in $G(\sigma s_{i})$ on the right hand
side, and $\overline{u}=ui\in G(\sigma)$ on the left hand side.

This is a brand new way to count the number of braid edges in a graph of a set
of reduced words. Now we have methods of breaking $G(\sigma)$ into subgraphs,
and a way to count the braid edges in $G(\sigma)$. Since we want to understand
the congruence classes in $\mathcal{B}(\sigma)$, this is a step closer to that
goal.

Because the arguments are very similar, we also prove a result that allows us
to count the number of commutation edges in $G(\sigma)$.

######  Proposition 4.10.

Let $\sigma,\tau\in\mathfrak{S}_{n}$, $n\geq 2$ such that $\tau\lessdot\sigma$
in the weak order lattice. Suppose that $\tau s_{i}=\sigma$, where
$i\in\text{Des}(\sigma)$. Let $I_{i}=\\{j\mid j\in\text{Des}(\sigma)\mbox{ and
}|j-i|>1\\}$.

  1. (1)

If $I_{i}\neq\emptyset$, then there are $\sum_{j\in I_{i}}|\mathcal{R}(\sigma
s_{i}s_{j})|$ commutation edges incident to the vertices of $G(\tau)$ that are
not contained in the induced subgraph.

  2. (2)

If $I_{i}=\emptyset$, then the only commutation edges incident to the vertices
of $G(\tau)$ are the commutation edges that are incident to two vertices from
$G(\tau)$.

###### Proof.

Consider $\sigma,\tau\in\mathfrak{S}_{n}$ such that $\tau\lessdot\sigma$.
Suppose that $i,j\in\text{Des}(\sigma)$ are such that $|i-j|>1$, and $\sigma
s_{i}=\tau$.

Since $i,j\in\text{Des}(\sigma)$, and letters $i$ and $j$ commute with each
other, there exist reduced decompositions of $\sigma$ such that $\sigma=\alpha
s_{i}s_{j}$ and $\sigma=\alpha s_{j}s_{i}$. We want to be able to count the
number of reduced words of $\sigma$ that have a commutation move in those last
two positions that use the letters $i$ and $j$. This means we really need to
count the number of ways we can write $\alpha$. There are $|\mathcal{R}(\sigma
s_{i}s_{j})|$ ways to write $\alpha$.

We note that all vertices that end in the letters $j~{}i$ are contained in the
subgraph $G(\sigma s_{i})$, where $\tau=\sigma s_{i}$. All vertices that end
in the letters $i~{}j$ are contained in the subgraph $G(\sigma s_{j})$. Then
the number of commutation edges between these subgraphs are equal to
$|\mathcal{R}(\sigma s_{i}s_{j})|$.

The same reasoning allows us to conclude that for all $k\in I_{i}$, then there
are $|\mathcal{R}(\sigma s_{k}s_{i})|$ “new” commutation edges incident to
vertices in $G(\tau)$.

Similarly, if $I_{i}=\emptyset$ then we cannot write $\sigma=\beta
s_{j}s_{i}=\beta s_{i}s_{j}$ for this particular $i$, then the only possible
commutation edges that can be incident to $G(\tau)$ must be fully contained in
the induced subgraph. ∎

The following is an immediate consequence of Proposition 4.10.

######  Corollary 4.11.

Let $\sigma\in\mathfrak{S}_{n}$. Then if $d_{\mathcal{C}}(v)$ counts the
number of commutation edges incident to $v$ in $G(\sigma)$,

$\sum_{v\in
G(\sigma)}d_{\mathcal{C}}(v)=\left(\sum_{i\in\text{Des}(\sigma)}\sum_{u\in
G(\sigma
s_{i})}d_{\mathcal{C}}(u)\right)+2\cdot\sum_{i,j\in\text{Des}(\sigma)~{}i-j>1}|\mathcal{R}(\sigma
s_{j}s_{i})|,$

where we consider $d_{\mathcal{B}}(u)$ in $G(\sigma s_{i})$ on the right hand
side, and $\overline{u}=ui\in G(\sigma)$ on the left hand side.

Note that the subgraphs in this section have been, in many ways, the most
natural method of partitioning our graphs into subgraphs. The related edge
degree recursions are certainly useful, but as we see in Section 7, they only
get us so far when we consider our main motivating problem.

However, as the results in this section are brand new tools, we are interested
in what applications they can have to other problems related to
$\mathcal{R}(\sigma)$ and $W(\mathfrak{S}_{n})$.

##  5\. Writing reduced words based on the descent set

As we worked on various examples proofs in the previous section, we began
asking questions about how we were generating the set $\mathcal{R}(\sigma)$.
If we had a single reduced word for $\sigma$, what shortcuts we were taking to
generate these sets quickly, and what other types of sub-structures did we
notice?

######  Example 5.1.

Consider the permutation $\sigma=[2431]=s_{1}s_{2}s_{3}s_{2}$ with descent set
$\text{Des}(\sigma)=\\{2,3\\}$.

$1232$$1323$$3123$ Figure 8. The graph $G([2431])$

We note that the braid edge itself is a copy of $G([1432])$, which is
$w_{0}^{(3,2)}$, and has the same descent set as $\sigma$. Starting with the
words 1323 and 1232, we attempt to move the letter 1 to the right. We note
that after moving the letter 1, we do not have a second full copy of
$G([1432])$. We would need both the vertices 2132 and 3123, as well as a braid
edge between them. There are two problems with this: there is no braid move
between those reduced words, and 2132 is not a reduced word of $\sigma$.

Next we consider $\sigma=[32154]=s_{4}s_{1}s_{2}s_{1}$ with descent set
$\text{Des}(\sigma)=\\{1,2,4\\}$. We have

$4121$$4212$$2412$$1421$$2142$$1241$$2124$$1214$ Figure 9. The graph
$G([32154])$

In this picture, we have four copies of the vertex set of $G([321])$, with 4
sitting in different spots through the reduced words for $121$. We focus on
this permutation because the longest string of consecutive elements in
$\text{Des}(\sigma)$ is the descent set for $w_{0}^{(3,1)}$. As the letter 4
moves through the word from left to right, we have effectively blocked braid
edges from appearing in the middle portion of the graph.

The example in Figure 9, and notation found in [16] leads us to the following
idea: rather than focus on intervals $[\sigma s_{i},\sigma]$ in the weak order
lattice, we can focus on $[\tau,\sigma]$ such that
$\tau^{-1}\sigma=w_{0}^{(k,i)}$, for some $i,k\in\mathbb{N}$.

######  Lemma 5.2.

Let $\sigma\in\mathfrak{S}_{n}$. Suppose that $\text{Des}(\sigma)$ contains a
string of $m$ consecutive elements, with smallest element in the string $i$:
$\\{i,i+1,\ldots,i+m-1\\}$. Then there exists a $u\in\mathfrak{S}_{n}$ such
that $u\leq\sigma$, and $u^{-1}\sigma=w_{0}^{(k,i)}$, for $k=m+1$.

###### Proof.

Let $\sigma=[a_{1}a_{2}\ldots a_{n}]\in\mathfrak{S}_{n}$. We recall that
$i\in\text{Des}(\sigma)$ if and only if $a_{i}>a_{i+1}$. We also recall that
for any $j$, $\sigma s_{j}=[a_{1}a_{2}\ldots a_{j+1}a_{j}\ldots a_{n}]$.

For any element $i\in\text{Des}(\sigma)$, we recall that $s_{i}=w_{0}^{1,i}$.
Suppose that $\\{i,i+1,\ldots i+m-1\\}\subset\text{Des}(\sigma)$ is a string
of consecutive elements where $m\geq 2$. This means that

$a_{i}>a_{i+1}>\ldots>a_{i+m-1}.$

Let $\tau_{\sigma}^{(j,k)}$ be defined as follows:

$\tau_{\sigma}^{(j,k)}:=\sigma s_{j}s_{j+1}\ldots s_{j+k-1}=[a_{1}\ldots
a_{j-1}a_{j+1}\ldots a_{j+k}a_{j}\ldots a_{n}],$

where $\tau_{\sigma}^{(0,0)}=\sigma$, and $\tau_{\sigma}^{(j,1)}=\sigma
s_{j}$.

We note that for the set $\\{i,i+1,\ldots i+m-1\\}\subset\text{Des}(\sigma)$,
if $j=i$ and $k=m$, we have

$\tau_{\sigma}^{(i,m)}=\sigma s_{i}s_{i+1}\ldots s_{i+m-1}=[a_{1}\ldots
a_{i-1}a_{i+1}a_{i+2}\ldots a_{i+m}a_{i}\ldots a_{n}].$

We see that $\\{i,i+1,\ldots
i+m-2\\}\subset\text{Des}(\tau_{\sigma}^{(i,m)})$, while
$i+m-1\notin\text{Des}(\tau_{\sigma}^{(i,m)})$.

Furthermore, $\ell(\tau_{\sigma}^{(i,m)})=\ell(\sigma)-m$. Since
$i\in\text{Des}(\sigma)$, $\ell(\tau_{\sigma}^{(i,1)})=\ell(\sigma)-1$. We
still have $i+1\in\text{Des}(\tau_{\sigma}^{(i,1)})$, and we can see that
$\ell(\tau_{\sigma}^{(i,2)})=\ell(\sigma)-2$. Inductively, this process
continues until we have $\ell(\tau_{\sigma}^{(i,m)})=\ell(\sigma)-m$.

Let $\sigma^{(1)}=\tau_{\sigma}^{(i,m)}$. We now consider

$\tau_{\sigma^{(1)}}^{(i,m-1)}=\sigma^{(1)}s_{i}s_{i+1}\ldots
s_{i+m-2}=[a_{1}\ldots a_{i-1}a_{i+2}\ldots a_{i+m}a_{i+1}a_{i}\ldots a_{n}].$

We note that

$i+m-1,i+m-2\notin\text{Des}(\tau_{\sigma^{(1)}}^{(i,m-1)})\mbox{ and
}\\{i,i+1,\ldots i+m-3\\}\subset\text{Des}(\tau_{\sigma^{(1)}}^{(i,m-1)}).$

We also have
$\ell(\tau_{\sigma^{(1)}}^{(i,m-1)})=\ell(\sigma^{(1)})-(m-1)=\ell(\sigma)-m-(m-1)$
using the same argument on descents as before. Let
$\sigma^{(2)}=\tau_{\sigma^{(1)}}^{(i,m-1)}$.

Inductively, for $1\leq x\leq m-3$, we have that the permutation
$\sigma^{(x+1)}=\tau_{\sigma^{(x)}}^{(i,m-x)}$ is such that

$\sigma^{(x+1)}=\sigma^{(x)}s_{i}s_{i+1}\ldots s_{i+m-(x+1)}=[a_{1}\ldots
a_{i-1}a_{i+x}\ldots a_{i+m}a_{i+x-1}\ldots a_{i+1}a_{i}\ldots a_{n}],$

where $\\{i,\ldots,i+m-(x+2)\\}\subset\text{Des}(\sigma^{(x+1)})$,
$\\{i+m-(x+1),\ldots,i+m-1\\}\cap\text{Des}(\sigma)=\emptyset$, and
$\ell(\sigma^{(x+1)})=\ell(\sigma)-\sum_{b=0}^{m-x}m-b$.

Now consider $\sigma^{(m-2)}=\tau_{\sigma^{(m-3)}}^{(i,m-(m-3))}$:

$\sigma^{(m-2)}=[a_{1}\ldots a_{i-1}a_{i+m-2}a_{i+m-1}a_{i+m}a_{i+m-3}\ldots
a_{i+1}a_{i}\ldots a_{n}].$

From the above one line notation, we see that
$\sigma^{(m)}:=\sigma^{(m-2)}s_{i}s_{i+1}s_{i}$ such that $\\{i,i+1,\ldots
i+m-2\\}\cap\text{Des}(\sigma^{(m)})=\emptyset$. Additionally,

$\ell(\sigma^{(m)})=\left(\ell(\sigma)-\sum_{b=0}^{m-3}m-b\right)-3=\ell(\sigma)-\binom{m+1}{2}.$

Let $u\in\mathcal{R}(\sigma^{(m)})$. Note that if $\sigma^{(m)}$ is the
identity, then $u$ is simply the empty word. In either case, by tracing our
products from $\sigma^{(m)}$ back to $\sigma^{(1)}$, let $v$ be the word

$i(i+1)i~{}(i+2)(i+1)i\ldots(i+k-1)(i+k-2)\ldots(i+1)i.$

We see that $\ell(v)=\binom{m+1}{2}$, and that we can verify that
$v\in\mathcal{R}(w_{0}^{(m+1,i)})$. By construction, we have
$uv\in\mathcal{R}(\sigma)$ as desired. ∎

This result leads us to the following, more general theorem.

######  Theorem 5.3.

Let $\sigma\in\mathfrak{S}_{n}$. Suppose that $\text{Des}(\sigma)$ can be
partitioned into maximal blocks of consecutive entries, $B_{1},B_{2},\ldots
B_{m}$. Let $\min(B_{j})=b_{j}$ for all $1\leq j\leq m$. Then

$\sigma=\tau\prod_{i=1}^{m}w_{0}^{(|b_{j}|+1,b_{j})}$

for some $\tau\leq\sigma$.

###### Proof.

For each block of consecutive descents, we apply Lemma 5.2 to produce

$\sigma=\tau_{1}w_{0}^{(|b_{1}|+1,b_{1})}.$

We apply Lemma 5.2 again to arrive at

$\sigma=\tau_{2}w_{0}^{(|b_{2}|+1,b_{2})}w_{0}^{(|b_{1}|+1,b_{1})}.$

We note that as the descent sets are disjoint, then

$w_{0}^{(|b_{2}|+1,b_{2})}w_{0}^{(|b_{1}|+1,b_{1})}=w_{0}^{(|b_{1}|+1,b_{1})}w_{0}^{(|b_{2}|+1,b_{2})}$

so the order does not matter.

We repeat this process inductively until we have worked our way down the
lattice to $\tau$, and the product

$\sigma=\tau\prod_{i=1}^{m}w_{0}^{(|b_{j}|+1,b_{j})}$

as desired. ∎

Using Theorem 5.3, we have the following classification of the shortest
permutation with a fixed descent set.

######  Corollary 5.4.

Let $\sigma\in\mathfrak{S}_{n}$. Suppose that $\text{Des}(\sigma)$ can be
partitioned into maximal blocks of consecutive entries, $B_{1},B_{2},\ldots
B_{m}$. Then

$\sigma^{\prime}=\prod_{i=1}^{m}w_{0}^{(|b_{j}|+1,b_{j})}$

is the permutation with minimal length such that
$\text{Des}(\sigma^{\prime})=\text{Des}(\sigma)$.

###### Proof.

From Theorem 5.3, we note that for $\text{Des}(\sigma)$, we must have

$\prod_{i=1}^{m}w_{0}^{(|b_{j}|+1,b_{j})}$

as part of a reduced decomposition of $\sigma$. Then $\tau=e$ produces the
permutation with minimal length with this descent set. ∎

##  6\. Shuffles Subgraphs

Using ideas from the previous section, we now discuss how to consider
subgraphs in $G(\sigma)$ that may not be of the form $G(\sigma s_{i})$,
$i\in\text{Des}(\sigma)$.

######  Definition 6.1.

Let $\sigma\in\mathfrak{S}_{n}$ be such that
$[i,i+k-2]\subset\text{Des}(\sigma)$ is a set of consecutive elements. From
Lemma 5.2, we note that there are permutations
$\alpha,\beta\in\mathfrak{S}_{n}$ such that $\beta=w_{0}^{(k,i)}$, and
$u=u_{1}u_{2}\ldots u_{l(\alpha)}\in\mathcal{R}(\alpha)$ and
$v=v_{1}v_{2}\ldots v_{l(\beta)}\in\mathcal{R}(w_{0}^{(k,i)})$ can be
concatenated to produce $uv\in\mathcal{R}(\sigma)$. That is,
$\sigma=\alpha\beta$. In order to distinguish the letters, we color the
letters of $u$ blue, and the letters of $v$ red.

A shuffle of the letters of $uv$ is defined in the following way:

  1. (1)

A commutation or braid move using only the blue letters of $u$, or using only
the red letters of $v$.

  2. (2)

A commutation move using one blue letter $u_{i}$ of $u$ and one red letter
$v_{j}$ of $v$.

  3. (3)

A braid move that uses two blue letters $u_{i}u_{i+1}$ of $u$ and one red
letter $v_{j}$ of $v$, or vice versa.

None of the above shuffle types change the color of the letters. After any
finite sequence of shuffles of any type, we no longer have the word $uv$. We
still refer to each new shuffle as a shuffle of the letters of $uv$.

######  Example 6.2.

Consider $\sigma=[165324]=s_{4}s_{5}s_{2}s_{3}s_{4}s_{2}s_{3}s_{2}$. We can
use Lemma 5.2 to write $45\in\mathcal{R}(\alpha)$,
$234232\in\mathcal{R}(\beta)$, and
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}45}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}234232}\in\mathcal{R}(\sigma)$.

  1. (1)

Using a shuffle of type 1, we have
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}45}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}434234}\in\mathcal{R}(\sigma)$.

  2. (2)

Using a shuffle of type 2, we have
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}5}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}34232}\in\mathcal{R}(\sigma)$.

  3. (3)

Using a shuffle of type 3, we have
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}54}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}534234}\in\mathcal{R}(\sigma)$

We see that for the first type of shuffle, we start with
$u\in\mathcal{R}(\alpha)$ and shuffle letters to get
$a\in\mathcal{R}(\alpha)$. For a fixed pair $a\in\mathcal{R}(\alpha)$ and
$b\in\mathcal{R}(\beta)$, the second type of shuffle commutes where the
letters of $a$ and $b$ sit. The third shuffle type is a mix of blue letters
forming a word $a^{\prime}$, and red letters form a word $b^{\prime}$.
However, $a^{\prime}\notin\mathcal{R}(\alpha)$ and
$b^{\prime}\in\mathcal{R}(\beta)$, which makes the words formed after a
shuffle of type 3 more difficult to discuss.

We know that we can start with any word in $\mathcal{R}(\sigma)$, and generate
the full set by performing all possible commutation and braid moves among the
letters. So we can use the letters of $uv$ to fully generate
$\mathcal{R}(\sigma)$ in the standard way.

The question is whether we can keep track of the letters of
$u\in\mathcal{R}(\alpha)$ and $v\in\mathcal{R}(\beta)$ as we perform the
shuffle process?

######  Lemma 6.3.

Let $\alpha,\beta,\sigma\in\mathfrak{S}_{n}$, with $u\in\mathcal{R}(\alpha)$,
$v\in\mathcal{R}(\beta)$ and $uv\in\mathcal{R}(\sigma)$ as described in Lemma
5.2 and Definition 6.1. We can fully construct $\mathcal{R}(\sigma)$ by
looking at all possible ways that the letters of $uv$ can shuffle through each
other.

###### Proof.

Consider $uv\in\mathcal{R}(\sigma)$, where $u=u_{1}\ldots
u_{l(\alpha)}\in\mathcal{R}(\alpha)$ and $v=v_{1}\ldots
v_{l(\beta)}\in\mathcal{R}(\beta)$. We color all the letters descended from
$u$ blue, and all the letters descended from $v$ red.

Let $w\in\mathcal{R}(\sigma)$ be an arbitrary word that is distinct from $uv$.
We know that there is a finite sequence of commutation and braid moves that
transform $uv$ into $w$. Since $G(\sigma)$ is connected, let us consider this
as a path of $m$ vertices in $G(\sigma)$.

$(uv)-(a_{2})-\cdots-(a_{m-1})-(w)$

To travel from $uv$ to $a_{2}$, we either perform a commutation move or a
braid move of the letters of $uv$. This is a shuffle of the letters of $uv$.

Inductively, each $a_{j}$ in this path has all the letters colored blue and
red, since no shuffle type changes the colors of the letters. We always have
the same number of blue letters and red letters, since none of the shuffles
recolors the letters. Thus, the letters of $w$ is a mix of $\ell(\alpha)$ blue
letters and $\ell(\beta)$ red letters.

Because $w$ was an arbitrary element of $\mathcal{R}(\sigma)$, every element
of the set is formed from a series of shuffles of the letters of $uv$. ∎

Our work on splitting $\sigma$ into pieces $\alpha$ and $\beta$, and shuffling
the letters of their respective reduced words, is similar to permutation
inflations. Permutation inflations are related to grid drawings of
permutations, and use patterns in the one line notation in consecutive spots
to write reduced words. For more information on inflations, we recommend [1]
or [3].

We pursued this new shuffle method rather than the inflations because we could
use our $\alpha$ and $\beta$ construction for any arbitrary permutation,
rather than being restricted to a particular family.

######  Example 6.4.

With the knowledge from Lemma 6.3, we look at a slightly more complex example
of $G(\sigma)$, though we do not draw the full graph:
$\sigma=[3215476]=s_{4}s_{6}s_{1}s_{2}s_{1}$ with descent set
$\text{Des}(\sigma)=\\{1,2,4,6\\}$. The longest string of consecutive descents
is $\\{1,2\\}$.

From Lemma 5.2 $\alpha=[1235476]$ and $\beta=[3214567]$. Note that as we
shuffle $a\in\mathcal{R}(\alpha)$ and $b\in\mathcal{R}(\beta)$, we only
perform shuffle moves of the first and second type. We consider
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}46}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}121}\in\mathcal{R}(\sigma)$
as our starting point.

For any reduced word of $\sigma$, we can select where $121$ or $212$ sits, and
then the remaining two spots can have either $4$ or $6$. Thus we have
$|\mathcal{R}(\sigma)|=2\binom{5}{3}\cdot 2=40$.

We can begin to construct the graph as follows:

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}46}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}121}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}46}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}212}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}64}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}212}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}64}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}121}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}6}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}12}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}6}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}21}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}6}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}12}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}6}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}21}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}21}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}6}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}12}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}6}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}6}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}21}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}6}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}12}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}$
Figure 10. Part of the graph $G([3215476])$

The square of vertices to the far left can be viewed as a copy of the standard
product graph $G([1235476])\times G([3214567])$. The commutation edges in that
square are copies of the single edge from $G([1235476])$, while the braids are
copies of the single braid edge in $G([3214567])$. As we shuffle the elements
4 and 6 to the right, notice that we do not have edges inherited from
$G([1235476])$ or $G([3214567])$ anymore. We have the vertex set of
$G([1235476])\times G([3214567])$, but no internal edges.

We would continue moving forward in this manner, sometimes with those internal
edges present, but most of the time they are not.

There is no reason that we need to stop at splitting $\sigma$ into two pieces
to work with shuffles, as we see in the following theorem:

######  Theorem 6.5.

Let $\sigma\in\mathfrak{S}_{n}$, such that
$\text{Des}(\sigma)=\cup_{i=1}^{m}D_{i}$ where the $D_{i}$’s are the maximal
subsets of $\text{Des}(\sigma)$ containing only consecutive elements. Then

  1. (1)

There exist elements $\beta_{i}$ such that $\text{Des}(\beta_{i})=D_{i}$ for
$1\leq i\leq m$, $\beta_{i}=w_{0}^{(k_{i},a_{i})}$ for some
$k_{i},a_{i}\in\mathbb{N}$, and $\sigma=\alpha\beta_{1}\ldots\beta_{m}$.

  2. (2)

For any $u\in\mathcal{R}(\alpha)$ and selection
$v_{i}\in\mathcal{R}(\beta_{i})$, there exists a reduced word of $\sigma$ of
the form $uv_{1}\ldots v_{m}$.

  3. (3)

We can fully construct $\mathcal{R}(\sigma)$ by looking at all the possible
ways that the letters of $uv_{1}\ldots v_{m}$ can shuffle through each other.

###### Proof.

Note that in the case where $\text{Des}(\sigma)=D_{1}$ or
$\text{Des}(\sigma)=D_{1}\cup D_{2}$, we simply recover the results in Lemma
5.2 and Lemma 6.3.

In the case of larger unions, (1) and (2) are inductive extension of the
result in Lemma 5.2, and (3) is an inductive extension of the result in Lemma
6.3. ∎

###  6.1. Characterizations of simple shuffle graphs

There were distinct advantages to the subgraphs in Section 4. Every edge is
accounted for, and the partitions of $V(G(\sigma))$ produce induced subgraphs
that are isomorphic to $G(\tau)$ for $\tau\leq\sigma$. As we saw in the first
part of Section 6, partitions of $V(G(\sigma))$ into subsets related to
shuffles often missing the edges present in $G(\alpha)$.

Our motivating question has to do with braid edges in graphs $G(\sigma)$. As
we see in Section 7, we can make definitive statements about braid edges if
$\sigma=w_{0}^{(k,i)}$ for some $k,i\in\mathbb{N}$. The shuffle graphs help us
divide up $G(\sigma)$ into more parts related to the $w_{0}^{(k,i)}$’s. This
helps us make certain arguments, but also leads to some mess.

######  Definition 6.6.

Let $\alpha,\beta_{1},\ldots\beta_{m},\sigma\in\mathfrak{S}_{n}$, with
$a\in\mathcal{R}(\alpha)$, $b_{i}\in\mathcal{R}(\beta_{i})$ for all $1\leq
i\leq m$, and $ab_{1}\ldots b_{m}\in\mathcal{R}(\sigma)$ as described in
Theorem 6.5.

Let $C_{I}$ denote all the words in $\mathcal{R}(\sigma)$ where the letters
from $a\in\mathcal{R}(\alpha)$ sit in the positions contained in $I$, where
$I\subset[\ell(\sigma)]$ and $|I|=\ell(\alpha)$. We call this a configuration,
$C_{I}$.

In the case that $\alpha=e$, we consider $C_{I}$ to be formed from all words
where the letters from $b_{1}\in\mathcal{R}(\beta_{1})$ sit in the positions
contained in $I$.

After a shuffle of type 3, we would consider sets labeled $C_{I}^{\prime}$. We
would still be looking at where the red letters descended from $a$ (or
$b_{1}$) would sit, but we would want to be able to differentiate this set
from $C_{I}$.

######  Definition 6.7.

Let $\alpha,\beta_{1},\ldots\beta_{m},\sigma\in\mathfrak{S}_{n}$, with
$u\in\mathcal{R}(\alpha)$, $v_{i}\in\mathcal{R}(\beta_{i})$ for all $1\leq
i\leq m$, and $uv_{1}\ldots v_{m}\in\mathcal{R}(\sigma)$ as described in
Theorem 6.5. We define $H_{I}$ to be the induced subgraph of $G$ with the
vertex set $C_{I}$.

If there is a commutation move or braid move between letters of the words
$a_{1},a_{2}\in\mathcal{R}(\alpha)$, then there is an edge between all
vertices of the form $a_{1}(b_{1}\ldots b_{m})$ and $a_{2}(b_{1}\ldots
b_{m})$, for any selection of words $b_{i}\in\mathcal{R}(\beta_{i})$.
Similarly, in a collection or reduced words $C_{I}$, any time there is a
commutation or braid move between $a_{1},a_{2}\in\mathcal{R}(\alpha)$, and the
letters used in these particular moves are sitting in consecutive spots in the
words contained in $C_{I}$, there is an edge between those vertices for any
selection $b_{i}\in\mathcal{R}(\beta_{i})$.

Note that not all configurations result in a subgraph with
$|\mathcal{R}(\alpha)||\mathcal{R}(\beta)|$ vertices. This is because not all
letters of a reduced word of $\alpha$ need to commute with all letters of a
word of $\beta$. See Example 5.1, Figure 8. Also note that we rarely have
subgraphs that are isomorphic to $G(\alpha)\times G(\beta)$, as the edges are
missing in many cases. See Example 5.1, Figure 9.

For the moment let us consider permutations
$\sigma=\alpha\beta\in\mathfrak{S}_{n}$ where $uv\in\mathcal{R}(\sigma)$ is
such that we only have shuffles of type 1 and 2 between reduced words of
$\alpha$ and $\beta$.

######  Lemma 6.8.

Let $\alpha,\beta,\sigma\in\mathfrak{S}_{n}$, with $u\in\mathcal{R}(\alpha)$,
$v\in\mathcal{R}(\beta)$ and $uv\in\mathcal{R}(\sigma)$ as described in Lemma
5.2 and Definition 6.1. Further suppose that for all $s_{i}$ in the support of
$\alpha$ and all $s_{j}$ in the support of $\beta$, $|i-j|\geq 1$. That is,
there are not any shuffles of the type 3 from Definition 6.1. Then

$|\mathcal{R}(\sigma)|\leq|\mathcal{R}(\alpha)||\mathcal{R}(\beta)|\binom{\ell(\sigma)}{\ell(\alpha)}.$

###### Proof.

We assume that there are not any shuffles of type 3 in $\mathcal{R}(\sigma)$.
So we only need to consider whether letters from $u\in\mathcal{R}(\alpha)$
commute with letters in $v\in\mathcal{R}(\beta)$, or not.

Let $C_{I}$ be defined as in Definition 6.6, where we have chosen the set $I$
such that $|I|=\ell(\alpha)$ and $I\subset\ell(\sigma)$. There are
$\binom{\ell(\sigma)}{\ell(\alpha)}$ choices for the set $I$. Furthermore,
because there are no shuffles of type 3, we have

$\mathcal{R}(\sigma)=\bigcup_{I\subset[\ell(\sigma)],~{}|I|=\ell(\alpha)}C_{I}.$

This is a disjoint union, and some sets $C_{I}$ could be empty.

Let us define new sets $A_{I}$ as follows:

$A_{I}=\\{w\mid a\in\mathcal{R}(\alpha)\mbox{ in positions in
}I,b\in\mathcal{R}(\beta)\mbox{ in the remaining positions}\\}.$

Each of the sets $A_{I}$ has size
$|A_{I}|=|\mathcal{R}(\alpha)||\mathcal{R}(\beta)|$.

These sets may contain words which are not in $\mathcal{R}(\sigma)$. Let
$a=a_{1}\ldots a_{\ell(\alpha)}\in\mathcal{R}(\alpha)$, and $b=b_{1}\ldots
b_{\ell(\beta)}\in\mathcal{R}(\beta)$. Suppose that there are letters in these
words $a_{i}$ and $b_{j}$ such that $|a_{i}-b_{j}|=1$. Then any index set $I$
that places the letter $a_{i}$ to the right of letter $b_{j}$ means that
$A_{I}$ contains words that are not in $\mathcal{R}(\sigma)$.

For any index set $I$, $C_{I}\subset A_{I}$ so that $|C_{I}|\leq|A_{I}|$.
There is no way for $C_{I}$ to be larger than $A_{I}$, since $A_{I}$ already
contains all possible words formed from $a\in\mathcal{R}(\alpha)$ in positions
in $I$.

If $C_{I}=A_{I}$ for all index sets $I$, then

$|\mathcal{R}(\sigma)|=|\mathcal{R}(\alpha)||\mathcal{R}(\beta)|\binom{\ell(\sigma)}{\ell(\alpha)}.$

If there are letters in a word $a\in\mathcal{R}(\alpha)$ that do not commute
with letters in $b\in\mathcal{R}(\beta)$, then there is some index set $J$
such that $C_{J}\neq A_{J}$. In which case,

$|\mathcal{R}(\sigma)|<|\mathcal{R}(\alpha)||\mathcal{R}(\beta)|\binom{\ell(\sigma)}{\ell(\alpha)}.$

Therefore, we have the desired inequality. ∎

The shuffling process and configuration subgraphs that are described in the
lemmas and definition above gives us a way to divide our graphs up into copies
of $G(\alpha)$ and $G(\beta)$.

######  Corollary 6.9.

Let $\alpha,\beta,\sigma\in\mathfrak{S}_{n}$, with $u\in\mathcal{R}(\alpha)$,
$v\in\mathcal{R}(\beta)$ and $uv\in\mathcal{R}(\sigma)$ as described in Lemma
5.2 and Definition 6.1.

If we arrive at $C_{I}$ using only shuffles of type 1 and 2, then $H_{I}$ is a
subgraph of $G(\alpha)\times G(\beta)$. $H_{I}$ does not need to be an induced
subgraph. If a shuffle of type 1 from Definition 6.1 exists in this
configuration, then each of those edges from $G(\alpha)$ is replaced with
$|\mathcal{R}(\beta)|$ copies of the same edge.

######  Lemma 6.10.

Let $\alpha,\beta,\sigma\in\mathfrak{S}_{n}$, with $u\in\mathcal{R}(\alpha)$,
$v\in\mathcal{R}(\beta)$ and $uv\in\mathcal{R}(\sigma)$ as described in Lemma
5.2 and Definition 6.1.

If we arrive at $C_{I}$ using all three types of shuffles, $H_{I}$ is not
necessarily a subgraph of $G(\alpha)\times G(\beta)$, because a type 3 shuffle
changes $\alpha$ and $\beta$.

###### Proof.

As soon as a shuffle of type 3 has occurred, we no longer have a reduced word
of the form $uv$ for $u\in\mathcal{R}(\alpha)$ and $v\in\mathcal{R}(\beta)$.
Instead, we now have $ab$ where $a\in\mathcal{R}(\alpha^{\prime})$, and
$\mathcal{R}(\beta^{\prime})$ where $\sigma=\alpha^{\prime}\beta^{\prime}$.
The subgraphs with the vertices $ab$ are not required to have any relationship
to vertices in $G(\alpha)\times G(\beta)$. ∎

The reason we want to look at this family of subgraphs is because we know a
lot about $G(w_{0}^{(k,i)})$. However, for an arbitrary $\sigma$, we have less
information about $G(\sigma s_{j})$ for $j\in\text{Des}(\sigma)$.

######  Lemma 6.11.

Let $\alpha,\beta\in\mathfrak{S}_{n}$. Then

$\sum_{v\in G(\alpha)\times
G(\beta)}d_{\mathcal{B}}(v)=|\mathcal{R}(\alpha)|\cdot\sum_{u\in
G(\beta)}d_{\mathcal{B}}(u)+|\mathcal{R}(\beta)|\cdot\sum_{t\in
G(\alpha)}d_{\mathcal{B}}(t).$

###### Proof.

We consider $G(\alpha)\times G(\beta)$ as follows: let $v\in G(\alpha)\times
G(\beta)$ be labeled as $(a,b)$ for $a\in\mathcal{R}(\alpha)$ and
$b\in\mathcal{R}(\beta)$.

There is a braid edge between $(a,b)$ and $(a^{\prime},b^{\prime})$ if and
only if there is a braid move between $a$ and $a^{\prime}$ and $b=b^{\prime}$,
or if there is a braid move between $b$ and $b^{\prime}$ and $a=a^{\prime}$.

Therefore, the braid degree of $v\in G(\alpha)\times G(\beta)$ depends on the
braid degrees of $a\in G(\alpha)$ and $b\in G(\beta)$. That is, $v=(a,b)$ is
such that $d_{\mathcal{B}}(v)=d_{b}^{G(\alpha)}(a)+d_{b}^{G(\beta)}(b)$. In
order to calculate $\sum_{v\in G(\alpha)\times G(\beta)}d_{\mathcal{B}}(v)$,
we have to be able to vary over $a\in\mathcal{R}(\alpha)$ and
$b\in\mathcal{R}(\beta)$.

Therefore, our calculation are

$\displaystyle\sum_{v\in G(\alpha)\times G(\beta)}d_{\mathcal{B}}(v)$
$\displaystyle=$ $\displaystyle\sum_{t\in G(\alpha)}\sum_{u\in
G(\beta)}d_{\mathcal{B}}(t)+d_{\mathcal{B}}(u)$ $\displaystyle=$
$\displaystyle\sum_{t\in G(\alpha)}\left(\sum_{u\in
G(\beta)}d_{\mathcal{B}}(t)+\sum_{u\in G(\beta)}d_{\mathcal{B}}(u)\right)$
$\displaystyle=$ $\displaystyle\sum_{t\in
G(\alpha)}\left(|\mathcal{R}(\beta)|d_{\mathcal{B}}(t)+\sum_{u\in
G(\beta)}d_{\mathcal{B}}(u)\right)$ $\displaystyle=$ $\displaystyle\sum_{t\in
G(\alpha)}|\mathcal{R}(\beta)|d_{\mathcal{B}}(t)+\sum_{t\in
G(\alpha)}\sum_{u\in G(\beta)}d_{\mathcal{B}}(u)$ $\displaystyle=$
$\displaystyle|\mathcal{R}(\beta)|\cdot\sum_{t\in
G(\alpha)}d_{\mathcal{B}}(t)+|\mathcal{R}(\alpha)|\cdot\sum_{u\in
G(\beta)}d_{\mathcal{B}}(u),$

as desired ∎

##  7\. Bounds on the number of Braid Classes

In this section, we heavily rely on two results we discussed in Section 2: the
main result from Fishel, Milićević, Patrias, and Tenner (Theorem 2.8[7]), and
the result from Reiner (Theorem 2.12 [8]).

After extensive work with examples for $n=4,5,6,7,8$, using Sage to help find
the sizes of the sets of reduced words, we arrived at the following
conjectures.

######  Conjecture 7.1.

For all $\sigma\in\mathfrak{S}_{n}$,

$\dfrac{1}{2}|\mathcal{R}(\sigma)|\leq|\mathcal{B}(\sigma)|\leq|\mathcal{R}(\sigma)|.$

######  Conjecture 7.2.

For all $\sigma\in\mathfrak{S}_{n}$,

$0\leq|\mathcal{C}(\sigma)|\leq\dfrac{1}{2}|\mathcal{R}(\sigma)|+1.$

###  7.1. The weak order lattice and the longest permutation

Much like the other research done by Tenner [15] and Schilling et al. [11], we
start with results related to $G(w_{0})$.

######  Theorem 7.3.

For $w_{0}\in\mathfrak{S}_{n}$,
$|\mathcal{B}(w_{0})|\geq\dfrac{1}{2}|\mathcal{R}(w_{0})|-1$.

###### Proof.

We consider the graph $G_{b}^{\prime}(w_{0})$, as defined in Definition 2.11.
Recall that the connected components of this graph are the braid classes of
$G(w_{0})$. We would like to show that there are at least
$\dfrac{1}{2}|\mathcal{R}(w_{0})|-1$ connected components.

Suppose to the contrary that there are less than
$\dfrac{1}{2}|\mathcal{R}(w_{0})|-1$ connected components in
$G^{\prime}_{\mathcal{B}}(w_{0})$. Then if $|\mathcal{R}(w_{0})|$ is even, we
have at most $\dfrac{1}{2}|\mathcal{R}(w_{0})|-2$ components, and if
$|\mathcal{R}(w_{0})|$ is odd, then there are at most
$\dfrac{1}{2}|\mathcal{R}(w_{0})|-\dfrac{3}{2}$ components.

We can partition our vertex set over the connected components. Suppose there
are $m$ connected components, and let $V_{i}$ be the vertex set for one of
these components, for $1\leq i\leq m<\dfrac{1}{2}|\mathcal{R}(w_{0})|-1$.
Then,

$V(G_{b}^{\prime}(w_{0}))=\bigcup_{1\leq i\leq m}V_{i}.$

We note that a graph with $V$ vertices and $k$ components must have at least
$V-k$ edges, since a component with $V_{i}$ vertices must have a spanning tree
with $V_{i}-1$ edges. We assume there are $m$ components, where
$m\leq\dfrac{1}{2}|\mathcal{R}(w_{0})|-i$, for
$i\in\left\\{\dfrac{3}{2},2\right\\}$. Thus, we can subtract off a maximum of
$\dfrac{1}{2}|\mathcal{R}(w_{0})|-i$ edges.

We also see that each of the connected components in $G_{b}^{\prime}(w_{0})$
are at minimum tree graphs, which means we have at least

$\sum_{v\in V(G(w_{0}))}d_{G^{\prime}_{\mathcal{B}}(w_{0})}(v)\geq
2|\mathcal{R}(w_{0})|-2.$

Thus, for $i\in\left\\{\dfrac{3}{2},2\right\\}$, we have

$\displaystyle\sum_{v\in V(G(w_{0}))}d_{G^{\prime}_{\mathcal{B}}(w_{0})}(v)$
$\displaystyle=$ $\displaystyle 2E(G^{\prime}_{\mathcal{B}}(\sigma))$
$\displaystyle\geq$ $\displaystyle
2|\mathcal{R}(w_{0})|-2-2\left[\dfrac{1}{2}|\mathcal{R}(w_{0})|-i\right]$
$\displaystyle>$ $\displaystyle|\mathcal{R}(w_{0})|,$

for either choice of $i$.

This contradicts Reiner’s result in Theorem 2.12 that states that the sum of
the braid degrees exactly equals the size of the set of reduced words. ∎

Initially, we may only note that this theorem is true for
$w_{0}\in\mathfrak{S}_{n}$. However, in Section 2, Definition 3.2, we defined
the family of $w_{0}^{(k,i)}$ permutations. Since these are permutations that
also produce graphs of the form $G(w_{0})$ for $w_{0}\in\mathfrak{S}_{k}$, the
result is true for more than one permutation in $\mathfrak{S}_{n}$ when $n>3$.

###  7.2. Bounds on the number of braid classes for certain families of
permutations

We now use our results from Sections 4 and 5 to prove results similar to
Theorem 7.3 for more general families of permutations.

In the following lemma, we refer to certain $\alpha\in\mathfrak{S}_{n}$ as
being completely commutative permutations. In this case we do not mean fully
commutative, we simply mean that a reduced decomposition of $\alpha$ is formed
from commuting generators. For example, $\sigma=s_{1}s_{3}s_{5}$ would be
completely commutative, while $\tau=s_{4}s_{1}s_{2}s_{3}$ would be fully
commutative.

######  Lemma 7.4.

Suppose that $\text{Des}(\sigma)=[i,i+k-1]\cup J$, where $k$ is the length of
the longest string of consecutive elements in $\text{Des}(\sigma)$. Then

  1. (1)

If $k=1$,

$A(\sigma):=|\mathcal{R}(\sigma)|-\left(\sum_{v\in
G(\sigma)}d_{\mathcal{B}}(v)\right)>0.$

  2. (2)

If $J=\\{j\\}$ and $\sigma=s_{j}w_{0}^{(k,i)}$, then $A(\sigma)>0$.

  3. (3)

If $J\neq\emptyset$, $\alpha$ is completely commutative with
$\text{Des}(\alpha)=J$, and $\sigma=\alpha w_{0}^{(k,i)}$, then $A(\sigma)>0$.

  4. (4)

If $J\neq\emptyset$, $\alpha$ is fully commutative with
$\text{Des}(\alpha)=J$, every $s_{i}$ in the support of $\alpha$ commutes with
all $s_{i}$’s in the support of $w_{0}^{(k,i)}$, and $\sigma=\alpha
w_{0}^{(k,i)}$, then $A(\sigma)>0$.

  5. (5)

If $J=\emptyset$ and $\sigma=w_{0}^{(k,i)}$, then $A(\sigma)=0$.

###### Proof.

First, we note that point five above is exactly Theorem 2.12. Thus we focus on
proving the other three parts of our lemma.

Let $\sigma\in\mathfrak{S}_{n}$ where $l(\sigma)=l$ and
$\text{Des}(\sigma)=[i,i+k-1]\cup J$ for some $k,i\in\mathbb{Z}$ such that no
string of consecutive elements in $J$ has length greater than $k$.

Suppose that for all $\tau\in\mathfrak{S}_{n}$ where $l(\tau)<l$, exactly one
of the following is true:

  1. (1)

$\tau=w_{0}^{(k,i)}$, and $A(\tau)=0$,

  2. (2)

$\tau\neq w_{0}^{(k,i)}$, and $A(\tau)>0$.

We want to show that $A(\sigma)>0$ as well.

Case 1: Let $k=1$. That is, suppose that $\text{Des}(\sigma)$ does not contain
any consecutive elements. Then we select any $j\in\text{Des}(\sigma)$, and
consider the word $aj\in\mathcal{R}(\sigma)$ where $a\in\mathcal{R}(\sigma
s_{j})$.

If $\text{Des}(\sigma)=\\{j\\}$, we note that
$|\mathcal{R}(\sigma)|=|\mathcal{R}(\sigma s_{j})|$. Then $A(\sigma)=A(\sigma
s_{j})>0$ by our induction hypothesis.

If $|\text{Des}(\sigma)|>1$, Proposition 3.3 notes that at most one
$j\in\text{Des}(\sigma)$ produces $\sigma s_{j}=w_{0}^{(k,i)}$. Using
Corollary 4.9, we have

$\displaystyle\sum_{v\in G(\sigma)}d_{\mathcal{B}}(v)$ $\displaystyle=$
$\displaystyle\left(\sum_{x\in\text{Des}(\sigma)}\sum_{u\in G(\sigma
s_{x})}d_{\mathcal{B}}(u)\right)+2\cdot\sum_{x,x+1\in\text{Des}(\sigma)}|\mathcal{R}(\sigma
s_{x}s_{x+1}s_{x})|$ $\displaystyle=$
$\displaystyle\sum_{x\in\text{Des}(\sigma)}\sum_{u\in G(\sigma
s_{x})}d_{\mathcal{B}}(u),$

because there are no consecutive elements in the set $\text{Des}(\sigma)$.

We assume that $A(\sigma s_{x})=0$ for at most one descent $x$, and $A(\sigma
s_{y})>0$ for all other descents $y$. There are at least two elements in
$\text{Des}(\sigma)$, and therefore,

$\displaystyle\sum_{v\in G(\sigma)}d_{\mathcal{B}}(v)$ $\displaystyle=$
$\displaystyle\sum_{x\in\text{Des}(\sigma)}\sum_{u\in G(\sigma
s_{x})}d_{\mathcal{B}}(u)$ $\displaystyle<$
$\displaystyle\sum_{x\in\text{Des}(\sigma)}\left(|\mathcal{R}(\sigma
s_{x})|\right)$ $\displaystyle=$ $\displaystyle|\mathcal{R}(\sigma)|,$

and therefore, $A(\sigma)>0$.

Case 2: Let $\ell(\alpha)=1$. Suppose that $\alpha=s_{j}$,
$\beta=w_{0}^{(k,i)}$, so that $jv\in\mathcal{R}(\sigma)$ for
$v\in\mathcal{R}(w_{0}^{(k,i)})$. Because
$\text{Des}(\sigma)=[i,i+k-1]\cup\\{j\\}$, we know that
$j\notin\\{i-1,i+k\\}$. Then $j$ commutes with every letter in
$u\in\mathcal{R}(\beta)$, so we can split up $G(\sigma)$ into subgraphs
$H_{t}$ as defined in Definition 6.7, where $1\leq t\leq\ell(\beta)+1$.

Since $j$ commutes with everything in $u\in\mathcal{R}(\beta)$, we know that
$j$ cannot be used in a braid move, and that
$|V(H_{t})|=|\mathcal{R}(\beta)|$. Thus each of the $H_{t}$’s is joined to
another $H_{t-1}$ and $H_{t+1}$ by commutation edges.

In any three consecutive positions in $\beta$, there are
$\sum_{m,m+1\in\text{Des}(\beta)}|\mathcal{R}(\beta s_{m}s_{m-1}s_{m})|$ braid
moves, corresponding to braid edges. Since $\beta$ is a $w_{0}^{(k,i)}$, using
notation from Definition 2.11, we also know that

$|\mathcal{R}(\beta)|=2\cdot|E_{\mathcal{B}}(\beta)|=\sum_{v\in
G(\beta)}d_{\mathcal{B}}(v),$

which means that

$|\mathcal{R}(\beta)|=2\cdot\left((l(\beta)-2)\sum_{m,m+1\in\text{Des}(\beta)}|\mathcal{R}(\beta
s_{m}s_{m-1}s_{m})|\right)=\sum_{v\in G(\beta)}d_{\mathcal{B}}(v).$

For $t=1,l(\beta)+1$, the subgraph $H_{t}$ has exactly $|\mathcal{R}(\beta)|$
vertices, and $\sum_{v\in H_{t}}d_{\mathcal{B}}(v)=|V(H_{t})|$.

For $t=2,l(\beta)$, the subgraph $H_{t}$ has exactly $|\mathcal{R}(\beta)|$
vertices, but

$\sum_{v\in
H_{t}}d_{\mathcal{B}}(v)=2\cdot\left((l(\beta)-3)\sum_{m,m+1\in\text{Des}(\beta)}|\mathcal{R}(\beta
s_{m}s_{m-1}s_{m})|\right)<|\mathcal{R}(\beta)|.$

For all other $3\leq t\leq l(\beta)-1$, the subgraph $H_{t}$ has exactly
$|\mathcal{R}(\beta)|$ vertices, but

$\sum_{v\in
H_{t}}d_{\mathcal{B}}(v)=2\cdot\left((l(\beta)-4)\sum_{m,m+1\in\text{Des}(\beta)}|\mathcal{R}(\beta
s_{m}s_{m-1}s_{m})|\right)<|\mathcal{R}(\beta)|.$

Thus

$\sum_{v\in G(\sigma)}d_{\mathcal{B}}(v)<|\mathcal{R}(\sigma)|,$

so that $A(\sigma)>0$ as desired.

Case 3 and 4: Let $\ell(\alpha)=m$. Let $\alpha=s_{a_{1}}\ldots s_{a_{m}}$,
$\beta=w_{0}^{(k,i)}$, so that $a_{1}\ldots a_{m}v\in\mathcal{R}(\sigma)$ for
$v\in\mathcal{R}(w_{0}^{(k,i)})$. Because $\text{Des}(\sigma)=[i,i+k-1]\cup
J$, we know that $a_{j}\notin\\{i-1,i+k\\}$ for any $1\leq j\leq m$. Then
$a_{j}$ commutes with every letter in $u\in\mathcal{R}(\beta)$, so we can
split up $G(\sigma)$ into subgraphs $H_{t}$ as defined in Definition 6.7,
where $1\leq t\leq\binom{\ell(\alpha)+\ell(\beta)}{\ell(\alpha)}$.

Since each $a_{j}$ commutes with everything in $u\in\mathcal{R}(\beta)$, and
$\alpha$ is fully commutative, we know that each $a_{j}$ cannot be used in a
braid move, and that
$|V(H_{t})|=|\mathcal{R}(\alpha)|\cdot|\mathcal{R}(\beta)|$. Thus each of the
$H_{t}$’s is joined to another $H_{t-1}$ and $H_{t+1}$ by commutation edges.
Additionally, each of the graphs $H_{t}$ are a subgraph of $G(\alpha)\times
G(\beta)$, where $V(H_{t})=V(G(\alpha)\times G(\beta))$, and $E(H_{t})\subset
E(G(\alpha)\times G(\beta))$. We also know from 6.11 that the only braid edges
are in the copies of $G(\beta)$.

Using the same argument as Case 2, we have the following facts about our
subgraphs $H_{t}$:

For any subgraph $H_{t}$ where the letters of $\beta$ sit in consecutive
positions, $H_{t}$ has $|\mathcal{R}(\alpha)||\mathcal{R}(\beta)|$ vertices,
and $\sum_{v\in H_{t}}d_{\mathcal{B}}(v)=|V(H_{t})|$.

For any subgraph $H_{t}$ where at least two letters of $\beta$ are separated
by at least one letter of $\alpha$, $H_{t}$ still has exactly
$|\mathcal{R}(\alpha)||\mathcal{R}(\beta)|$ vertices, but $\sum_{v\in
H_{t}}d_{\mathcal{B}}(v)<|\mathcal{R}(\alpha)||\mathcal{R}(\beta)|$ Thus

$\sum_{v\in G(\sigma)}d_{\mathcal{B}}(v)<|\mathcal{R}(\sigma)|,$

so that $A(\sigma)>0$ as desired. ∎

Note that the cases we have proven in Lemma 7.4 relied heavily on the work we
did in Sections 4 and 5. This Lemma also covers all the cases we have been
able to prove.

######  Theorem 7.5.

Let $\sigma\in\mathfrak{S}_{n}$ be one of the permutations covered by Lemma
7.4. Then

$|\mathcal{B}(\sigma)|\geq\dfrac{1}{2}|\mathcal{R}(\sigma)|-1\quad\mbox{ and
}\quad|\mathcal{C}(\sigma)|\leq\dfrac{1}{2}|\mathcal{R}(\sigma)|+2.$

###### Proof.

We can follow all the steps of the proof of Lemma 7.3, replacing $w_{0}$ with
$\sigma$. The proof is dependent on arriving at

$\sum_{v\in G(w_{0})}d_{\mathcal{B}}(v)>|\mathcal{R}(w_{0})|,$

which is a contradiction for $w_{0}$. If $\sigma$ is one of the permutations
in Lemma 7.4, then $A(\sigma)>0$, and this is also a contradiction for
$\sigma$.

Thus $|\mathcal{B}(\sigma)|\geq\dfrac{1}{2}|\mathcal{R}(\sigma)|-1$. By
Theorem 2.8,

$|\mathcal{B}(\sigma)|+|\mathcal{C}(\sigma)|-1\leq|\mathcal{R}(\sigma)|.$

We can now rewrite this as

$\dfrac{1}{2}|\mathcal{R}(\sigma)|-1+|\mathcal{C}(\sigma)|-1\leq|\mathcal{R}(\sigma)|,$

which means that

$|\mathcal{C}(\sigma)|\leq\dfrac{1}{2}|\mathcal{R}(\sigma)|+2,$

as desired. ∎

While not complete for arbitrary permutations, this theorem represents all
current knowledge of the relationship between $|\mathcal{B}(\sigma)|$ and
$|\mathcal{R}(\sigma)|$. We used all of our new tools related to subgraphs to
arrive at this result, and believe that additional work on our new families of
subgraphs are required to prove any more cases.

##  8\. Future Work

Finally, we detail some future directions of study for the work done in this
paper.

  1. (1)

There are two possible results that would prove Theorem 7.5 for all
permutations:

######  Conjecture 8.1.

For any $\sigma\in\mathfrak{S}_{n}$,

$A(\sigma)=|\mathcal{R}(\sigma)|-\left(\sum_{v\in
G(\sigma)}d_{\mathcal{B}}(v)\right)\geq 0.$

######  Conjecture 8.2.

For all $\sigma\in\mathfrak{S}_{n}$, when $\sigma=w_{0}^{(k,i)}$ for some
$k,i\in\mathbb{N}$, then $G(\sigma)$ has the highest proportion of braid edges
to vertices in any graph of $\mathcal{R}(\sigma)$ in $\mathfrak{S}_{n}$.

We have spent considerable time attempting to prove these conjectures, but as
of the writing of this paper, the cases present in Lemma 7.4 represents all of
our progress on Theorem 7.5.

  2. (2)

Theorem 6.5 allows us to break permutations into more parts than we consider
in Lemma 7.4. That is, more parts that are equivalent to $w_{0}^{(k,i)}$’s.
Can we add cases to Lemma 7.4 using a more general division of $\sigma$?

  3. (3)

If Theorem 7.5 can be proven for all permutations, we still have Conjectures
7.1 and 7.2, which we believe are the true limits of these ratios. Are there
other methods of proving these conjectures without our work on subgraphs?

  4. (4)

Since these families of subgraphs have not been studied, we intend to continue
to investigate what they can tell us about $\mathcal{R}(\sigma)$ apart from
congruence classes and number of edges in $G(\sigma)$.

  5. (5)

As noted in Section 6, 12 and 21 inflations have been well studied. Since
shuffles are a more general method of looking at permutations, we continue to
study what they can tell us about $\mathcal{R}(\sigma)$ and $G(\sigma)$.

## Acknowledgements

Most of this research was done as part of the author’s PhD dissertation at
Arizona State University. The author would like to thank her advisor, Susanna
Fishel, for advice and support related to the writing of this document. The
author would like to thank J. Carlos Martínez Mori for the development of
Figure 2. The author would also like to thank Samantha Dahlberg and Bridget
Tenner for answering questions on related problems in research on sets of
reduced words.

## References

  * [1] Michael H. Albert, Nik Ruškuc, and Vincent Vatter.  Inflations of geometric grid classes of permutations (english summary).  Israel Journal of Mathematics, 205:73–108, 2015.
  * [2] Sara Billey, Krzysztof Burdzy, and Bruce E. Sagan.  Permutations with given peak set.  J. Integer Seq., 16(6):Article 13.6.1, 18, 2013.
  * [3] Samantha Dahlberg and Younghwan Kim.  Diameters of graphs on reduced words of 12 and 21-inflations, 2020.
  * [4] Alexander Diaz-Lopez, Pamela E. Harris, Isabella Huang, Erik Insko, and Lars Nilsen.  A formula for enumerating permutations with a fixed pinnacle set.  Discrete Mathematics, 344(6):112375, 2021.
  * [5] Jennifer Elder, Nadia Lafrenière, Erin McNicholas, Jessica Striker, and Amanda Welch.  Homomesies on permutations – an analysis of maps and statistics in the findstat database.  Mathematics of Computation, 2023.
  * [6] Serge Elnitsky.  Rhombic tilings of polygons and classes of reduced words in coxeter groups.  Journal of Combinatorial Theory, Series A, 77(2):193–221, 1997\.
  * [7] Susanna Fishel, Elizabeth Milićević, Rebecca Patrias, and Bridget Eileen Tenner.  Enumerations relating braid and commutation classes.  European Journal of Combinatorics, 74:11–26, 2018.
  * [8] Victor Reiner.  Note on the expected number of yang–baxter moves applicable to reduced decompositions.  European Journal of Combinatorics, 26(6):1019–1021, 2005.
  * [9] Victor Reiner and Yuval Roichman.  Diameter of graphs of reduced words and galleries.  Transactions of the American Mathematical Society, 365, 05 2013\.
  * [10] Martin Rubey, Christian Stump, et al.  FindStat - The combinatorial statistics database.  http://www.FindStat.org.
  * [11] Anne Schilling, Nicolas M. Thiéry, Graham White, and Nathan Williams.  Braid moves in commutation classes of the symmetric group.  European Journal of Combinatorics, 62:15–34, 2017.
  * [12] Richard P. Stanley.  On the number of reduced decompositions of elements of coxeter groups.  European Journal of Combinatorics, 5(4):359–372, 1984.
  * [13] Bridget Eileen Tenner.  Reduced decompositions and permutation patterns.  Journal of Algebraic Combinatorics, 24, 07 2005.
  * [14] Bridget Eileen Tenner.  Pattern avoidance and the bruhat order.  Journal of Combinatorial Theory, Series A, 114(5):888–905, 2007\.
  * [15] Bridget Eileen Tenner.  On the expected number of commutations in reduced words.  Australasian Journal of Combinatorics, 62(1):147–154, 2015.
  * [16] Bridget Eileen Tenner.  Interval structures in the bruhat and weak orders.  Journal of Combinatorics, 13(1):135 – 165, 2022.