Bruhat Interval Labels, Shellings, and Möbius Functions

Cancellation identity. Let $P=\{i_1<\cdots <i_k\}\subseteq \{1,\dots ,r\}$ index the positions deleted from $t_1\cdots t_r$ by a maximal chain, so that $a={\prod }_{p\mathrm{\notin }P}{t}_p$ is a reduced word with $\mathrm{\ell }(a)=r-k$, and let $j\mathrm{\notin }P$ satisfy $j>i_k$; put $U:=t_{j+1}\cdots t_r$ and $t:=U^{-1}{t}_{j}U\in T$. Writing $A:={\prod }_{p<j,p\mathrm{\notin }P}{t}_p$ one has $a=A{t}_{j}U$, because every position above $j$ is retained; hence $at=A{t}_{j}U{U}^{-1}{t}_{j}U=A{t}_j^{2}U=AU$, where we used $t_j^2=1$, and $AU$ is the product of $t_1\cdots t_r$ with the positions $P\cup \{j\}$ deleted, a word of length $r-k-1=\mathrm{\ell }(a)-1$. Therefore $\mathrm{\ell }(at)\le \mathrm{\ell }(a)-1$.

Rank-two intervals have an increasing chain. Suppose $\mathrm{\ell }(b)-\mathrm{\ell }(a)=2$. By [F6] the element $a$ is the product of a reduced subword of $t_1\cdots t_r$ of length $r-2$, that is, of a word obtained by deleting exactly two positions; among all such deleted pairs choose $\{d_1<d_2\}$ with $d_2$ minimal, let $y$ be the product of the word obtained by deleting only $d_1$, and put $t:=(t_r\cdots t_{d_2+1})t_{d_2}(t_{d_2+1}\cdots t_r)\in T$. The augmentation lemma applied to this reduced subword expression gives $y=at$, that the deletion word of $y$ is a reduced expression of $y$ of length $\mathrm{\ell }(a)+1=r-1$, and that $a\to y$, so $a$ is covered by $y$ by [F4]. Moreover $y\le b$ by [F6], and $\mathrm{\ell }(y)=r-1=\mathrm{\ell }(b)-1$, so $y$ is covered by $b$ by [F4]. Hence $(b,y,a)$ is a maximal chain of $([a,b],c)$ and its label word is $(d_1,d_2)$, which is increasing.

Lexicographic minimality of prefix and suffix. Let $m\text{\hspace{0.17em}⁣}:b=m_0⋗\cdots ⋗m_k=a$ be a lexicographically minimal maximal chain of $([a,b],c)$; it exists because the set of maximal chains of $[a,b]$ is finite [F7] and nonempty, and $\prec$ is a linear order on label words. Then the prefix $m_0⋗\cdots ⋗m_{k-1}$ is lexicographically minimal in the rooted interval $([m_{k-1},b],c)$: its entries are the first $k-1$ entries of $\lambda (m)$, computed from the same root chain $c$ [F2], so if a maximal chain $n$ of that rooted interval had a smaller label word, then the chain obtained by appending the cover $m_{k-1}⋗a$ would be a maximal chain of $([a,b],c)$ whose label word begins with $\lambda (n)$ and hence is lexicographically smaller than $\lambda (m)$, a contradiction. Likewise the suffix $m_1⋗\cdots ⋗m_k$ is lexicographically minimal in the rooted interval $([a,m_1],c\cup \{m_0⋗m_1\})$: prepending the cover $m_0⋗m_1$ to a competing maximal chain $n^{\mathrm{\prime }}$ there produces a maximal chain of $([a,b],c)$ whose label word is $({\lambda }_1(m),\lambda (n^{\mathrm{\prime }}))$, smaller than $\lambda (m)$ whenever $\lambda (n^{\mathrm{\prime }})$ is smaller than $({\lambda }_2(m),\dots ,{\lambda }_k(m))$.

