I was planning to include this as part of an earlier post, but I figured this was important enough to warrant a new post. Bruhat order is a partial ordering on a Weyl group that arises from Schubert calculus. The main result required here is Theorem 5.3, but since this is its own post I added some additional material that we may explore in further detail later. We have two main goals here: one is to develop the theory sufficiently to state and prove the main result in my dissertation, and the other is to present some of my work that is unpublished and probably will only be published here. It's going to take a few more posts to get to my dissertation, after which we will see where it goes. There is an unpublished result of mine based on the root systems that has already been cited by Sara Billey in a talk and that I hope to get to here.
Definition 1: Let (R,B) be a root system. If u,v∈W(R), define u→v if there exists y∈I(v) such that usy=v; that is, u−1v is a reflection and ℓ(u)<ℓ(v). Then define a partial ordering ≤, called Bruhat order, to be the reflexive, transitive closure of →.
This definition of Bruhat order is not always the easiest to work with. The main theorem in this post gives another characterization of Bruhat order in terms of subwords.
Definition 2: Given a word (sx1,…,sxn), we say that a sequence (e1,…,en) is a subword of this word if ei∈{1,sxi} for all i. A subword has an associated word obtained by deleting all of the 1's; we say the subword is reduced if the corresponding word is reduced, and we say that the subword is for the element e1e2⋯en. We can iterate this process; if we have two subwords u′=(e1,…,en), u″ of a word \mathbf{u} we say that \mathbf{u}' is a subword of \mathbf{u}'' if e_i\in \{1,f_i\} for all i.
We will need the following lemma (or rather the corollary afterwards).
Lemma 5.1 (The deletion property): Let (R,B) be a root system, let w\in W(R), and let (s_{x_1},\ldots,s_{x_n}) be a word for w. If w is not reduced, then there exist indices i < j such that
(s_{x_1},\ldots,\widehat{s_{x_i}},\ldots,\widehat{s_{x_j}},\ldots,s_{x_n})
is a word for w.
Proof: Let j be the minimal index such that (s_{x_1},\ldots,s_{x_j}) is not a reduced word. Let v=s_{x_1}\cdots s_{x_{j-1}}. Then \ell(vs_{x_j}) < \ell(v), so there exists an index i such that
(s_{x_1},\ldots,\widehat{s_{x_i}},\ldots,s_{x_{j-1}})
is a word for vs_{x_j}. These are the i and j we seek in the statement of the result. \square
The proof of the following is easy and we leave it to the reader.
Corollary 5.2: Let (R,B) be a root system and let w\in W(R). Given any word (s_{x_1},\ldots,s_{x_n}) for w there exists a reduced subword for w. \square
Theorem 5.3: Let (R,B) be a root system and let u,v\in W(R). Then u\leq v if and only if for any word (s_{x_1},\ldots,s_{x_n}) for v there exists a reduced subword for u.
Proof: We prove that if u\leq v then there exists such a reduced subword by induction on \ell(v)-\ell(u), the result being true by the corollary when \ell(u)=\ell(v). Otherwise by definition there exists a u' with u\leq u'\to v. By Theorem 2.3 we may delete one element from any word for v to obtain a word for u', or equivalently set the element at some single index to 1 to obtain a subword for u'. By the induction hypothesis, for this subword for u' we have that there is a reduced subword that is a word for u. Thus there is a reduced subword for u of the word for v, and one implication follows.
Suppose now that there exists such a subword for u in any word for v. Let \mathbf{v} be a reduced word for v containing a reduced subword \mathbf{u} for u; we prove by induction on \ell(v) that u\leq v. When \ell(v)=0 we must have that \ell(u)=0 so the result holds. Let s_{x_n} be the last simple reflection in \mathbf{v}, so the element \mathbf{v}_{\ell(v)}, so that \ell(v)=n. Let \widehat{\mathbf{v}} be the subword of \mathbf{v} such that \widehat{\mathbf{v}}_n=1 and \widehat{\mathbf{v}}_i=\mathbf{v}_i for i < n; note that this is a subword for vs_{x_n}. Similarly, let \widehat{\mathbf{u}} be the subword of \mathbf{u} such that \widehat{\mathbf{u}}_n=1 and \widehat{\mathbf{u}}_i=\mathbf{u}_i for i < n. Suppose first \mathbf{u}_n\neq s_{x_n}. Then \mathbf{u}=\widehat{\mathbf{u}} is a subword of \widehat{\mathbf{v}}, so u\leq vs_{x_n}\to v by the induction hypothesis and the result follows.
If \mathbf{u}_n=s_{x_n}, then since \widehat{\mathbf{u}} is a subword for us_{x_n} and is a subword of \widehat{\mathbf{v}} we have by the induction hypothesis that us_{x_n}\leq vs_{x_n}. Thus there exists some u' such that us_{x_n}\leq u'\to vs_{x_n}, and there is a reduced subword \mathbf{u}' of \widehat{\mathbf{v}} for u'. Assume without loss of generality that \widehat{\mathbf{u}} is a subword of \mathbf{u}'. We split into two cases, depending on whether x_n\in I(u').
If x_n\notin I(u'), then \ell(u's_{x_n}) > \ell(u'), hence if \mathbf{u}'' is the subword of \mathbf{v} for u's_{x_n} such that \mathbf{u}''_i=\mathbf{u}'_i for i < n and \mathbf{u}''_n=s_{x_n}, then since \mathbf{u} is a subword of \mathbf{u}'' and u's_{x_n}\to v (since if u's_y=vs_{x_n} then (u's_{x_n})s_{x_n\ast y}=v) we have by the induction hypothesis that u\leq u's_{x_n}\leq v and we are done.
If x_n\in I(u'), then we may assume that \mathbf{u}'_n=s_{x_n}. This is because if this were not the case then we could delete an element of \mathbf{u}', setting say \mathbf{u}'_i=1 to obtain a word for u's_{x_n}, then set \mathbf{u}'_n=s_{x_n} to obtain another subword for u'. \mathbf{u}' contains a reduced subword for us_{x_n} by the induction hypothesis whose last element is not s_{x_n} (because no word for us_{x_n} ends in s_{x_n}), hence there is a reduced subword \widetilde{\mathbf{u}} of \mathbf{u}' for u, so that u\leq u'\to vs_{x_n}\to v by the induction hypothesis and we are done. The result follows by induction.
\square
Now we for the additional material, where we relate Bruhat order to subsystems. The following theorem, which is an easy consequence of the theory built so far in this blog, is highly nontrivial in the setting of Coxeter systems. It was the main result of (Dyer, Matthew. On the "Bruhat graph" of a Coxeter system, Compositio Mathematica 78.2 (1991): 185-191). To start we will need a lemma, followed by a definition, then we may move on to the theorem. Recall that for a root system (R,B) and a subsystem U, we defined in Theorem-Definition 4.5 a function \phi_U:W(R)\to W(U) that sends an element w\in W(R) to the element of W(U) whose inversion set in U is the intersection I(w)\cap U.
Lemma 5.4: Let (R,B) be a root system, let U\subseteq R be a subsystem, and let w\in W(R). Then w\in W(U) if and only if
\phi_U(w)=w
Proof: By definition, the codomain of \phi_U is W(U), hence if \phi_U(w)=w then w\in W(U). Conversely, suppose w\in W(U) and \phi_U(w)=w'\in W(U). Then I_U(w)=I_U(w'), and since w,w'\in W(U) it follows by Proposition 3.5 that w=w'. The result follows. \square
Definition 3: Let (R,B) be a root system and let U be a subsystem. If u,v\in W(R) are such that \ell(u) < \ell(v) and there exists a root y\in U such that us_y=v, then we say that u\to_U v. Define \leq_U to be the reflexive, transitive closure of \to_U. Note that Bruhat order on W(U) is the restriction of the relation \leq_U.
The Bruhat graph of a Weyl group W(R) is the directed graph on W(R) with the edges u\to v, where we may consider the edge u\to v as being labeled with the reflection u^{-1}v. The theorem below says that the Bruhat graph of wW(U)\subseteq W(R) for any coset wW(R) is isomorphic as a labeled graph to the Bruhat graph of W(U) and is an induced subgraph of the Bruhat graph of W(R) (so there are no extra edges that do not come from reflections in W(U)).
Theorem 5.5: Let (R,B) be a root system, let U be a subsystem, and let w\in W(R). If u,v are both contained in the coset wW(U), then u\to_R v if and only if u\to_U v.
Proof: If u\to_U v, then clearly u\to_R v. Conversely, if u\to_R v, then there exists a reflection t\in W(R) such that ut=v. Since u,v are in the same left coset of W(U) we must have that t\in W(U). We need to prove then that if t\in W(R) is a reflection and t\in W(U), then there is a root y\in U such that t=s_y. The contrapositive is that if t=s_y for some y\in R-U, then t\notin W(U). To see this, let w'\in W(R) be an element such that w'(y)\in B. Then s_y\notin W(U) if and only if s_{w'(y)}\notin W(w'(U)). For all z\in w'(U)\cap R^+(B) we have that w'(y)\ast z\in R^+(B), hence \phi_{w'(U)}(s_{w'(y)})=1\neq s_{w'(y)}, hence s_{w'(y)}\notin W(w'(U)) by Lemma 5.4 and we are done. \square
This implies that if u,v\in wW(U) and \phi_U(u)\leq_U \phi_U(v), then u\leq v. However, this does not in general imply that if u,v\in wW(U) and u\leq v then \phi_U(u)\leq_U \phi_U(v). For an example, consider the root system R_{A}^3, defined in post 2. Let x=t_2-t_3 and let y=t_1-t_4. Then U=\{\pm x,\pm y\} is a subsystem of R_{A}^3 since x\ast y=y and y\ast x=x, and s_x\leq s_y. However it is not the case that s_x\leq_U s_y because \ell_U(s_x)=\ell_U(s_y).