Deleted-position labels from a fixed reduced expression, the lexicographic shelling criterion, and Möbius data

Let $W$ be the group presented by a Coxeter matrix $(S,m)$, with length function $\mathrm{\ell }$, reflection set $T$ and Bruhat order $\le$ (Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups, The canonical reflection homomorphism, roots, reflections, and the positive cone, The Bruhat graph by length-increasing reflection chains, the Bruhat order, inversion symmetry, and reflection parity). Let $u\le v$ in $W$ and fix a reduced expression $v=s_1\cdots s_q$, where $q=\mathrm{\ell }(v)$.

(1) Maximal chains. By Finiteness of Bruhat intervals, the chain refinement property, and grading by length the interval $[u,v]=\{x\in W:u\le x\le v\}$ (Intervals in a poset; locally finite, lower-finite and upper-finite posets) is finite and graded with rank function $x\mapsto \mathrm{\ell }(x)-\mathrm{\ell }(u)$ (Graded poset, rank function, and rank levels); a maximal chain of $[u,v]$ is a chain of covers $m\text{\hspace{0.17em}⁣}:v=x_0⋗x_1⋗\cdots ⋗x_k=u$ with $k=\mathrm{\ell }(v)-\mathrm{\ell }(u)$, where $⋗$ is the covering relation of Graded poset, rank function, and rank levels.

(2) The deleted-position labeling. Let $m\text{\hspace{0.17em}⁣}:v=x_0⋗x_1⋗\cdots ⋗x_k=u$ be a maximal chain of $[u,v]$. Recursively, suppose that $P_j\subseteq \{1,\dots ,q\}$ satisfies $\mathrm{\mid }{P}_j\mathrm{\mid }=q-j$ and that $x_j={\prod }_{p\in P_j}{s}_p$ (product in increasing order of positions) is a reduced expression of $x_j$. By the cover criterion and reflection deletion of The lifting property in all four descent cases, the cover criterion, reflection deletion, and directedness (3), applied to the reduced expression $x_j={\prod }_{p\in P_j}{s}_p$, the cover $x_j⋗x_{j+1}$ determines a unique position ${\lambda }_{j+1}(m)\in P_j$ with $x_{j+1}={\prod }_{p\in P_j\setminus \{{\lambda }_{j+1}(m)\}}{s}_p$, and this deletion word is a reduced expression of $x_{j+1}$; put $P_{j+1}:=P_j\setminus \{{\lambda }_{j+1}(m)\}$. This defines the label word $\lambda (m)=({\lambda }_1(m),\dots ,{\lambda }_k(m))$ of $m$. Its entries are pairwise distinct, because $P_0⊋P_1⊋\cdots ⊋P_k$. Hence $m\mapsto \lambda (m)$ is a descending rooted-chain labeling of $[u,v]$ in the sense of Finite lattice congruences, interval endpoints and descending rooted-chain labels (2), with values in the linearly ordered set $\{1,\dots ,q\}$: a label is determined by the chain above its step and need not be a function of that step alone. The notions increasing, falling, descent set and the lexicographic order $\prec$ of label words are those of Finite lattice congruences, interval endpoints and descending rooted-chain labels (3).

(3) Rooted intervals. If $u\le a<b\le v$ and $c$ is a descending chain from $v$ to $b$, the induced labeling of the rooted interval $([a,b],c)$ (Finite lattice congruences, interval endpoints and descending rooted-chain labels (2)) is again a deleted-position labeling of $[a,b]$: its labels are positions in the reduced expression of $b$ obtained from $v=s_1\cdots s_q$ by deleting the positions of the steps of $c$, and the label of a step of a maximal chain of $[a,b]$ is the position of the letter it deletes from that retained expression. Labels compared inside one rooted interval therefore belong to the one ordered set $\{1,\dots ,q\}$. The labeling depends on the fixed reduced expression of $v$; no two label words obtained from different fixed expressions are compared anywhere on this page.

(4) The lexicographic shelling criterion. Let $K$ be a finite abstract simplicial complex (An abstract simplicial complex) whose facets — its maximal simplices under inclusion — are listed in a linear order $F_1,\dots ,F_t$. The order is a shelling of $K$, and $K$ is shellable, if for all $i<k$ there are $j<k$ and a vertex $x\in F_k$ with $F_i\cap F_k\subseteq F_j\cap F_k=F_k\setminus \{x\}$; this is the exact earlier-facet codimension-one intersection criterion. The facets of the order complex $\mathrm{\Delta }([u,v])$ of $[u,v]$ are the maximal chains of $[u,v]$, and those of $\mathrm{\Delta }((u,v))$ are the maximal chains of the open interval $(u,v)$ (Face poset and order complex). The lexicographic order of maximal chains of $[u,v]$ is $m^{\mathrm{\prime }}\prec m:⟺\lambda (m^{\mathrm{\prime }})\prec \lambda (m)$.

(5) Möbius data. $\mu$ denotes the Möbius function of a finite poset (The integer-valued Möbius function ${\mu }_P$ of a locally finite poset), so that on $[u,v]$ one has $\mu (x,x)=1$ and $\mu (x,y)=-{\sum }_{x\le z<y}\mu (x,z)$ for $x<y$ (The Möbius recurrence: ${\mu }_P(x,x)=1$ and both interval sums of ${\mu }_P$ vanish when $x<y$).

This item asserts neither that the labeling satisfies the no-tie condition (N) or the lex-increasing property (L) of Finite lattice congruences, interval endpoints and descending rooted-chain labels (4), nor that the lexicographic order is a shelling; both are proved in Deletion-labeled Bruhat intervals are lexicographically shellable, with the explicit earlier/later chain comparison ↗, the recorded justifier of this definition, before any consumer uses them.