At most one increasing chain. Suppose $m,m^{\mathrm{\prime }}$ are maximal chains of $([a,b],c)$ with increasing label words $(i_1<\cdots <i_k)$ and $(j_1<\cdots <j_k)$; we prove $i_k=j_k$, the claim then following by induction on $k=\mathrm{\ell }(b)-\mathrm{\ell }(a)$ applied to the rooted interval $([m_{k-1},b],c)$ of rank $k-1$. Assume $i_k<j_k$. Then $a=m_k$ is the product of $t_1\cdots t_r$ with the positions $i_1,\dots ,i_k$ deleted, and step 1.1 applied to that deleted set and the position $j:=j_k>i_k$ gives $\mathrm{\ell }(at)\le \mathrm{\ell }(a)-1$ for $t:=(t_r\cdots t_{j_k+1})t_{j_k}(t_{j_k+1}\cdots t_r)$. On the other hand, the retained expression of $m_{k-1}^{\mathrm{\prime }}$ is $t_1\cdots t_r$ with the positions $j_1,\dots ,j_{k-1}$ deleted, and the cover $m_{k-1}^{\mathrm{\prime }}⋗a$ deletes the further position $j_k$; since every position above $j_k$ is retained, [F3] exhibits $a=m_{k-1}^{\mathrm{\prime }}t$ with this same reflection $t$, so $m_{k-1}^{\mathrm{\prime }}=at$. But $\mathrm{\ell }(m_{k-1}^{\mathrm{\prime }})=\mathrm{\ell }(a)+1$ because $m_{k-1}^{\mathrm{\prime }}$ covers $a$ [F4], contradicting $\mathrm{\ell }(at)\le \mathrm{\ell }(a)-1$. Hence $i_k\ge j_k$, the same argument with $m$ and $m^{\mathrm{\prime }}$ interchanged gives $j_k\ge i_k$, and therefore $i_k=j_k$; then $m_{k-1}=m_{k-1}^{\mathrm{\prime }}=at$, and the two prefixes are maximal chains of the same rooted interval $([m_{k-1},b],c)$ whose increasing label words are $(i_1,\dots ,i_{k-1})$ and $(j_1,\dots ,j_{k-1})$, so the induction hypothesis applied to that rooted interval forces the prefixes to coincide. The case $k\le 1$ is vacuous: a rank-zero interval has one chain and a rank-one interval has at most one maximal chain.

The falling chain by inversion. Apply the argument of step 1.2 to the inverted configuration: the element $b^{-1}$ with the reversed reduced expression $t_r\cdots t_1$ [F9], the interval $[a^{-1},b^{-1}]$ [F8] and the inverted root chain; inversion is an order isomorphism [F8] and mirrors positions by $p\mapsto r+1-p$, so it produces a maximal chain $b⋗z⋗a$ of $([a,b],c)$ whose deleted pair is $\{f_1<f_2\}$ with $f_1$ maximal among the deleted pairs of $t_1\cdots t_r$, and whose label word is $(f_2,f_1)$, which is falling.

At most one falling chain. If two maximal chains of $([a,b],c)$ had falling label words, then their inverses would be two maximal chains of the inverted rooted interval $([a^{-1},b^{-1}],c^{-1})$ of $[u^{-1},v^{-1}]$ whose label words are increasing under the position mirror $p\mapsto r+1-p$ [F8, F9]; step 2.1 applied to that rooted interval (which is an instance of the same statement) would force the two inverted chains to coincide, hence the two original chains to coincide.

The rank-two diamond. Suppose $\mathrm{\ell }(b)-\mathrm{\ell }(a)=2$. Every maximal chain of $([a,b],c)$ has two steps and a label word with two distinct entries [F1], hence its word is increasing or falling [F10]; by steps 2.1 and 3.1 there is at most one maximal chain of each kind, so the chains $(b,y,a)$ of step 1.2 and $(b,z,a)$ of step 2.2 are all of them, provided they are distinct. If they coincided, then their label words $(d_1,d_2)$ and $(f_2,f_1)$ would coincide, forcing $d_1=f_2$ and $d_2=f_1$, hence $d_1<d_2=f_1<f_2=d_1$, a contradiction; so the two chains are distinct and $[a,b]$ has exactly two maximal chains. Writing $i:=d_1$, $j:=d_2$, $p:=f_2$ and $m:=f_1$ gives $i<j$, $m<p$, the increasing word $(i,j)$ of the first chain and the falling word $(p,m)$ of the second, and $j\le p$ because $d_2$ was chosen minimal among all deleted pairs while $\{f_1,f_2\}$ is a deleted pair. Finally, a rank-one element of the graded interval $[a,b]$ is the middle element $b⋗x⋗a$ of exactly one maximal chain, so the two distinct middle elements $y,z$ are the only ones, and $[a,b]$ has exactly four elements.

