Heaps, Commutation Classes, and Fully Commutative Elements

Clause (1). Suppose that $P\mathrm{\ne }\mathrm{\varnothing }$ has no minimal element. Fix a listing $P=\{p_1,\dots ,p_n\}$ of the finite set and define a sequence by $x_0:=p_1$ and, given $x_k=x\in P$, let $j$ be the least index with $p_j\prec x$ (it exists because $x$ is not minimal) and put $x_{k+1}:=p_j$. This recursion is well defined on $\mathbb{N}$ using only the order of the indices. It satisfies $x_{k+1}\prec x_k$ for every $k$, so for $i<j$ transitivity gives $x_j\prec x_i$, in particular $x_i\mathrm{\ne }{x}_j$; the infinite sequence therefore has pairwise distinct terms, contradicting the finiteness of $P$. Hence some element of $P$ is minimal.

Two basic facts about linear extensions. (i) Every finite poset $Q$ has a linear extension: if $Q=\mathrm{\varnothing }$ take the empty tuple, and otherwise repeatedly remove a minimal element of the induced poset on the remaining set, which exists by clause (1) applied to that nonempty finite subposet, and list the removed elements in their order of removal; if $a\prec b$ in $Q$ and $b$ were removed before $a$, then at the moment $b$ was removed the element $a$ still belonged to the remaining set and satisfied $a\prec b$, contradicting minimality of $b$ there. (ii) If $(z_1,\dots ,z_r)$ is a linear extension of $Q$ and the consecutive entries $z_i,z_{i+1}$ are incomparable in $Q$, then interchanging them yields a linear extension: every pair of entries other than $\{z_i,z_{i+1}\}$ keeps its relative order, and the pair $\{z_i,z_{i+1}\}$ is incomparable, so no order relation is violated.

Clause (2). Let $\tau =(y_1,\dots ,y_{n-m})$ be a linear extension of the induced poset on $P\setminus I$, which exists by step 2.1(i) since $P\setminus I$ is a finite poset. The concatenation $\pi =(x_1,\dots ,x_m,y_1,\dots ,y_{n-m})$ is a linear extension of $P$: within each block the order of the respective induced poset is respected, and a relation crossing the blocks would have to run from the second block to the first, of the form $y_j\prec x_i$; but $x_i\in I$, so the ideal property would give $y_j\in I$, contradicting $y_j\in P\setminus I$. Hence $\sigma$ extends to a linear extension $\pi$ of $P$ whose first $m$ entries are exactly the elements of $I$, and applying the same concatenation to an arbitrary linear extension $\tau$ of the induced poset on $P\setminus I$ gives the dual assertion of clause (2). In particular step 2.1(i) proves the first sentence of clause (2).

Clause (3), the reduction. Let $\pi$ and $\sigma$ be linear extensions of $P$ and let $a$ be the last entry of $\pi$. Then $a$ is maximal in $P$: if $a\prec y$ for some $y\in P$, then $y$ occurs after $a$ in $\pi$, contradicting that $a$ is last. Every entry occurring after $a$ in $\sigma$ is incomparable with $a$: if $y\prec a$ then $y$ occurs before $a$ in $\sigma$, and if $a\prec y$ then $a$ is not maximal. Consequently moving $a$ to the last position of $\sigma$ by successively interchanging it with the entry immediately to its right is a sequence of interchanges of consecutive incomparable entries, each of which yields a linear extension by step 2.1(ii); the resulting list ${\sigma }_1$ is a linear extension of $P$ ending in $a$, obtained from $\sigma$ by finitely many such interchanges.

Clause (3), the induction. Induct on $n=\mathrm{\mid }P\mathrm{\mid }$: for $n=0$ both linear extensions are empty and no interchange is needed. For $n\ge 1$ let $\pi$, $\sigma$, $a$ and ${\sigma }_1$ be as in step 3.2, and delete the common last entry $a$ from $\pi$ and ${\sigma }_1$. The resulting tuples ${\pi }^{\mathrm{\prime }}$ and ${\sigma }_1^{\mathrm{\prime }}$ are linear extensions of the induced poset on $Q:=P\setminus \{a\}$, a finite poset with $n-1<n$ elements, so by the induction hypothesis ${\sigma }_1^{\mathrm{\prime }}$ is obtained from ${\pi }^{\mathrm{\prime }}$ by finitely many interchanges of consecutive entries that are incomparable in $Q$. Two elements of $Q$ are comparable in $Q$ exactly when they are comparable in $P$, so each of these interchanges is also an interchange of consecutive entries incomparable in $P$, and inserting them into $\pi$ and ${\sigma }_1$ produces linear extensions of $P$. Hence $\pi$ is connected to ${\sigma }_1$ by such interchanges, and step 3.2 connects ${\sigma }_1$ to $\sigma$; thus $\sigma$ is obtained from $\pi$ by finitely many interchanges of consecutive entries that are incomparable in $P$.

