Complexes of injective words and their commutation classes

Jakob Jonsson and Volkmar Welker

Vol. 243 (2009), No. 2, 313–329

DOI: 10.2140/pjm.2009.243.313

Abstract

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 Δ, let Γ(Δ) be the Boolean cell complex whose cells are indexed by all injective words over the sets forming the faces of Δ. 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, we study the subcomplex Γ(Δ,P) of Γ(Δ) 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′→ s′s such that {s,s′} is not an edge in E. We study the Boolean cell complex Γ∕G(Δ) whose cells are indexed by commutation classes [w] of words indexing cells in Γ(Δ). We prove:

• If Δ is shellable then so are Γ(Δ,P) and Γ∕G(Δ).
• If Δ is Cohen–Macaulay (respectively sequentially Cohen–Macaulay) then so are Γ(Δ,P) and Γ∕G(Δ).
• The complex Γ(Δ) is partitionable.

Our work generalizes work by Farmer and by Björner and Wachs on the complex of all injective words.

Keywords

injective word, Boolean cell complex, simplicial complex, Cohen–Macaulay complex, shellable complex

Mathematical Subject Classification 2000

Primary: 05E99, 52B22

Secondary: 18F25

Milestones

Received: 26 February 2008

Revised: 17 May 2009

Accepted: 18 May 2009

Published: 1 December 2009