The lexicographically first chain is the unique increasing chain. Induct on the rank $k$. For $k\le 1$ the sole maximal chain is increasing and lexicographically first. For $k=2$, step 4.1 gives exactly the two words $(i,j)$ and $(p,m)$ with $i<j\le p$, so $(i,j)\prec (p,m)$ and the lexicographically first chain is increasing. For $k\ge 3$, let $m$ be a lexicographically minimal maximal chain of $([a,b],c)$; by step 1.3 its prefix and suffix are lexicographically minimal in rooted intervals of rank $k-1$, so their words are increasing by induction. These words cover all adjacent pairs of entries of $\lambda (m)$, so $\lambda (m)$ is increasing. Step 2.1 gives uniqueness, proving (iii).

Local descent replacement. Let $m\text{\hspace{0.17em}⁣}:b=m_0⋗\cdots ⋗m_k=a$ and $1\le e<k$ with ${\lambda }_e(m)>{\lambda }_{e+1}(m)$; let $c_m$ be $c$ extended by $m_0⋗\cdots ⋗m_{e-1}$ and consider the rooted rank-two interval $([m_{e+1},m_{e-1}],c_m)$. Its maximal chains are the segment $m_{e-1}⋗m_e⋗m_{e+1}$, whose label word there is the falling $({\lambda }_e(m),{\lambda }_{e+1}(m))$, and the unique increasing chain $m_{e-1}⋗y⋗m_{e+1}$ with word $(i^{\mathrm{\prime }},j^{\mathrm{\prime }})$ satisfying $i^{\mathrm{\prime }}<j^{\mathrm{\prime }}\le {\lambda }_e(m)$, by step 4.1 (and step 5.1 for its uniqueness). Then $k^{\mathrm{\prime }}:=m_0⋗\cdots ⋗m_{e-1}⋗y⋗m_{e+1}⋗\cdots ⋗m_k$ is a maximal chain of $([a,b],c)$: it has the same number of steps as $m$ and each of its steps is a cover, and $y\mathrm{\ne }{m}_e$ because the increasing chain is distinct from the segment. Only the element in position $e$ changed, so $k^{\mathrm{\prime }}\cap m=m\setminus \{m_e\}$; the labels of $k^{\mathrm{\prime }}$ above $m_{e-1}$ equal those of $m$ because the root chain $c_m$ is the same, and its label at position $e$ is $i^{\mathrm{\prime }}<{\lambda }_e(m)$, so the first differing entry of the two label words is at position $e$ and $\lambda (k^{\mathrm{\prime }})\prec \lambda (m)$.

Conditions (N) and (L). For $n\le 1$ the interval has a single maximal chain by [F9], whose empty or one-entry word is increasing, lexicographically first, and has no repeated entry. For $n\ge 2$, by [F1] the labels of any maximal chain of a rooted interval are pairwise distinct, which is (N). By [F5] every rooted interval of $[u,v]$ has exactly one increasing maximal chain and its label word is lexicographically first among the maximal chains of that rooted interval, which is (L). This proves (i); the rooted intervals of $[u,v]$ with their induced labeling are exactly the rooted intervals to which [F2] attaches the deleted-position labels.