Setup. Enumerate the nonempty chain $C$ in increasing order as $C=\{c_1\prec c_2\prec \cdots \prec c_m\}$, and set $Q:=(P\setminus C)\cup \{\ast \}$ for a new element $\ast \mathrm{\notin }P$. Let $R$ be the relation on $Q$ consisting of the pairs $(x,y)$ with $x,y\in P\setminus C$ and $x\prec y$, the pairs $(x,\ast )$ with $x\in P\setminus C$ and $x\prec c$ for some $c\in C$, and the pairs $(\ast ,y)$ with $y\in P\setminus C$ and $c\prec y$ for some $c\in C$. Let ${⪯}_Q$ be the reflexive transitive closure of $R$, so ${⪯}_Q$ is reflexive and transitive by construction.

The relation ${⪯}_Q$ is antisymmetric. A cycle of $R$ whose vertices lie in $P\setminus C$ would produce $x_1\prec x_2\prec \cdots \prec x_1$ in the poset $P$, impossible by transitivity and antisymmetry; so every nontrivial cycle passes through $\ast$, and between two consecutive occurrences of $\ast$ it consists of an edge $(\ast ,y)$, a path inside $P\setminus C$ from $y$ to an element $x$, and an edge $(x,\ast )$. By the definition of $R$ there are then $c^{\mathrm{\prime }},c\in C$ with $c^{\mathrm{\prime }}\prec y$ and $x\prec c$, and the path inside $P\setminus C$ gives $y⪯x$; hence $c^{\mathrm{\prime }}⪯y⪯x⪯c$. Since $c^{\mathrm{\prime }},c\in C$ and $C$ is convex, this forces $x\in C$, contradicting $x\in P\setminus C$. Therefore $R$ has no nontrivial cycles, and ${⪯}_Q$ is a partial order on the finite set $Q$.

By [F4] the finite poset $Q$ has a linear extension ${\pi }_Q=(u_1,\dots ,u_r)$; let $\pi$ be the tuple obtained from ${\pi }_Q$ by replacing the one occurrence of $\ast$ with the block $(c_1,\dots ,c_m)$. Then $\pi$ lists every element of $P$ exactly once. It is a linear extension of $P$: if $x\prec y$ with $x,y\in P\setminus C$ then $x{⪯}_{Q}y$, so $x$ precedes $y$ in $\pi$; if $x\in P\setminus C$ and $x\prec c_i$ then $(x,\ast )\in R$, so $x$ precedes $\ast$ in ${\pi }_Q$ and hence precedes the whole block; if $c_i\prec y$ with $y\in P\setminus C$ then $(\ast ,y)\in R$, so the whole block precedes $y$; and the block itself lists $c_1,\dots ,c_m$ in increasing order, so it respects the relations inside $C$. Since $C$ exhausts the block, its elements occur consecutively in $\pi$.

In particular, let $x⋖y$ be a covering pair and put $C:=\{x,y\}$. Then $C$ is a nonempty chain, and it is convex: if $x⪯z⪯y$ with $z\in P$, then either $z=x$, or $z=y$, or $x\prec z\prec y$, which is excluded by [F3]; in all cases $z\in C$. So step 3.1 applies and yields a linear extension of $P$ in which $x$ and $y$ are consecutive.

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$.

Clause (1). Suppose first that some $s\in \mathcal{R}(w)$ contains the contiguous factor $F=⟨u,v{⟩}_m$ with $m:=m(u,v)\in [3,\mathrm{\infty })$, and let $s^{\ast }$ be obtained from $s$ by replacing $F$ with $⟨v,u{⟩}_m$. By [F2], $s^{\ast }$ represents $w$ and has the same length, so $s^{\ast }\in \mathcal{R}(w)$. Delete from a word all letters outside $\{u,v\}$; this projection is unchanged by every interchange of adjacent commuting letters, because such a pair consists of distinct letters with $m=2$, so either both letters lie outside $\{u,v\}$ and are deleted, or exactly one of them lies in $\{u,v\}$ and keeps its position among the surviving letters (both letters in $\{u,v\}$ is impossible since $m(u,v)\ge 3$). The projections have a common prefix and suffix outside the factor, while their middle blocks are the distinct alternating words $u,v,u,\dots$ and $v,u,v,\dots$; cancelling the common prefix and suffix shows that the full projections differ. Hence $s^{\ast }\mathrm{\notin }C(s)$, so $\mathcal{R}(w)$ is not a single commutativity class and $w$ is not fully commutative; this proves (a)$\Rightarrow$(b). Conversely, if $w$ is not fully commutative, choose $s,s^{\mathrm{\prime }}\in \mathcal{R}(w)$ with $s^{\mathrm{\prime }}\mathrm{\notin }C(s)$ and, by F3, a sequence of braid moves $s=q_0,q_1,\dots ,q_r=s^{\mathrm{\prime }}$; let $t$ be the first index with $q_t\mathrm{\notin }C(s)$. Then $q_{t-1}\in C(s)$ and the move $q_{t-1}\to q_t$ is not a commutation, so it replaces a contiguous factor $⟨x,y{⟩}_{m(x,y)}$ by $⟨y,x{⟩}_{m(x,y)}$ with $x\mathrm{\ne }y$ and $m(x,y)\ge 3$. The word $q_{t-1}$ is obtained from $s$ by braid moves, hence has length $k=\mathrm{\ell }(w)$ and represents $w$, so it is a reduced word of $w$ containing the forbidden factor; this proves (b)$\Rightarrow$(a).

