Complexes of injective words and their commutation classes (Q1036223)

Let \(S\) be a finite alphabet. An injective word over \(S\) is a word over \(S\) such that each letter in \(S\) appears at most once in the word. For an abstract simplicial complex \(\Delta\), let \(\Gamma(\Delta)\) be the Boolean cell complex whose cells are indexed by all injective words over the sets forming the faces of \(\Delta\). The boundary of a cell indexed by a given word \(w\) consists of those cells that are indexed by subwords of \(w\). For a partial order \(P\) on \(S\), the authors study the subcomplex \(\Gamma(\Delta, P)\) of \(\Gamma(\Delta)\) consisting of those cells that are indexed by words whose letters are arranged in increasing order with respect to some linear extension of the order \(P\). For a graph \(G=(S,E)\) on vertex set \(S\) and a word \(w\) over \(S\), let \([w]\) be the class of all words that we can obtain from \(w\) via a sequence of commutations \(ss^\prime\to s^\prime s\) such that \(\{s,s^\prime \}\) is not an edge in \(E\). The authors study the Boolean cell complex \(\Gamma\slash G(\Delta)\) whose cells are indexed by commutation classes \([w]\) of words indexing cells in \(\Gamma(\Delta)\). It is demonstrated that if \(\Delta\) is shellable then so are \(\Gamma(\Delta, P)\) and \(\Gamma\slash G(\Delta)\). Moreover, it is shown that if \(\Delta\) is Cohen-Macaulay (sequentially Cohen-Macaulay) then so are \(\Gamma(\Delta, P)\) and \(\Gamma\slash G(\Delta)\). Finally, it is proved that the complex \(\Gamma(\Delta)\) is partitionable. The proved statements generalize results by \textit{F.D.~Farmer} [``Cellular homology for posets'', Math. Jap. 23, 607--613 (1979; Zbl 0416.55003)], \textit{A.~Björner} and \textit{M.L.~Wachs} [``On lexicographically shellable posets'', Trans. Am. Math. Soc. 277, 323--341 (1983: Zbl 0514.05009)] on the complex of all injective words.