The label word determines the chain. Let $m$ be a maximal chain of a rooted interval with retained expression $t_1\cdots t_r$. By the recursion of [F1], each element $m_i$ is the product of $t_1\cdots t_r$ with the positions ${\lambda }_1(m),\dots ,{\lambda }_i(m)$ deleted, so the label word determines every element of $m$ and hence the chain; consequently distinct maximal chains have distinct label words, and the lexicographic order of label words is a linear order on the maximal chains.

Small ranks. If $u=v$ there is no element $x$ with $u<x<u$, and if $n=1$ there is no $x$ with $u<x<v$, because such an $x$ would satisfy $\mathrm{\ell }(u)<\mathrm{\ell }(x)<\mathrm{\ell }(v)$ [F10] while $\mathrm{\ell }(v)=\mathrm{\ell }(u)+1$; so $(u,v)$ is empty, its order complex has the single facet $\mathrm{\varnothing }$ [F4], and the shelling condition of [F3] is vacuous for a one-facet complex. If $n=2$, then $[u,v]$ has exactly four elements [F6], the open interval consists of the two middle elements, which have the same length $\mathrm{\ell }(u)+1$ and are therefore incomparable [F10], and $\mathrm{\Delta }((u,v))$ has the two facets $\{a\},\{b\}$, the empty set and the two singletons being the only chains of a two-element antichain; listing the facets in either order, say $F_1=\{a\}$, $F_2=\{b\}$, the criterion of [F3] holds for $i=1$, $k=2$ with $j=1$ and the vertex $b$ of $F_2$, because $F_1\cap F_2=\mathrm{\varnothing }=F_2\setminus \{b\}$.

Earlier/later chain comparison. By step 1.1 the deleted-position labeling of $[u,v]$ satisfies (N) and (L) on every rooted interval, and by [F9] the poset $[u,v]$ is finite and graded with the covering relation of [F9]; these are exactly the hypotheses of the abstract comparison lemma [F7], which therefore yields, for all maximal chains $m^{\mathrm{\prime }},m$ of $[u,v]$ with $\lambda (m^{\mathrm{\prime }})\prec \lambda (m)$, a maximal chain $k$ with $\lambda (k)\prec \lambda (m)$, $m^{\mathrm{\prime }}\cap m\subseteq k\cap m$ and $\mathrm{\mid }k\cap m\mathrm{\mid }=\mathrm{\mid }m\mathrm{\mid }-1$. In that argument $k$ is obtained by replacing a two-step segment at a descent position by the increasing chain of the corresponding rooted rank-two interval, which is the local descent replacement of At most one increasing chain, rank-two diamonds, the lexicographically first chain, and the local descent replacement (iv).

Shelling of the open interval. For $n\le 1$ the conclusion is step 1.3. Suppose $n\ge 2$ and put $E:=\{u,v\}$ and $F_m:=m\setminus E$ for each maximal chain $m$ of $[u,v]$. Every maximal chain of $(u,v)$ becomes maximal in $[u,v]$ upon adjoining the endpoints, and conversely: any missing intermediate element would enlarge either chain. Thus $m\mapsto F_m$ is a bijection onto the facets of $\mathrm{\Delta }((u,v))$ by [F4]. Give $F_m$ the label word of its endpoint extension $m$; this orders the facets linearly by step 1.2. For $m^{\mathrm{\prime }}\prec m$, step 2.1 supplies $k\prec m$ with $m^{\mathrm{\prime }}\cap m\subseteq k\cap m=m\setminus \{z\}$ for one vertex $z$ of $m$; the cardinality equality there gives the last equality, and $z\mathrm{\notin }E$ since both endpoints lie in every chain. Removing $E$ yields $F_{m^{\mathrm{\prime }}}\cap F_m\subseteq F_k\cap F_m=F_m\setminus \{z\}$, and explicitly $\mathrm{\mid }{F}_k\cap F_m\mathrm{\mid }=\mathrm{\mid }k\cap m\mathrm{\mid }-2=\mathrm{\mid }m\mathrm{\mid }-3=\mathrm{\mid }{F}_m\mathrm{\mid }-1$. This is exactly [F3], proving (iii); (ii) is step 2.1 and (iv) is step 1.3.