Clause (2), (c)$\Rightarrow$(b). Assume $s$ is reduced and $w$ is fully commutative, so $C(s)=\mathcal{R}(w)$ by [F1]. If $P_s$ had a covering pair $i⋖j$ with $s_i=s_j$, then $\{i,j\}$ would be a two-element convex chain, so by [F4] some linear extension of $P_s$ has $i,j$ consecutive; its labeled word $s^{\mathrm{\prime }\mathrm{\prime }}$ lies in $L(P_s,s)=C(s)$ by [F5], hence in $\mathcal{R}(w)$, and contains two consecutive equal letters. Deleting those two letters gives an expression of $w$ with $k-2$ letters, because $s_i^2=1$ in $W$ by [F2], contradicting $\mathrm{\ell }(w)=k$. Hence (b) holds.

Clause (2), the braid class equals the commutation class under (a). Assume (a), and let $H(s)$ be the set of words obtained from $s$ by finitely many braid moves. Then $H(s)=C(s)$: otherwise choose a sequence of braid moves from $s$ to a word outside $C(s)$ with the fewest moves, so that its last move is applied to a word $q\in C(s)$ and leaves $C(s)$; that move is not a commutation, hence replaces a contiguous alternating factor $⟨x,y{⟩}_{m(x,y)}$, $x\mathrm{\ne }y$, $m(x,y)\ge 3$, of $q$. The positions of that factor form a chain in $P_q$, because consecutive positions of the factor carry the noncommuting pair $\{x,y\}$; they are convex, because the order of $P_q$ is contained in the position order, so an element lying between two positions of the factor is itself one of them. Thus $P_q$ contains a convex alternating chain of length $m(x,y)\ge 3$, and since $q\in C(s)$ gives $P_q\cong P_s$ by [F5] while containing such a chain is invariant under labeled isomorphism, condition (a) fails for $P_s$, a contradiction. Hence $H(s)=C(s)$.

Clause (2), (c)$\Rightarrow$(a). Assume $s$ is reduced and $w$ is fully commutative, so $C(s)=\mathcal{R}(w)$ by [F1]. If $P_s$ contained a convex chain with labels alternating between distinct $u,v$ of length $m=m(u,v)\in [3,\mathrm{\infty })$, then by [F4] some linear extension of $P_s$ has the chain's elements consecutive; its labeled word $s^{\mathrm{\prime }\mathrm{\prime }}$ lies in $L(P_s,s)=C(s)$ by [F5], hence in $\mathcal{R}(w)$, and its consecutive letters at those positions are the alternating factor $⟨u,v{⟩}_m$. This contradicts clause (1)(b), proved in step 1.1, so (a) holds.

Clause (2), (a) and (b) imply that $s$ is reduced. If $s$ were not reduced, then by F3 there is a sequence of braid moves from $s$ to a word $u$ containing a consecutive equal pair, so $u\in H(s)=C(s)$ by step 1.3. Hence $P_u\cong P_s$ by [F5]. The two consecutive equal positions of $u$ satisfy $i{\prec }_{u}i+1$; no element lies strictly between them, because the order of $P_u$ is contained in the position order and there is no integer strictly between $i$ and $i+1$; so they form a covering pair of $P_u$ with equal labels. Under the labeled isomorphism this gives a covering pair of $P_s$ with equal labels, contradicting (b). Hence $s$ is reduced.

Clause (2), conclusion of (a),(b)$\Rightarrow$(c). Assume (a) and (b). By step 2.2 the word $s$ is reduced, so $\mathrm{\ell }(w)=k$. Every word braid-equivalent to $s$ has length $k$, represents $w$ by [F2], and is therefore reduced; hence $H(s)$ consists of reduced words of $w$. By F3 every reduced word of $w$ is braid-equivalent to $s$, so $\mathcal{R}(w)\subseteq H(s)=C(s)$ by step 1.3, while conversely every member of $C(s)$ is obtained from $s$ by commutations and so has length $k$ and represents $w$, hence lies in $\mathcal{R}(w)$. Therefore $\mathcal{R}(w)=C(s)$ and $w$ is fully commutative; by [F5] this also gives $P_s\cong P_{s^{\mathrm{\prime }}}$ for every $s^{\mathrm{\prime }}\in \mathcal{R}(w)$.