Words, heaps, linear extensions, commutation classes, and fully commutative elements

Let $(S,m)$ be a finite Coxeter matrix and let $W$ be the group presented by it, with length $\mathrm{\ell }$ and set $\mathcal{R}(w)$ of reduced expressions, so that $m(s,t)$ is the order of $st$ in $W$ (Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups).

(1) Words. A word in $S$ is a finite sequence $s=(s_1,\dots ,s_k)$ with $s_i\in S$. Its length is $k$, it represents the element $s_1\cdots s_k\in W$, and concatenation of words represents the product of the represented elements. A word is reduced when it is a reduced expression of the element it represents, so $\mathcal{R}(w)$ is the set of all reduced words representing $w$.

(2) The heap of a word. Let $s=(s_1,\dots ,s_k)$ be a word and put $[k]=\{1,\dots ,k\}$. Write $i{\prec }_{s}j$ when $i<j$ and either $s_i=s_j$ or $m(s_i,s_j)\ge 3$ (including $m(s_i,s_j)=\mathrm{\infty }$); thus $i{\prec }_{s}j$ exactly when $i<j$ and the pair $s_i,s_j$ is not a commuting pair, i.e. $m(s_i,s_j)\mathrm{\ne }2$. Let ${⪯}_s$ be the reflexive transitive closure of ${\prec }_s$. Every relation ${\prec }_s$ has $i<j$, so ${⪯}_s$ is contained in the usual order of the positions and is antisymmetric; hence ${⪯}_s$ is a partial order on $[k]$ (Partial order and partially ordered set). The heap of $s$ is the labeled poset $P_s:=([k],{⪯}_s)$ in which the position $i$ carries the label $s_i$. Elements of a heap with the same label are pairwise comparable: if $i<j$ and $s_i=s_j$, then $i{\prec }_{s}j$.

(3) Labeled heaps and labeled isomorphism. A labeled poset is a triple $(P,⪯,\lambda )$ in which $(P,⪯)$ is a finite poset and $\lambda :P\to S$ is a map. Two labeled posets $(P,⪯,\lambda )$ and $(P^{\mathrm{\prime }},{⪯}^{\mathrm{\prime }},{\lambda }^{\mathrm{\prime }})$ are isomorphic when there is a bijection $\phi :P\to P^{\mathrm{\prime }}$ with $x⪯y⟺\phi (x){⪯}^{\mathrm{\prime }}\phi (y)$ for all $x,y\in P$ and ${\lambda }^{\mathrm{\prime }}(\phi (x))=\lambda (x)$ for all $x\in P$. A labeled poset is a heap (for $(S,m)$) when it is isomorphic to $P_s$ for some word $s$.

(4) Linear extensions. Let a linear extension of a finite poset be as in Linear extensions of a finite poset. For a word $s$ of length $k$, the labeled linear extensions of $P_s$ are the words $L(P_s,s):=\{(s_{x_1},\dots ,s_{x_k}):(x_1,\dots ,x_k)\text{ is a linear extension of }{P}_s\}\mathrm{.}$

(5) Commutativity classes. Two words $s,s^{\mathrm{\prime }}$ of the same length are commutation-equivalent, written $s\sim s^{\mathrm{\prime }}$, when $s^{\mathrm{\prime }}$ is obtained from $s$ by finitely many interchanges of two adjacent letters $s_i,s_{i+1}$ with $m(s_i,s_{i+1})=2$. This is an equivalence relation on words: it is generated by the single interchanges, which are involutions, and it is by construction closed under composition. The commutativity class of $s$ is $C(s):=\{s^{\mathrm{\prime }}:s^{\mathrm{\prime }}\sim s\}$. Commutation-equivalent words have the same length, the same multiplicity of every letter, and represent the same element of $W$: an interchange of adjacent letters with $m(s_i,s_{i+1})=2$ changes neither the length nor the multiplicities, and the represented element is unchanged because $st=ts$ in $W$ whenever $m(s,t)=2$; indeed, $s^2=t^2=1$ and $(st{)}^2=1$ imply $st=(st{)}^{-1}=t^{-1}{s}^{-1}=ts$ (Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups).

(6) Fully commutative elements. An element $w\in W$ is fully commutative when all its reduced words lie in a single commutativity class, that is, when $\mathcal{R}(w)=C(s)$ for one (equivalently, every) $s\in \mathcal{R}(w)$.

(7) Abstentions and conventions. The heap is defined for an arbitrary, not necessarily reduced, word. Nothing is asserted here about the relation between $\mathcal{R}(w)$ and $L(P_s,s)$, about invariance of $P_s$ under commutation, or about which elements are fully commutative; those are the content of Labeled linear extensions of a heap are exactly the words in its commutativity class, and heaps classify commutativity classes ↗ and Fully commutative elements: the braid-factor criterion and the forbidden-chain heap criterion. All data are finite and no Choice is used.