Labeled linear extensions of a heap are exactly the words in its commutativity class, and heaps classify commutativity classes

Three elementary facts about $P_s$. (i) The identity listing $(1,2,\dots ,k)$ is a linear extension of $P_s$, since every generating relation $i{\prec }_{s}j$ satisfies $i<j$; its labeled word is $s$. (ii) Let $\pi$ be a linear extension of $P_s$ and let $x,y$ be consecutive entries. If $m(s_x,s_y)=2$, then the labels are distinct by $m(s,s)=1$, and neither orientation is a generating relation. If $x,y$ were comparable in the transitive closure, a generating path between them would have an intermediate position; that position must occur between $x$ and $y$ in every linear extension, a contradiction. Thus they are incomparable. Conversely, if they are comparable, orient them so $x{<}_{P_s}y$. Their consecutiveness in $\pi$ means no position lies strictly between them, so they form a cover. Since the order is generated by the defining relations, a cover must itself be a generating pair: a path of length at least two would have an intermediate position. Hence $s_x=s_y$ or $m(s_x,s_y)\ge 3$, so $m(s_x,s_y)\mathrm{\ne }2$. Therefore consecutive entries are incomparable exactly when their labels commute, and swapping them preserves the linear-extension property exactly in that case. (iii) If $s_i=s_j$ with $i<j$, then $i{\prec }_{s}j$, so for each $u\in S$ the positions carrying label $u$ form a chain, listed in increasing position order.

If $s^{\mathrm{\prime }}$ is obtained from $s$ by interchanging adjacent letters $s_i,s_{i+1}$ with $m(s_i,s_{i+1})=2$, transpose positions $i$ and $i+1$ and fix all others. The transposition preserves labels. It preserves every generating relation between positions outside the transposed pair because those positions lie either before both or after both; for a pair involving one transposed position and an outside position, the relative position order and the label dependence are unchanged after transporting the position. The transposed pair itself has no generating relation, and no path can relate it because the two positions are adjacent in the word. Thus the transposition preserves the generating relation in both directions, hence its reflexive transitive closure, and is a labeled poset isomorphism $P_s\to P_{s^{\mathrm{\prime }}}$. Composing these maps shows that $s\sim s^{\mathrm{\prime }}$ implies the heaps are isomorphic.

Clause (1), the inclusion $C(s)\subseteq L(P_s,s)$. Every word of $C(s)$ is the labeled word of some linear extension of $P_s$; this is proved by induction on the number of interchanges. It holds for $s$ by 1.1(i). If $u\in C(s)$ is the labeled word of a linear extension $\pi$ of $P_s$ and $u^{\mathrm{\prime }}$ differs from $u$ by interchanging adjacent letters $u_j,u_{j+1}$ with $m(u_j,u_{j+1})=2$, then the $j$-th and $(j+1)$-st entries $x,y$ of $\pi$ are consecutive with labels $u_j,u_{j+1}$, hence are incomparable by 1.1(ii), so interchanging them in $\pi$ gives a linear extension of $P_s$ whose labeled word is $u^{\mathrm{\prime }}$.

Clause (1), the inclusion $L(P_s,s)\subseteq C(s)$. Let $\pi$ be a linear extension of $P_s$ with labeled word $u$. By [F4], $\pi$ is obtained from the identity listing by finitely many interchanges of consecutive entries incomparable in $P_s$; by 1.1(ii) each of these interchanges replaces the current labeled word by a word differing in one interchange of adjacent commuting letters, and the labeled word of the identity listing is $s$ by 1.1(i). Hence $u\sim s$, that is, $u\in C(s)$.

Clause (2). Fix $u\in S$. By 1.1(iii) the positions with label $u$ form a chain of $P_s$, and a linear extension lists them in increasing position order, so the $j$-th occurrence of $u$ in the labeled word of a linear extension is the $j$-th element of that chain; two linear extensions with the same labeled word therefore coincide entry by entry, and the map from linear extensions of $P_s$ to words is injective. By 2.1 and 2.2, $L(P_s,s)=C(s)$, so the number of words of $C(s)$ equals the number of linear extensions of $P_s$; thus $C(s)$ is finite, and since every linear extension lists each position of the finite set $[k]$ exactly once, every member of $C(s)$ has length $k$ and contains each $u$ exactly as many times as the labeling $s$ does.

Clause (3), from an isomorphism to commutation equivalence. Let $\phi :P_s\to P_{s^{\mathrm{\prime }}}$ be a labeled isomorphism of posets. Since it is a bijection, $s$ and $s^{\mathrm{\prime }}$ have the same length $k$. With labels $\lambda (i)=s_i$ and ${\lambda }^{\mathrm{\prime }}(j)=s_j^{\mathrm{\prime }}$, the listing $\rho :=({\phi }^{-1}(1),{\phi }^{-1}(2),\dots ,{\phi }^{-1}(k))$ is a linear extension of $P_s$: if $x{<}_{P_s}y$, then $\phi (x){<}_{P_{s^{\mathrm{\prime }}}}\phi (y)$, so $\phi (x)$ occurs before $\phi (y)$ in the identity listing of $P_{s^{\mathrm{\prime }}}$, and hence $x$ occurs before $y$ in $\rho$. Its labeled word is $(\lambda ({\phi }^{-1}(1)),\dots ,\lambda ({\phi }^{-1}(k)))=({\lambda }^{\mathrm{\prime }}(1),\dots ,{\lambda }^{\mathrm{\prime }}(k))=s^{\mathrm{\prime }}$, by label preservation. Therefore $s^{\mathrm{\prime }}\in L(P_s,s)\subseteq C(s)$ by 2.2, so $s^{\mathrm{\prime }}\sim s$.

Every labeled isomorphism maps the $j$-th occurrence of each label $u$ to the $j$-th occurrence of $u$: the positions with label $u$ form a chain by 1.1(iii), and the isomorphism preserves its order. Together, steps 1.2 and 3.2 prove $s\sim s^{\mathrm{\prime }}$ exactly when $P_s$ and $P_{s^{\mathrm{\prime }}}$ are isomorphic. In particular $s\mapsto P_s$ is well defined and injective on commutativity classes.

For any labeled heap $H=(P,⪯,\lambda )$, its labeled linear extensions are the words $(\lambda (x_1),\dots ,\lambda (x_n))$ as $(x_1,\dots ,x_n)$ ranges over the linear extensions of $P$. By definition of heap, choose a labeled isomorphism $H\to P_q$ for some word $q$. It transports linear extensions and preserves labels, so the labeled linear extensions of $H$ form exactly $L(P_q,q)=C(q)$ by clause (1). If another word $q^{\mathrm{\prime }}$ represents $H$, then $P_q$ and $P_{q^{\mathrm{\prime }}}$ are isomorphic, so 4.1 gives $q\sim q^{\mathrm{\prime }}$ and $C(q)=C(q^{\mathrm{\prime }})$. Thus the assignment is surjective onto labeled heaps up to isomorphism, and its inverse is the set of labeled linear extensions.

Clause (4). Let $w\in W$ and $s,s^{\mathrm{\prime }}\in \mathcal{R}(w)$ with $s\sim s^{\mathrm{\prime }}$. By 4.1 there is a labeled isomorphism $P_s\to P_{s^{\mathrm{\prime }}}$. If $w$ is fully commutative, then all its reduced words lie in one commutativity class, so any two of them are related by such isomorphisms. Therefore the isomorphism class of $P_s$ is independent of the reduced word $s$, defining the heap $P_w$.