HOMOLOGY OF THE BOOLEAN COMPLEX

KÁRI RAGNARSSON AND BRIDGET EILEEN TENNER^{†}

Abstract. We construct and analyze an explicit basis for the homology of the boolean complex of a Coxeter system. This gives combinatorial meaning to the spheres in the wedge sum describing the homotopy type of the complex. We assign a set of derangements to any unlabeled Coxeter graph. For each derangement, we construct a corresponding element in the homology of the complex, and the collection of these elements forms a basis for the homology of the boolean complex. In this manner, the spheres in the wedge sum describing the homotopy type of the complex can be represented by a set of derangements. We give an explicit, closed-form description of the derangements that can be obtained from any graph, and compute this set for several families of graphs. In the cases of complete graphs and Ferrers graphs, these calculations give bijective proofs of previously obtained enumerative results.

Keywords. Coxeter system, boolean complex, homology, derangement, complete graph, Ferrers graph, staircase shape

1. Introduction

In [8], we developed the boolean complex of a finitely generated Coxeter system, based on work by the second author in [11], and analyzed its homotopy type. The boolean complex of a Coxeter system can be constructed from the unlabeled Coxeter graph of the system. We take this as a starting point and talk about the boolean complex Δ(G) of a finite simple graph G, keeping in mind that any such graph can be the unlabeled Coxeter graph of a Coxeter system. Our main result in [8] was to show that the boolean complex of any finite simple graph has the homotopy type of a wedge of spheres. More precisely, there is a homotopy equivalence

|Δ(G)| ≃ ⋁_{i=1}^{β(G)} S^{|G|−1},  (1)

where the boolean number β(G) is a graph invariant which can be calculated recursively using edge operations. That this complex is homotopy equivalent to a wedge of spheres was also shown by Jonsson and Welker [7], who work in a more general context and do not address the question of the number of spheres in this particular setting. In the special case where G is a complete graph, Δ(G) is a complex of injective words, and Farmer [5] and Björner–Wachs [2] each showed that this complex has the homotopy type of a wedge of spheres. The number of spheres in this case was enumerated by Reiner–Webb in [9].

The boolean number is an interesting graph invariant, several examples of which were calculated in [8] and [3]. For some families of graphs the boolean number has intriguing enumerative properties. One notable example are the complete graphs, for which we showed that β(K_{n}) is the number of derangements of an n-element set in [8], recovering the enumerative result of Reiner–Webb from [9] mentioned above. Another example are the Ferrers graphs of staircase shapes, whose boolean numbers were shown in [3] to be the Genocchi numbers of the second kind, which also enumerate derangements with alternating excedances.

2010 Mathematics Subject Classification. Primary 20F55; Secondary 05C99, 05E15, 06A07.

† Research partially supported by a DePaul University Faculty Summer Research Grant.

In this paper we give bijective proofs of these enumerative results and give combinatorial meaning to the spheres appearing in the wedge sum in (1). This meaning is not apparent from the proofs in the papers cited above. Each of these proofs uses either discrete Morse theory ([8]) or shellability ([5, 7, 2]) to collapse most of the respective complexes down to a point, leaving only cells of maximal dimension connected to a single point, which results in a homotopy type of a wedge of spheres. However, which maximal cells remain at the end of the collapsing process depends on a series of choices, and the cells themselves do not form spheres within Δ(G). Therefore this process does not shed much light on what role the spheres in (1) really play.

Our approach in this paper is via the homology of the boolean complex. Of course, since Δ(G) has the homotopy type of a group of (|G| − 1)-dimensional spheres, we know that the reduced homology of Δ(G) is a graded group of dimension β(G) concentrated in degree |G| − 1. Rather than calculating the homology groups, our goal is to find, and analyze, an explicit basis for the homology of Δ(G). Each element in this basis is a formal sum of cells in Δ(G), and taking the union of the closure of these cells in Δ(G) gives a subcomplex that has the homotopy type of a sphere. (We actually take homology with ℤ/2 coefficients but the basic principle is the same.) The homological generators of the boolean complex are therefore good representatives for the spheres in (1).

The route from graphs to homological generators takes a detour through derangements. Given a graph G we recursively construct a set of derangements of the vertex set of G using the same edge operations used for calculating the boolean number of a graph. To each of these derangements we associate an element in the homology of Δ(G), and the central result of the paper is Theorem 5.2 which says that the outcome of these two steps is a basis for the homology of Δ(G). Thus we can regard the derangements associated to a graph G as combinatorial representatives for the spheres in the wedge sum describing the homotopy type of Δ(G). Another important result is Theorem 3.11 where we give an explicit, closedform description of the set of derangements associated to G. When G is a complete graph, this is the set of all derangements, and when G is the Ferrers graph associated to a staircase shape, this is the set of permutations of alternating excedances. Thus we obtain bijective proofs of the enumerative results mentioned earlier.

The paper is divided into seven sections. Following this introduction is a review of background material, including boolean complexes and their homotopy type and a discussion of homology. In Section 3, we make the connection between graphs and derangements and in Section 4 we reveal the link between derangements and homology. Section 5 is devoted to the proof of Theorem 5.2. In Section 6, we give a series of examples which provide bijective arguments for results previously obtained enumeratively in [9], [8] and [3]. We conclude with Section 7 where we briefly investigate some statistics related to the derangements associated to a graph.

2. Background

2.1. Boolean complexes. Boolean complexes were introduced in [8] as cell complexes associated to Coxeter systems. In fact, as noted in [8], the boolean complex of a Coxeter system only depends on its unlabeled Coxeter graph, and therefore one can equally well think of boolean complexes associated to finite simple graphs. We shall focus on the graph perspective here, referring the reader to [8] for the relationship to Coxeter systems.

Given a graph G with vertex set V (G), let 𝕎(G) be set of words on letters in V (G) without repetition, ordered by subword inclusion. Form an equivalence relation ∼ on 𝕎(G) by saying that two letters commute if and only if they are not adjacent in G. More precisely, if a_{1}, …, a_{k}, s, t, b_{1}, …, b_{ℓ} are distinct vertices in G, and s and t are not adjacent, then

a_{1} ⋯ a_{k}stb_{1} ⋯ b_{ℓ} ∼ a_{1} ⋯ a_{k}tsb_{1} ⋯ b_{ℓ}

in 𝕎(G), and ∼ is the equivalence relation generated by this condition. Let 𝔹(G) be the set of equivalence classes in 𝕎(G) with respect to ∼, with partial order induced by the order relation on 𝕎(G). We call 𝔹(G) the boolean poset of G (this was called the boolean ideal in [8]), and say that an element in 𝕎(G) is a word representative for its equivalence class in 𝔹(G).

The boolean poset is ranked by word length, where we adopt the convention that a word of length k + 1 has rank k (so the empty word has rank −1). For each integer k, let 𝔹_{k}(G) ⊆ 𝔹(G) be the subset of elements of rank k. It is not hard to see that 𝔹(G) is a simplicial poset, meaning that the principal (lower) order ideal of every element is isomorphic to a boolean algebra. Consequently ([1]), there is an associated regular cell complex Δ(G) that has 𝔹(G) as face poset, where the dimension of each cell in Δ(G) equals the rank of the corresponding element in 𝔹(G). The empty word corresponds to the empty cell and will henceforth be ignored. We refer to Δ(G) as the boolean complex of G.

Note that, although the closure of each cell in Δ(G) is a simplex, Δ(G) is not a simplicial complex. This is because a cell in Δ(G) is not determined by the 0-cells in its closure. An example of this, described in full detail in [8], is the graph consisting of two vertices and an edge between them. Instead Δ(G) is a Δ-complex, as defined in [6].

2.2. Homotopy type of boolean complexes. One obtains a geometric realization |Δ(G)| in the standard way: take a geometric simplex of dimension k for each k-cell in Δ(G), and glue simplices together according to the face poset. By the homotopy type of the boolean complex we mean the homotopy type of |Δ(G)|. The goal of this section is to recall the main result in [8], stated below as Theorem 2.2, which shows that the boolean complex of a graph G with n vertices has the homotopy type of a wedge of (n − 1)-spheres. In [8] we gave a recursive formula for computing the number of spheres occurring in the wedge sum. This number is a graph invariant, which we denote β(G) and call the boolean number of G. The recursion was given in terms of graph operations, defined as follows.

Definition 2.1. Let G be a finite simple graph and e an edge in G.

• Deletion: G − e is the graph obtained by deleting the edge e.

• Simple contraction: G/e is the graph obtained by contracting the edge e and then removing all loops and redundant edges.

• Extraction: G − [e] is the graph obtained by removing the edge e and its incident vertices.

In the statement of the theorem, and throughout the paper, we let |G| denote the number of vertices in a finite graph G, and we let δ_{n} denote the graph with n vertices and no edges. Furthermore, we use the symbol ≃ to denote homotopy equivalence, and write b · S^{r} for a wedge sum of b spheres of dimension r. (In particular 0 · S^{r} is a point.)

Theorem 2.2 ([8]). For every nonempty, finite simple graph G, there is an integer β(G) so that

|Δ(G)| ≃ β(G) · S^{|G|−1}.

Moreover, the values β(G) can be computed using the recursive formula

β(G) = β(G − e) + β(G/e) + β(G − [e]),  (2)

if e is an edge in G such that G − [e] is nonempty, with initial conditions

β(K_{2}) = 1 and β(δ_{n}) = 0,

where K_{2} is the complete graph on two vertices.

The following results are also useful.

Corollary 2.3 ([8]). A finite simple graph G has an isolated vertex if and only if β(G) = 0. That is, the center of a Coxeter group contains a generator of the group if and only if the group’s boolean complex is contractible.

Proposition 2.4 ([8]). If G = H_{1} ⊔ H_{2} for graphs H_{1} and H_{2}, then

Δ(G) = Δ(H_{1}) ∗ Δ(H_{2}),

where ∗ denotes simplicial join, and consequently

|Δ(G)| ≃ β(H_{1})β(H_{2}) · S^{|H_{1}|+|H_{2}|−1}.

In particular, β(G) = β(H_{1})β(H_{2}).

2.3. Homology of boolean complexes. The goal of this subsection is to recall how the homology of |Δ(G)| is computed from Δ(G) (without appealing to the homotopy type) and explaining how a nonzero element in the homology represents a sphere in |Δ(G)|. The procedure for computing the homology of a Δ-complex is well known and is discussed, for example, in [6]. In the discussion here, we adapt the procedure to take advantage of the particular setting of the boolean complex. In doing so, we also establish notation and conventions used in later sections. To simplify matters we always take homology with 𝔽_{2}- coefficients, thus avoiding issues of orientation, and write H_{∗}(Δ(G)) for H_{∗}(Δ(G), 𝔽_{2}) from now on.

Let G be a finite simple graph with vertex set V (G). For each integer k, let C_{k}(G) be the free 𝔽_{2}-vector space with basis 𝔹_{k}(G). In particular, we have C_{−1}(G) ≅ 𝔽_{2}, generated by the empty string, and C_{k}(G) = 0 if k > |G| − 1 or k < −1. We will, without special mention, regard 𝔹_{k}(G) as a subset of C_{k}(G), and use the same symbol to denote an element in 𝔹_{k}(G) and the corresponding basis element in C_{k}(G). For each v ∈ V (G), and each integer k let

∂_{k,v}^{G}: C_{k}(G) → C_{k−1}(G),

be the map of 𝔽_{2}-modules defined on a basis element σ ∈ 𝔹_{k}(G) as follows: if σ contains the letter v, then let ∂_{k,v}^{G}(σ) be the string obtained by deleting v; if σ does not contain v, then set ∂_{k,v}^{G}(σ) = 0. Summing over elements of V (G), we get the differential maps

∂_{k}^{G} := ∑_{v∈V (G)} ∂_{k,v}^{G}: C_{k}(G) → C_{k−1}(G).

It is easy to check that ∂_{k}^{G} ∘ ∂_{k+1}^{G} = 0 for each k. Hence, putting

Z_{k}(G) := ker(∂_{k}^{G})  and  B_{k}(G) := im(∂_{k+1}^{G}),

we have B_{k}(G) ⊆ Z_{k}(G) ⊆ C_{k}(G). An element of Z_{k}(G) is called a homological cycle, and an element of B_{k}(G) is called a boundary. The kth homology group of 𝔹(G) is defined as the quotient

H_{k}(Δ(G)) = Z_{k}(G)/B_{k}(G).

We write H_{∗}(Δ(G)) to denote the graded group having H_{k}(Δ(G) in degree k. There is a canonical isomorphism

H̃_{∗}(|Δ(G)|, 𝔽_{2}) ≅ H_{∗}(Δ(G)),

where the homology on the left side is reduced because of the generator in C_{−1}(G).

The motivation for this terminology is that one can think of a generator as corresponding to a k-simplex. Each face of this simplex is obtained by deleting a single letter, and thus one can regard ∂_{k}^{G} as a map sending a simplex to its boundary. Carrying the analogy over to sums of simplices, an element in C_{k}(G) is called a boundary if it is in the image of ∂_{k+1}^{G}, while it is called a cycle if it is in the kernel of ∂_{k}^{G}, meaning that the boundaries of individual simplices “cancel.” Loosely speaking, the homology group H_{k}(Δ(G)) then measures kdimensional “holes” (cycles) in |Δ(G)| that are not filled in by (k+1)-dimensional simplices.

Since |Δ(G)| is homotopy equivalent to a wedge of (|G| − 1)-dimensional sphere, the only nonzero homology group is H_{|G|−1}(Δ(G)) ≅ 𝔽_{2}^{β(G)}. Notice further that since C_{|G|}(G), and hence B_{|G|−1}(G), equals zero, we have H_{|G|−1}(G) = Z_{|G|−1}(G). A nonzero element in H_{|G|−1}(𝔹(G)) is therefore a cycle in C_{|G|−1}(G), or in other words a formal sum of elements in 𝔹_{|G|−1}(G) whose boundaries cancel. The closure of the corresponding union of (|G| − 1)-simplices in |Δ(G)| encloses a (|G| − 1)-dimensional hole, and can be thought of as representing a (|G| − 1)-sphere in |Δ(G)|. Thus finding a canonical set of generators for the homology of a boolean complex amounts to giving a combinatorial meaning to the spheres appearing in the wedge-sum representation of its homotopy type.

In subsequent sections we will show how one can obtain a basis for the homology of the boolean complex of a graph from a certain class of permutations of the vertices constructed from the graph. These permutations will be written in cycle notation. To avoid confusion, as suggested above, we will refer to an element in Z_{k}(G) as a homological cycle, with the term cycle being reserved for permutation discussions. In the remainder of the paper we will often write ∂^{G} and ∂_{v}^{G} instead of ∂_{k}^{G} and ∂_{k,v}^{G}, respectively, as the dimension k is usually clear from the context. When the graph G is clear from the context, we will drop the superscript G and just write ∂ and ∂_{v}. This convention debuts in the following lemma, which is obvious yet very useful.

Lemma 2.5. Let G be a finite simple graph with vertex set V (G). For x ∈ C_{|G|−1}(G) the following are equivalent:

(1) ∂(x) = 0, and

(2) ∂_{v}(x) = 0 for each v ∈ V (G).

We emphasize that the method for computing homology presented here is specific to 𝔽_{2} coefficients. Without going into detail, computing cohomology with coefficients in ℤ (or an arbitrary abelian group) would first entail choosing an orientation for each element in Δ(G) by ordering the vertices. The choice of string representatives for an element in Δ(G) matters in that setting: changing representatives via a commutativity relation changes the orientation, and hence the sign in C_{k}(G, ℤ). Working with coefficients in 𝔽_{2} simplifies things greatly, as one need not worry about orientations. Furthermore, with general coefficients, one must multiply ∂_{v} by a factor of (−1)^{i} when the vertex being deleted is in the i-th position of the string, making the differential ∂ an alternating sum. Since there is no substantive benefit to working with ℤ coefficients when we know a priori that the boolean complex is a wedge of spheres, we avoid the nuisance of keeping track of signs by restricting ourselves to 𝔽_{2} coefficients.

2.4. String concatenation product. For a finite graph G, the chain complex C_{∗}(Δ(G)) has a product structure given by word concatenation. This is defined on basis elements as follows. Let σ and τ be word representatives for generators σ̄ ∈ C_{k}(Δ(G)) and τ̄ ∈ C_{ℓ}(Δ(G)). Thus σ is a word on k + 1 vertices of G, and σ̄ is the corresponding element in 𝔹_{k}(G) ⊂ C_{k}(Δ(G)), and similarly with τ. We define the concatenation product by

σ̄τ̄ := \begin{cases}\overline{στ} ∈ C_{k+l+1}(Δ(G)), & if σ and τ have no common letters, \\ 0, & if σ and τ have common letters. \end{cases}

It is not hard to check that this is a well-defined, associative operation. Extending linearly, we obtain the string concatenation product sending general elements x ∈ C_{k}(Δ(G)) and y ∈ C_{ℓ}(Δ(G)) to xy ∈ C_{k+l+1}(Δ(G)).

2.5. Collapsing maps. Here we discuss the collapsing map of boolean complexes induced by an inclusion of graphs with the same vertex set, and the effect of this map in homology.

Definition 2.6. For a finite set V, let K_{V} be the complete graph with vertex set V. When the finite set is {1, …, n}, write K_{n} for short.

Notice that for a complete graph K_{V}, the boolean poset is the same as the poset of injective words: 𝔹(K_{V}) = 𝕎(K_{V}). If G is another graph with vertex set V, then by definition we have a projection of posets 𝕎(G) → 𝔹(G). Since 𝕎(G) = 𝕎(K_{V}), we can interpret this as a map of boolean posets

π_{G}: 𝔹(K_{V}) ↠ 𝔹(G),

which we call a collapsing map. This collapsing map induces a map on boolean complexes π_{G}: Δ(K_{V}) → Δ(G) and consequently a map of chain complexes

π_{G}_{∗}: C_{∗}(Δ(K_{V})) → C_{∗}(Δ(G)).

Being a map of chain complexes means that π_{G}_{∗} is a map of graded groups that respects the differential (that is, ∂_{∗}^{G} ∘ π_{G}_{∗} = π_{G}_{∗} ∘ ∂_{∗}^{K_{V}}), and this implies that we have an induced map in homology

π_{G}_{∗}: H_{∗}(Δ(K_{v})) → H_{∗}(Δ(G)),

which we also refer to as the collapsing map.

More generally, when G is a subgraph of a graph G′, and both graphs have the same vertex set V, there is a collapsing map of boolean posets π_{G}^{G′}: 𝔹(G′) ↠ 𝔹(G) which satisfies π_{G}^{G′} ∘ π_{G′} = π_{G}. This map also induces a map of boolean complexes and a map in homology π_{G}^{G′}_{∗}: H_{∗}(Δ(G′)) → H_{∗}(Δ(G)).

When the graphs involved are clear from the context and there is no danger of confusion, we will write π instead of π_{G} or π_{G}^{G′}.

3. From graphs to derangements

In this section we describe an algorithm that constructs a set of derangements of the vertex set of a finite simple graph G. The algorithm is recursive, using the same edge operations involved in the recursive computation of the boolean number of the graph, and as a consequence the number of derangements produced is equal to the boolean number of the graph. We also give an explicit, closed-form description of the resulting set of derangements in Theorem 3.11.

In Section 4 we will show how derangements of the vertex set of a graph give rise to homology cycles for the boolean complex of the graph, and in Section 5 we prove that the homology cycles coming from the derangements constructed in this section form a basis for the homology of the boolean complex. Therefore the derangements constructed here are key to understanding the combinatorial meaning of the spheres representing the homotopy type of the boolean complex.

Definition 3.1. A derangement of a finite set V is a permutation of V that has no fixed points. The set of derangements of V is denoted by D_{V}. When V is the finite set {1, …, n} we may write D_{n} for D_{V}. The derangement number d_{n} is the cardinality of D_{n}.

It is useful here to write permutations in cycle notation. For example, (134)(26)(587) is the map 1 ↦ 3, 2 ↦ 6, 3 ↦ 4, 4 ↦ 1, 5 ↦ 8, 6 ↦ 2, 7 ↦ 5, and 8 ↦ 7. Thus a derangement is a permutation which can be written as a product of disjoint cycles, all of which have length at least two. For small values of n, the derangements of {1, …, n} and the derangement numbers d_{n} are give in Table 1.

Definition 3.2. Let V be a linearly ordered finite set. A derangement of V is written in standard cycle form if it is written as a product of disjoint cycles so that the minimum element of a cycle appears as the leftmost letter in that cycle, and the cycles are arranged from left to right in increasing values of minimum letters.

Example 3.3. The permutation (134)(26)(587) is written in standard cycle form, while the alternative representations (134)(587)(26) and (341)(26)(587) are not.

n D_{n} = Derangements of {1, …, n}  d_{n}
1 none  0
2 (12)  1
3 (123), (132)  2
4 (1234), (1243), (1324), (1342), (1423), (1432), (12)(34), (13)(24), (14)(23) 9

Table 1. Derangements and derangement numbers for small cases.

The derangement-producing algorithm described below assumes a linear ordering of the vertex set, and its output depends on the order. Formally, we are therefore recursively defining a map

(G, ≤) ⟼ D(G, ≤) ⊆ D_{V (G)},

where V (G) is the vertex set of G, and ≤ is a linear order on V (G). Such a pair (G, ≤) is usually referred to as an ordered graph. In the remainder of the paper we will abuse notation by referring to an ordered graph G instead of (G, ≤), and D(G) instead of D(G, ≤), taking the linear ordering to be understood. This will not cause any confusion since we only consider one linear ordering for a given graph. In our examples, vertices will be labeled by integers and the ordering is clear. Note, however, that the derangements in the set D(G) depend on the ordering of G. That is, a different initial labeling of the graph will yield different derangements. Thus, a cleverly chosen labeling can be the key to proving certain characteristics of the set of derangements D(G).

There are three components to the recursive definition of D(G), including the initial conditions, and these are highlighted as three separate bullet points in the following discussion.

Given a nonempty finite simple ordered graph G with maximal vertex t, the initial conditions are as follows.

• If V (G) = {s, t} and there is an edge between these vertices, then D(G) := {(st)}.

• If t is an isolated vertex, then set D(G) := ∅.

Definition 3.4. Let G be a finite simple ordered graph. If t is the maximal non-isolated vertex of G and s is maximal among vertices adjacent to t then the maximal edge of G is the edge {s, t}.

In the recursive step we perform edge operations on the maximal edge of G. First, we must explain how, for a finite simple ordered graph G and an edge e = {s, t} in G, applying the three edge operations (deletion, simple contraction, and extraction) to G behaves on ordered graphs, and how permutations of the vertex sets of the resulting graphs, G−e, G/e and G − [e] give rise to permutations of the vertex set of G.

Deletion: G−e has the same vertex set as G and is given the same ordering of vertices. A permutation of V (G − e) is a permutation of V (G). Simple contraction: Let x be the vertex in G/e obtained by contracting the edge e. We obtain a linear ordering on V (G/e) by letting x take the place of s in the ordering on V (G). Given a permutation w of V (G/e), let w_{st} be the permutation of V (G) obtained by writing w in cycle notation, and replacing x by st in the appropriate cycle. Extraction: V (G − [e]) is a subset of V (G) and the linear ordering of V (G) restricts to a linear ordering of V (G − [e]). Given a permutation w of V (G − [e]), a permutation w ⊔ (st) on V (G) is given by applying w to any element of V (G − [e]) = V (G) \ {s, t} and the transposition (st) to the elements s and t.

We are now able to state the recursive condition for computing D(G). As before, t is the maximal vertex of G in this discussion.

• If t is not an isolated vertex in G and e = {s, t} is the maximal edge in G, and G has at least three vertices, then set

D(G) := D(G − e) ∪ {w_{st} : w ∈ D(G/e)} ∪ {w ⊔ (st) : w ∈ D(G − [e])}.  (3)

We record the following properties of D(G) which are preserved throughout the recursive construction.

Lemma 3.5. Let G be a finite simple ordered graph and let t be the maximal vertex of G. If w ∈ D(G) then w is a derangement and t is adjacent to w^{−1}(t) in G.

Also observe that if G has any isolated vertex (maximal or otherwise), then D(G) = ∅ because the isolated vertex will be maximal at some step in the iteration, and the second initial condition will apply. This is a special case of the following result.

Proposition 3.6. For a nonempty finite simple ordered graph G,

|D(G)| = β(G).

Proof. The two numbers |D(G)| and β(G) agree at the initial conditions in the recursive definition for D(G). The result follows if we can show that they also satisfy the same recurrence relation. We prove this by showing that the three sets on the right-hand side of equation (3) are disjoint.

A derangement v_{st} in the second set satisfies v_{st}(s) = t and v_{st}(t) ≠ s, while a derangement u ⊔ (st) in the third set satisfies (u ⊔ (st))(s) = t and (u ⊔ (st))(t) = s. Therefore the second and third sets are disjoint. Since t is the maximal vertex in G − e and s is not adjacent to t in G − e, Lemma 3.5 implies that w(s) ≠ t for w ∈ D(G − e). Consequently the first set is disjoint from the other two. □

We now present an example of an ordered graph G and show how to compute D(G). In practice, contracting two vertices s and t acts in the linear ordering as the absorption of the larger vertex into the smaller vertex. It is convenient to name the new vertex by the concatenation “st” of the names of the previous two. The position of such a vertex in the linear order of the new graph is dictated by the first letter in the concatenation. This convention is used throughout the following example.

Example 3.7. Let G be the graph given below, with vertices ordered by their labels.

3 4 1 2

Throughout this example, the maximal edge used in the recursion will be drawn more thickly than other edges. Let e be the maximal edge in the initial graph. The graphs G − e, G/e, and G − [e] are given below, along with their accompanying labelings.

\begin{matrix}3 \\ 4 \\ 1 \\ 2 \\ G − e \end{matrix}  \begin{matrix}3 \\ 1 \\ 24 \\ G/e \end{matrix}  \begin{matrix}3 \\ 1 \\ G − [e] \end{matrix}

In the third of these graphs, G − [e], the only operation not leading to the empty set is extraction, with gives the cycle (13). Thus, combining this with the original extraction operation, this contributes the derangement (13)(24) to D(G). In the second graph, G/e, extraction of the marked edge e′ yields a contribution of ∅. Thus we need only consider deletion and simple contraction of this edge, as follows.

3 1 24 (G/e) − e′  ^{1 243 (G/e)/e′}

Iterations of this process shows that these two graphs and labelings contribute the derangements (1324) and (1243), respectively. Finally, the graph G − e yields the derangements (14)(23) and (1423).

Therefore, in this example, D(G) = {(14)(23), (1423), (1324), (1243), (13)(24)}.

There is an explicit criterion, given in Theorem 3.11 below, for deciding whether a given derangement w belongs to D(G) based on connectivity properties of the ordered graph G. To describe this criterion we must introduce the following notions.

Definition 3.8. Let G be an ordered graph and let w be a permutation of its vertex set. For a vertex t in G set

ρ_{w}(t) = {t, w(t), ⋯, w^{k−1}(t)} ,

where k is the smallest positive integer such that w^{k}(t) ≤ t, and set

λ_{w}(t) = w^{−ℓ}(t) ,

where ℓ is the smallest positive integer such that w^{−ℓ}(t) ≤ t.

When w is written in standard cycle form and t is not the smallest element in its cycle, λ_{w}(t) is the first element appearing to the left of t that is smaller than t, and ρ_{w}(t) is the set of elements obtained by starting at t and moving to the right until reaching an element less than t. When t is the smallest element in its cycle, ρ_{w}(t) is the entire set of elements in the cycle of t, and λ_{w}(t) = t. This characterizes the smallest element, as noted in the following lemma.

Lemma 3.9. Given a derangement w of an ordered set V, written in standard cycle form, and an element t ∈ V, λ_{w}(t) ∈ ρ_{w}(t) if and only if t is the smallest element in its cycle.

Example 3.10. Let w = (13472)(56). Then λ_{w} and ρ_{w} are given below.

\begin{matrix}t & λ_{w}(t) & ρ_{w}(t) \\ 1 & 1 & \{1, 2, 3, 4, 7\} \\ 2 & 1 & \{2\} \\ 3 & 1 & \{3, 4, 7\} \\ 4 & 3 & \{4, 7\} \\ 5 & 5 & \{5, 6\} \\ 6 & 5 & \{6\} \\ 7 & 4 & \{7\} \end{matrix}

We now state and prove the criteria for membership in the set D(G). Example 3.12 depicts an instance of when this criteria is met and when it is not.

Theorem 3.11. Let G be a finite simple ordered graph and let w be a permutation of its vertex set. Then w ∈ D(G) if and only if for every vertex t of G the vertex λ_{w}(t) is adjacent to some vertex in ρ_{w}(t).

Proof. For a finite simple ordered graph G and a permutation w of its vertex set, we will say that w is G-valid at a vertex r of G if λ_{w}(r) is adjacent to some vertex in ρ_{w}(r). We say that w is G-valid if it is G-valid at r for every vertex r of G. Let D′(G) denote the set of G-valid permutations V (G). We will show that D′(−) satisfies the same recursion and the same initial conditions as D(−), and hence D′(G) = D(G).

First let us observe that the conclusion of Lemma 3.5 holds for D′(G): If w is a permutation of V (G) with w(r) = r for some vertex r then λ_{w}(r) = r and ρ_{w}(r) = {r} so w is not G-valid at r (since G is assumed to be simple). Thus any element of D′(G) is a derangement. Furthermore, if t is the maximal vertex of G and w ∈ D′(G) then λ_{w}(t) = w^{−1}(t) and ρ_{w}(t) = {t}, so validity at t implies that t is adjacent to w^{−1}(t) in G.

Now we establish the initial conditions. If G is an ordered graph with vertices s < t and an edge between them, then one easily checks that D′(G) = {(st)} = D(G). If the maximal vertex t of G is isolated then no derangement w of V (G) can be G-valid at t since always ρ_{w}(t) = {t}. Hence D′(G) = ∅ = D(G).

For the recursive step let G be an ordered graph with at least two edges such that the maximal vertex t is not isolated and let e = {s, t} be the maximal edge in G. We can write D′(G) as a disjoint union

D′(G) = A(G) ⊔ B(G) ⊔ C(G) ,

where

A(G) = {w ∈ D′(G) : w(s) ≠ t} ,
B(G) = {w ∈ D′(G) : w(s) = t, w(t) ≠ s} , and
C(G) = {w ∈ D′(G) : w(s) = t, w(t) = s} .

The proof is complete once we establish the following equalities.

A(G) = D′(G − e),  (i)
B(G) = {u_{st} : u ∈ D′(G/e)} , and  (ii)
C(G) = {v ⊔ (st) : v ∈ D′(G − [e])} .  (iii)

We start by proving (i). Any (G − e)-valid derangement of V (G − e) = V (G) is also G-valid, so D′(G − e) ⊆ D′(G). Furthermore, for w ∈ D′(G − e) we know that t is adjacent to w^{−1}(t) in G − e, so s ≠ w^{−1}(t). Combining these facts we have D′(G − e) ⊆ A(G).

Now suppose w ∈ A(G). If w ∉ D′(G − e) then there is some vertex r at which w is not (G−e)-valid. By assumption w is G-valid at r, so we must have λ_{w}(r) = s and t ∈ ρ_{w}(r). In particular, s is in the same w-cycle as t and appears left of t when w is written in standard cycle form. However, we know that t is adjacent to w^{−1}(t), and maximality of e = {s, t} and the assumption w(s) ≠ t then imply w^{−1}(t) < s ≤ r. Since w^{−1}(t) appears between s and t when w is written in standard cycle form, this makes the conditions λ_{w}(r) = s and t ∈ ρ_{w}(r) incompatible, leading to a contradiction. We conclude that w ∈ D′(G), and since this holds for all w ∈ A(G) we have A(G) ⊆ D′(G − e), completing the proof of (i).

To prove (iii) we first observe that any derangement w of V (G) such that w(s) = t and w(t) = s can be written as w = v ⊔ (st) where v is a derangement of V (G − [e]). Clearly w ∈ C(G) if and only if v ∈ D′(G − [e]).

It remains to prove (ii). Any derangement w of V (G) such that w(s) = t and w(t) ≠ s can be written as w = u_{st} where u is a derangement of V (G/e). We show that w is G-valid if and only if u is G/e-valid. First observe that w is always G-valid at t since λ_{w}(t) = s and ρ_{w}(t) = {t}. Now let x denote the vertex in G/e obtained upon identifying s with t. Since the ordering of G/e is obtained by letting x take the place of s in the ordering of G we have an injective, order-preserving map i: V (G/e) → V (G) that sends x to s and any other vertex to itself. For each r in V (G/e) we will show that G/e-validity of u at r implies G-validity of w at i(r) and that G-validity of w (at every vertex) implies G/e-validity of u at r. Since i has image V (G) \ {t}, and we already know that w is G-valid at t, it follows that w is G-valid if and only if u is G/e-valid, completing the proof. To prove the claim one checks that for r ∈ V (G/e) one has

λ_{w}(i(r)) = i(λ_{u}(r))

and

ρ_{w}(i(r)) = \begin{cases}ρ_{u}(r), & if x ∉ ρ_{u}(r) ; \\ (ρ_{u}(r) \ \{x\}) ∪ \{s, t\}, & if x ∈ ρ_{u}(r) . \end{cases}

We consider four cases.

If λ_{u}(r) ≠ x and x ∉ ρ_{u}(r) then λ_{w}(i(r)) = λ_{u}(r) and ρ_{w}(i(r)) = ρ_{u}(r) so the result is obvious.

If λ_{u}(r) ≠ x and x ∈ ρ_{u}(r) then λ_{w}(i(r)) = λ_{u}(r) and ρ_{w}(i(r)) = (ρ_{u}(r) \ {x}) ∪ {s, t}. The result now follows from the fact that λ_{u}(r) is adjacent to x in G/e if and only if it is adjacent to either s or t in G.

If λ_{u}(r) = x and x ∉ ρ_{u}(r) then λ_{w}(i(r)) = s and ρ_{w}(i(r)) = ρ_{u}(r). Furthermore, since λ_{u}(r) ∉ ρ_{u}(r) we know that r is not minimal in its u-cycle by Lemma 3.9. It follows that i(r) is not minimal in its w-cycle; in particular i(r) > λ_{w}(i(r)) = s. For any q ∈ ρ_{w}(i(r)) we have q ≥ i(r) > s so maximality of e = {s, t} implies that q is not adjacent to t. Thus we can deduce that q is adjacent to x in G/e if and only if q is adjacent to s in G/e. It follows that u is G/e-valid at r if and only if w is G-valid at i(r).

If λ_{u}(r) = x and x ∈ ρ_{u}(r) then r = x and x is minimal in its u-cycle by Lemma 3.9. It follows that i(r) = s is minimal in its w-cycle. In this case w is automatically G-valid at i(r) because s = λ_{w}(i(r)) is adjacent to t ∈ ρ_{w}(i(r)). On the other hand, if we assume that w is G-valid then G-validity at w(t) implies that s = λ_{w}(w(t)) is adjacent to a vertex of ρ_{w}(w(t)) in G, and hence r = x is adjacent to the same vertex (which also belongs to ρ_{u}(r) since this set is the entire u-cycle of r), proving G/e-validity of u at x. □

Example 3.12. Let G be the 7-vertex graph depicted below.

1 2 3 4 5 6 7

It is easy to check that (1234)(567) is an element of D(G). On the other hand, the derangement (1234567) is excluded from D(G) because λ_{(1234567)}(5) = 4 and ρ_{(1234567)}(5) = {5, 6, 7}, but 4 is not adjacent to 5, 6, or 7 in the graph. As another example, the derangement (13472)(56) of Example 3.10 is excluded from D(G) because λ_{(13472)(56)}(3) = 1 and ρ_{(13472)(56)}(3) = {3, 4, 7}, and 1 is not adjacent to 3, 4, or 7.

Theorem 3.11 allows us to describe the derangements induced by the disjoint sum of two ordered graphs in terms of the derangements induced by the parts. In the statement we use the notation w_{1} ⊔ w_{2} to denote the permutation of V_{1} ⊔ V_{2} obtained from a permutation w_{1} of a set V_{1} and a permutation w_{2} of a set V_{2}.

Corollary 3.13. If G_{1} and G_{2} are disjoint finite ordered simple graphs then

D(G_{1} ⊔ G_{2}) = {w_{1} ⊔ w_{2} : w_{1} ∈ D(G_{1}), w_{2} ∈ D(G_{2})} .

The set D(G) invites a variety of combinatorial questions. For example, we can look at those elements in D(G) whose standard cycle form consists of exactly one cycle. Let us call this set D^{1}(G) ⊆ D(G). Note that when extraction is used in the recursive construction of elements of D(G), additional cycles are created. Thus D^{1}(G) satisfies the recursion

D^{1}(G) = D^{1}(G − e) ∪ {w_{st} : w ∈ D^{1}(G/e)}.  (4)

Some enumerative results about D^{1}(G) are stated in the following proposition.

Proposition 3.14. Let G be a finite simple ordered graph.

(a) |D^{1}(G)| = 0 if and only if G is not connected.

(b) |D^{1}(G)| = 1 if and only if G is a tree.

(c) If G has exactly one cycle, and that cycle contains m vertices, then |D^{1}(G)| = m − 1.

Proof. Statements (a) and (b) follow easily from equation (4). Statement (c) can be proved by induction on the total number of edges in G, using the recursion of equation (4) and statement (a). □

It is interesting to note that the results of Theorem 3.14 are independent of the ordering of the vertex set of G. More generally, one can let D^{k}(G) ⊆ D(G) be the subset of derangements with exactly k disjoint cycles. Examples suggest that the sizes of the sets D^{k}(G) are independent of the ordering of the vertex set of G. In later sections we will show that the elements in D(G) can be treated as combinatorial representatives for the spheres appearing in the wedge sum description of the homotopy type of Δ(G) offered by Theorem 2.2. This raises the question of the significance of the number of cycles in w ∈ D(G) with respect to the boolean complex Δ(G).

4. From derangements to homology

We now describe a map from the set of derangements of the vertex set of a finite ordered graph G to the top-dimensional homology of the boolean complex of G. Just as in Section 3, we fix an ordering ≤ on V (G), and the output of the map defined here depends on that ordering. As before, we suppress the “≤” in our notation. Formally, we are therefore defining a map

ϕ_{G}: D_{V (G)} ⟶ H_{|G|−1}(Δ(G)).

When no confusion will arise, this map may be denoted simply as ϕ.

We initially do this for complete graphs, defining a map ϕ_{K_{V}} : D_{V} → C_{|V |−1}(Δ(K_{V})), where K_{V} is the complete graph with vertex set V. We then show in Lemma 4.3 that ϕ_{K_{V}} actually takes values in H_{|V |−1}(Δ(K_{V})) ⊆ C_{|V |−1}(Δ(K_{V})). Finally, the map ϕ_{G} is obtained by composing ϕ_{K_{V (G)}} with the collapsing map π_{G}.

Definition 4.1. Let G be a finite simple graph. For a ∈ C_{k}(Δ(G)) and b ∈ C_{ℓ}(Δ(G)), set

(a ⋄ b) := ab + ba ∈ C_{k+ℓ+1}(Δ(G)),

where ab and ba are the string concatenation products (see Section 2.4).

Consider a linearly ordered set V. The following algorithm describes a map ϕ = ϕ_{K_{V}} : D_{V} → C_{|V |−1}(Δ(K_{V})). The input is a derangement w ∈ D_{V}, written in standard cycle form, and the final output of this procedure is ϕ(w).

Step 1. Between each consecutive pair of letters in each cycle of w, insert the

symbol ⋆. Step 2. If there are no ⋆ symbols in the string, then HALT. Otherwise, determine which symbol ⋆ has the largest right-hand neighbor. Step 3. Suppose that the symbol ⋆ located in Step 2 is between quantities Q and R; that is, it appears as Q ⋆ R. Then replace Q ⋆ R by (Q ⋄ R).

Step 4. GOTO Step 2.

Example 4.2. Let w = (134)(26)(587). Applying the above procedure to w gives the following sequence of steps.

(1 ⋆ 3 ⋆ 4)(2 ⋆ 6)(5 ⋆ 8 ⋆ 7)
(1 ⋆ 3 ⋆ 4)(2 ⋆ 6)((5 ⋄ 8) ⋆ 7)
(1 ⋆ 3 ⋆ 4)(2 ⋆ 6)((5 ⋄ 8) ⋄ 7)
(1 ⋆ 3 ⋆ 4)(2 ⋄ 6)((5 ⋄ 8) ⋄ 7)
(1 ⋆ (3 ⋄ 4))(2 ⋄ 6)((5 ⋄ 8) ⋄ 7)
(1 ⋄ (3 ⋄ 4))(2 ⋄ 6)((5 ⋄ 8) ⋄ 7)

Thus

ϕ((134)(26)(587)) = (1 ⋄ (3 ⋄ 4))(2 ⋄ 6)((5 ⋄ 8) ⋄ 7)
= (1 ⋄ (34 + 43))(26 + 62)((58 + 85) ⋄ 7)
= (1(34 + 43) + (34 + 43)1)(26 + 62)((58 + 85)7 + 7(58 + 85))
= (134 + 143 + 341 + 431)(26 + 62)(587 + 857 + 758 + 785))
= 13426587 + 13426857 + 13426758 + 13426785

+13462587 + 13462857 + 13462758 + 13462785 +14326587 + 14326857 + 14326758 + 14326785 +14362587 + 14362857 + 14362758 + 14362785 +34126587 + 34126857 + 34126758 + 34126785 +34162587 + 34162857 + 34162758 + 34162785 +43126587 + 43126857 + 43126758 + 43126785 +43162587 + 43162857 + 43162758 + 43162785

The following result allows us to regard ϕ as a map D(K_{V}) → H_{|V |−1}(Δ(K)), and we do so henceforth without further mention.

Lemma 4.3. Let V be finite ordered set. If w is a derangement of V, then ϕ_{(K_{V} )}(w) is a homological cycle.

Proof. We must show that ∂(ϕ(w)) equals 0. By Lemma 2.5 this is equivalent to showing that for each v ∈ V we have ∂_{v}(ϕ(w)) = 0. Because w has no fixed points, the letter v is in the same cycle as at least one other letter in the standard cycle form of w. Thus ϕ(w) contains a product (v ⋄ x) = (x ⋄ v) for some x not containing the letter v. Observe that

∂_{v}((v ⋄ x)) = ∂_{v}(vx + xv) = x + x = 2x = 0.

This, combined with the fact that (0 ⋄ y) = (y ⋄ 0) = 0 for all y, implies that ∂_{v}(ϕ(w)) = 0 for all v ∈ V. Consequently, ∂(ϕ(w)) = 0, so ϕ(w) is a homological cycle. □

Definition 4.4. For a finite simple ordered graph G, let ϕ_{G} be the composite

ϕ_{G}: D(G) ↪ D(V (G)) ⟶^{ϕ_{(K_{V (G)})}} H_{|G|−1}(Δ(K_{V (G)})) ⟶^{π_{G}} H_{|G|−1}(Δ(G)).

5. The derangement basis

Having set up the maps from graphs to derangements and from derangements to homology in the previous sections, we are now prepared to prove the main result of this paper. This states that given a finite simple ordered graph G, the homological cycles {ϕ(w) : w ∈ D(G)} form a basis for the homology of Δ(G). Looking ahead to this result, we make the following definition.

Definition 5.1. Given a finite simple ordered graph G, the set {ϕ(w) : w ∈ D(G)} is the derangement basis associated to G.

The definition is justified by the following result.

Theorem 5.2. Given a finite simple ordered graph G, the derangement basis associated to G is a basis for H_{|G|−1}(Δ(G)).

Proof. Lemma 4.3 shows that the derangement basis consists of homological cycles, and Proposition 3.6 shows that |D(G)| = β(G), which is the 𝔽_{2}-rank of H_{|G|−1}(Δ(G)). Thus it remains to show that the elements of the derangement basis are linearly independent. We prove this by induction, assuming that the result holds for graphs with fewer edges. The base case is trivial to show.

Equation (3) allows us to rewrite the derangement basis associated to G as a disjoint union

{ϕ(w) : w ∈ D(G − e)} ⊔ {ϕ(w_{st}) : w ∈ D(G/e)} ⊔ {ϕ(w ⊔ (st)) : w ∈ D(G − [e])}. (5)

The graphs G − e, G/e, and G − [e] all have fewer edges than G, so by induction their associated derangement bases are linearly independent sets. Using this fact, it follows that each of the three sets in the union (5) is a linearly independent set.

Suppose that

∑_{u∈D(G_{e})} ϵ_{u}ϕ(u) + ∑_{v∈D(G/e)} ϵ_{v}ϕ(v_{st}) + ∑_{w∈D(G−[e])} ϵ_{w}ϕ(w ⊔ (st)) = 0.  (6)

If we apply the collapsing map π : H_{∗}(Δ(G)) → H_{∗}(Δ(G − e)) of Section 2.5 to equation (6), then elements arising from D(G/e) and D(G−[e]) are mapped to 0, since they can be written as a sum of terms of products involving st+ts. This leaves ∑_{u∈D(G_{e})} ϵ_{u}ϕ(u) = 0. Elements of {ϕ(w) : w ∈ D(G − e)} are linearly independent, so this implies that ϵ_{u} = 0 for all u ∈ D(G_{e}).

We must now consider a linear combination

∑_{v∈D(G/e)} ϵ_{v}ϕ(v_{st}) + ∑_{w∈D(G−[e])} ϵ_{w}ϕ(w ⊔ (st)) = 0.

If x is the vertex in G/e obtained by contracting the edge e, then ϕ(v_{st}) is obtained from ϕ(v) by replacing x by st+ts. Write ϕ(v_{st}) = ϕ(v)_{[st]} +ϕ(v)_{[ts]}, where the former is obtained by replacing x in ϕ(v) by st and the latter is obtained by replacing x in ϕ(v) by ts. Thus the above equation can be rewritten as

∑_{v∈D(G/e)} ϵ_{v} (ϕ(v)_{[st]} + ϕ(v)_{[ts]}) + ∑_{w∈D(G−[e])} ϵ_{w}ϕ(w)(st + ts) = 0.

If we look at those terms involving st, and analogously at those involving ts, we see that

∑_{v∈D(G/e)} ϵ_{v}ϕ(v)_{[st]} + ∑_{w∈D(G−[e])} ϵ_{w}ϕ(w)st = 0.  (7)

Notice that we can identify the sub-chain complex C_{∗}(Δ(G))_{s̃,t̃} of C_{∗}(Δ(G)) generated by strings that do not involve s or t with the sub-chain complex C_{∗}(Δ(G/e))x̃ of C_{∗}(Δ(G/e)) generated by strings that do not involve x. Applying the differential maps ∂_{s} and ∂_{t} to equation (7), we get an equation in C_{∗}(Δ(G))_{s̃,t̃} which is equivalent to the equation

∂_{x} ( ∑_{v∈D(G/e)} ϵ_{v}ϕ(v)) + ∑_{w∈D(G−[e])} ϵ_{w}ϕ(w) = 0,  (8)

in C_{∗}(Δ(G/e))x̃, since deleting both s and t from a term in ϕ(v_{st}), or in ϕ(v)_{[st])}, is equivalent to deleting x from that term in ϕ(v).

Recall that ∂_{x}ϕ(v) = 0 for all v ∈ D(G/e). Therefore, equation (8) reduces to

∑_{w∈D(G−[e])} ϵ_{w}ϕ(w) = 0.

Elements of {ϕ(x) : w ∈ D(G−[e])} are linearly independent, so ϵ_{w} = 0 for all w ∈ D(G−[e]). Finally, equation (6) now simplifies to

∑_{v∈D(G/e)} ϵ_{v}ϕ(v_{st}) = 0,

from which it follows that ϵ_{v} = 0 for all v ∈ D(G/e).

Thus all coefficients in equation (6) must be 0, and the derangement basis associated to G is linearly independent. □

6. Examples

We now consider several families G of graphs, and show that with certain well-chosen orderings of the vertices, the sets {D(G) : G ∈ G} have particularly nice properties. The families considered here are complete graphs, Ferrers graphs for staircase shapes, and unlabeled graphs for the classical and affine Coxeter groups. The results regarding the sets D(G) support previously obtained results in [8] and [3] for boolean numbers.

6.1. Complete graphs. Let K_{n} denote the complete graph on n vertices. It was shown in [8], as well as in [9] in terms of injective words, that the boolean number of the complete graph is equal to the derangement number. That is,

β(K_{n}) = d_{n}.  (9)

This equality was proved independently in both [9] and [8] by demonstrating that the sequences {β(K_{n})} and {d_{n}} satisfy the same recurrence relation and have the same initial values. However, a combinatorial understanding of the identity was lacking. We now justify equation (9) combinatorially, thus giving a satisfying understanding of the relationship between the spheres in Δ(K_{n}) and derangements, by explaining the connection between derangements of {1, …, n} and generators of the homology of Δ(K_{n}).

Proposition 6.1. Considering any ordering of the vertices of K_{n}. Then D(K_{n}) = D_{V (K_{n})}.

Proof. The criteria provided in Theorem 3.11, together with the fact that all possible edges exist in the complete graph, indicate that every possible derangement can be obtained. Thus we see bijectively that D(K_{n}) = D_{V (K_{n})}. □

Note that this could also be shown by a simple counting argument, as follows. Proposition 3.6 shows that D(K_{n}) contains β(K_{n}) distinct derangements, and β(K_{n}) = d_{n} by [9] and [8]. Since D(G) ⊆ D_{V (G)} for all graphs G, and |D_{V (G)}| = d_{|V (G)|}, we see that in fact D(K_{n}) = D_{V (K_{n})}.

Example 6.2. Applying Theorem 5.2 to the complete graph with vertices {1, 2, …, n} gives the homology generators described below, along with the corresponding derangements.

n D(K_{n}) Derangement basis of K_{n}
1 ∅  ∅
2 (12)  (1 ⋄ 2) = 12 + 21
3 (123)  (1 ⋄ (2 ⋄ 3)) = 123 + 132 + 231 + 321
(132)  ((1 ⋄ 3) ⋄ 2) = 132 + 312 + 213 + 231
4 (1234) (1 ⋄ (2 ⋄ (3 ⋄ 4)))

= 1234 + 1243 + 1342 + 1432 + 2341 + 2431 + 3421 + 4321

(1243) (1 ⋄ ((2 ⋄ 4) ⋄ 3))

= 1243 + 1423 + 1324 + 1342 + 2431 + 4231 + 3241 + 3421

(1324) ((1 ⋄ 3) ⋄ (2 ⋄ 4))

= 1324 + 3124 + 1342 + 3142 + 2413 + 2431 + 4213 + 4231

(1342) ((1 ⋄ (3 ⋄ 4)) ⋄ 2)

= 1342 + 1432 + 3412 + 4312 + 2134 + 2143 + 2341 + 2431

(1423) ((1 ⋄ 4) ⋄ (2 ⋄ 3))

= 1423 + 4123 + 1432 + 4132 + 2314 + 2341 + 3214 + 3241

(1432) (((1 ⋄ 4) ⋄ 3) ⋄ 2)

= 1432 + 4132 + 3142 + 3412 + 2143 + 2413 + 2314 + 2341

(12)(34) (1 ⋄ 2)(3 ⋄ 4) = 1234 + 2134 + 1243 + 2143
(13)(24) (1 ⋄ 3)(2 ⋄ 4) = 1324 + 3124 + 1342 + 3142
(14)(23) (1 ⋄ 4)(2 ⋄ 3) = 1423 + 4123 + 1432 + 4132

6.2. Ferrers graphs for staircase shapes. We now use the main result of this paper to give an explanation of an enumerative result obtained in [3] for certain Ferrers graphs.

Definition 6.3. For r ≥ 1, the staircase shape of height r is the Ferrers shape σ_{r} = (r, r − 1, …, 2, 1). The Ferrers graph F_{r} of the staircase shape σ_{r} is the bipartite graph on 2r vertices where r vertices describe the rows of σ_{r}, r vertices describe the columns of σ_{r}, and two vertices are adjacent if there is a square in the corresponding row and column of the shape σ_{r}.

It was shown in [3] that

β(F_{r}) = g_{r}

for all r ≥ 1, where {g_{r}} are the median Genocchi numbers, also called the Genocchi numbers of the second kind. This is sequence A005439 of [10].

Definition 6.4. A permutation w ∈ 𝔖_{2r} has alternating excedances if w(i) > i whenever i is odd and w(i) < i whenever i is even. Such a permutation is always a derangement because w(i) ≠ i for all i. When written in standard cycle form, this means that each odd number is followed by a larger number, and each even number is followed by a smaller number. The set of permutations in 𝔖_{2r} with alternating excedances will be denoted AE_{2r}.

The median Genocchi number g_{r} is equal to the number of permutations w ∈ 𝔖_{2r} such that w has alternating excedances (see [4]); that is,

g_{r} = |AE_{2r}|.

Example 6.5. The second median Genocchi number is g_{2} = 2, and the permutations in 𝔖_{4} with alternating excedances are (12)(34) and (1342).

We now explain why β(F_{r}) = g_{r} by demonstrating an ordering of the vertices of F_{r} for which D(F_{r}) is equal to the set AE_{2r}. The vertices of F_{r} arise from the rows and columns of the staircase shape σ_{r}, so we can define an ordering on the vertices of F_{r} in terms of the staircase shape.

Definition 6.6. Given a staircase shape σ_{r}, label the rows 1, 3, 5, …, 2r−1 so that the labels increase as the lengths of the rows decrease. In contrast, label the columns 2, 4, 6, …, 2r so that the labels decrease as the lengths of the columns decrease. This gives a corresponding ordering on the vertices of F_{r}.

The labeling on the shape σ_{r} is depicted in Figure 1. Therefore, the bipartite graph F_{r} consists of one set of vertices {1, 3, 5, …, 2r−1} and a second set of vertices {2, 4, 6, …, 2r}. The edges in this graph are exactly those of the form {2i + 1, 2j} where i < j. That is, each odd vertex is connected to every even vertex having a larger label. Equivalently, each even vertex is connected to every odd vertex having a smaller label. The correspondingly labeled Ferrers graph for the case r = 4 is given in Figure 2.

Proposition 6.7. For all r ≥ 1, D(F_{r}) = AE_{2r}.

Proof. As noted earlier, elements of AE_{2r} are derangements whose cycle notations are such that every odd number is followed by something larger and every even number is followed by something smaller. It is this description which motivates the linear ordering of the vertices of F_{r}, since, as can be seen in the example of Figure 2, each odd vertex is adjacent to all larger even vertices, and each even vertex is adjacent to all smaller odd vertices.

Suppose that w ∈ AE_{2r}. For any letter t which is not minimal in its cycle in w, there are two key facts to note, both of which follow from the above characterization of AE_{2r}:

(1) λ_{w}(t) is odd and necessarily smaller than t, and

1 3 5 ⋮2r − 1 2r ⋯ 6 4 2

Figure 1. Linear ordering of the rows and columns in the staircase shape σ_{r}.

7 5 3 1 8 6 4 2

Figure 2. Labeling of the Ferrers graph F_{4}.

(2) ρ_{w}(t) contains an even number, which is necessarily at least as large as t.

In F_{r}, every odd vertex is adjacent to all larger even vertices. Therefore λ_{w}(t) is adjacent to at least one element of ρ_{w}(t) in the graph F_{r}. Hence, Theorem 3.11 implies that such a w is an element of D(F_{r}), and thus AE_{2r} ⊆ D(F_{r}).

Now consider w ∈ 𝔖_{2r} \ AE_{2r}. There are two possibilities for the standard cycle form of w: either an odd number is followed by something smaller, or an even number is followed by something larger. Suppose that the first case occurs, and that the odd number is t. By definition, we have λ_{w}(t) ≤ t. Moreover, since t is followed by a smaller number, we know that t is not the minimal letter in its cycle, so in fact λ_{w}(t) < t. Theorem 3.11 says that λ_{w}(t) must be adjacent to an element of ρ_{w}(t) = {t} in F_{r}. However, odd vertices are not adjacent to smaller vertices in F_{r}, so this is a contradiction. Now suppose that there is an even number t followed by a larger number s in the cycle notation of w. Every element of ρ_{w}(s) is greater than or equal to s, and so strictly greater than t. Theorem 3.11 indicates that λ_{w}(s) = t must be adjacent to some element of ρ_{w}(s), but even vertices are not adjacent to larger vertices in F_{r}, so this is a contradiction as well. Therefore w ∉ D(F_{r}), and so D(F_{r}) ⊆ AE_{2r}. □

6.3. Coxeter graphs. In [8], the boolean numbers were given for the unlabeled Coxeter graphs of the classical finite and affine Coxeter groups. We now describe linear orderings of the vertices in each graph and the corresponding derangements arising from these orderings. The most interesting cases are the non-exceptional ones, since there we see patterns in the derangements that explain the previous calculations of β.

Definition 6.8. Given a string S = s_{1}s_{2} ⋯ s_{n} of distinct letters, a valid parsing of S is way to partition the letters of S into parts of length at least 2. We will view the parts as cycles and the product of these cycles as a derangement.

Example 6.9. There is one valid parsing of s_{1}s_{2}: (s_{1}s_{2}). Similarly, there is only one valid parsing of s_{1}s_{2}s_{3}: (s_{1}s_{2}s_{3}). There are two valid parsings of s_{1}s_{2}s_{3}s_{4}: (s_{1}s_{2}s_{3}s_{4}) and (s_{1}s_{2})(s_{3}s_{4}).

If no other conditions are imposed, then it is straightforward to show that the number of valid parsings of s_{1}s_{2} ⋯ s_{n} is f_{n}, the (n − 1)st Fibonacci number.

Definition 6.10. Given a string S, let V P (S) denote the set of all valid parsings of S.

Many of the derangements described in this section will be described in terms of valid parsings. The proofs are fairly straightforward, and details are left to the reader. We will let the standard Coxeter group names indicate the corresponding unlabeled Coxeter graphs. For example, the graph A_{n} consists of an n-vertex path.

Definition 6.11. For a path of n vertices, the path ordering is the labeling in which the vertex labels increase from one end to the other.

Proposition 6.12. (1) Given the path ordering, D(A_{n}) = V P (12 ⋯ n).

(2) For the graph D_{n}, give the path ordering to one path of length n − 1, so that the degree-three vertex is labeled 2; label the remaining leaf n. Then

D(D_{n}) = {p ∈ V P (12n3 ⋯ (n − 2)(n − 1)) : 2 and n are in the same cycle of p}.

(3) For the graph E_{n}, give the path ordering to the path of length n − 1 so that the degree-three vertex is labeled 3; label the remaining leaf n. Then

D(E_{n}) = {p ∈ V P (123n45 ⋯ (n − 1)) : 3 and n are in the same cycle of p}.

The remaining finite Coxeter groups’ graphs are all special cases of A_{n}, and their corresponding derangements can be analogously defined using the path ordering.

Results for the affine Coxeter groups are similar, with the only substantially different case being the group Ã_{n}, which is a cycle on n + 1 vertices.

Proposition 6.13. Consider the ordering of V (Ã_{n}) where the label i is between the labels i ± 1, modulo n. Then

D(Ã_{n}) = V P (12 ⋯ n) ∪

⋃_{k=3}^{n} {p ∈ V P (1k(k + 1) ⋯ n2 ⋯ (k − 1)) : {1, k, …, n} is in the same cycle of p}.

Note that the statements in Theorems 6.12 and 6.13 are such that the valid parsings satisfying the given conditions are always written in standard cycle form.

Example 6.14. With the ordering given above,

D(Ã_{5}) ={(12345), (123)(45), (12)(345), (13452),
(145)(23), (14523), (15)(234), (152)(34), (15234)}.

7. Derangement frequency

Theorem 3.11 characterizes when a derangement w is in the set D(G) for a graph G. We now use this criteria to understand the “frequency” of w in the following sense.

Definition 7.1. Given a derangement w of a finite, totally ordered set V, let f(w) be the number of simple ordered graphs G with vertex set V such that w ∈ D(G), and let

r(w) = \frac{f(w)}{2^{\binom{|V |}{2}}}

The statistic f(w) is the frequency of w and r(w) is the rate of w.

Given a derangement w of V, Theorem 3.11 tells us that a graph G with w ∈ D(G) must contain at least one edge in each of the sets E_{w,t} = {(λ_{w}(t), s) : s ∈ ρ_{w}(t)} for each vertex t. Thus calculating the frequency of a derangement amounts to counting the possible edge sets that contain at least one edge in each E_{w,t}. This is greatly simplified by the following easy observation, the proof of which is left to the reader. It will ease notation in the following discussion to define the set U(w) as the set of vertices that are not minimal in their w-cycles.

Lemma 7.2. Let w be a derangement of a totally ordered set V.

(a) For distinct t ∈ U(w), the sets E_{w,t} are disjoint.

(b) If s is minimal in its w-cycle then E_{w,w(s)} ⊆ E_{w,s}.

Lemma 7.2 shows that to construct a graph G with w ∈ D(G), one can independently choose edges from the sets E_{w,t} with t ∈ U(w) and in doing so also end up with edges from the sets W_{w,s} with s ∉ U(w). From this it is straightforward to derive the following description of the frequency and rate of a derangement.

Proposition 7.3. Let w be a derangement of a totally ordered set V. Then the frequency of w is

f(w) = 2^{\binom{|V |}{2}−∑_{U(w)} |ρ_{w}(x)|} · ∏_{U(w)} (2^{|ρ_{w}(x)|} − 1)

= 2^{\binom{|V |}{2}} · ∏_{U(w)} (1 − \frac{1}{2^{|ρ_{w}(x)|}} ) ,

and the rate of w is

r(w) = ∏_{U(w)} (1 − \frac{1}{2^{|ρ_{w}(x)|}} ) .

Example 7.4. Consider w = (13472)(56) from Example 3.10. Then

f(w) = 2^{14} (2^{1} − 1) (2^{3} − 1) (2^{2} − 1) (2^{1} − 1) (2^{1} − 1) = 2^{14} · 21

and

r(w) = \frac{21}{2^{7}}.

This means that there are 2^{14} · 21 ordered graphs G for which w ∈ D(G), and that of all ordered graphs G on 7 vertices, 21/2^{7} of them have w ∈ D(G).

The frequency and rate function are, in a certain sense, increasing with respect to the sizes of the sets ρ_{w}(t). To make this precise, let D^{k}(V) be the set of derangements of V with k disjoint cycles. For w ∈ D^{k}(V) let θ(w) ∈ (ℤ_{+})^{|V |−k} be the (|V | − k)-tuple consisting of the numbers {|ρ_{w}(t)| : t ∈ U(w)}, written in non-decreasing order. We order the (|V | − k)-tuples {θ(w) : w ∈ D^{k}(V)} via the cartesian order. Using this as a basis for comparing derangements, we obtain the following monotonicity result as a direct consequence of Proposition 7.3.

Example 7.5. Let w = (13472)(56) from Example 3.10, and let w′ = (13427)(56). Then θ(w) = (3, 2, 1, 1, 1) and θ(w′) = (2, 2, 1, 1, 1), so θ(w) > θ(w′).

Corollary 7.6. Let V be an ordered set and let w_{1} and w_{2} be derangements of V with the same number of cycles. If θ(w_{1}) ≤ θ(w_{2}) then f(w_{1}) ≤ f(w_{2}) and r(w_{1}) ≤ r(w_{2}).

We now give examples of the frequency and rate functions for some extremal cases. In each of these, the vertex set is V = {1, …, n}.

Example 7.7. For derangements with a fixed number of cycles, θ(w) is minimized when every vertex that is not minimal in its cycle is followed by a smaller vertex. That is, suppose that ρ_{w}(x) = {x} for each x ∈ U(w), meaning that each cycle can be written as a decreasing sequence. Then the frequency of w is

\frac{2^{\binom{n}{2}}}{2^{|U(w)|}}

and the rate of w is

\frac{1}{2^{|U(w)|}} .

If we allow the number of cycles to vary, then this value is minimized if there is only one value of x which is minimal in its cycle, meaning that the standard cycle form of w has exactly one cycle. In other words, this is minimized for w = (1n ⋯ 432):

f((1n ⋯ 432)) = \frac{2^{\binom{n}{2}}}{2^{n−1}} and r((1n ⋯ 432)) = \frac{1}{2^{n−1}} .

On the other hand, the derangements with the highest rate in this situation are those where the standard cycle form of w has as many cycles as possible, namely ⌊n/2⌋ cycles, in which case the rate of w is

\frac{1}{2^{⌈n/2⌉}} .  (10)

Example 7.8. Suppose that the cycle lengths in the standard cycle form of w are c_{1}, c_{2}, . . .. If, for each non-minimal element in each cycle, |ρ_{w}(x)| is maximal, meaning that each cycle can be written as an increasing sequence, then the frequency of w is

2^{\binom{n}{2}} · ∏_{i} ∏_{k=1}^{c_{i}−1} (1 − \frac{1}{2^{k}} ) .

and the rate of w is

∏_{i} ∏_{k=1}^{c_{i}−1} (1 − \frac{1}{2^{k}} ) .

This value is maximized if there is only one cycle in the standard form of w, and hence c_{1} = n. In other words, this is maximized for w = (1234 ⋯ n):

f((1234 ⋯ n)) = ∏_{k=1}^{n−1} (2^{k} − 1) and r((1234 ⋯ n)) = \frac{∏_{k=1}^{n−1} (2^{k} − 1)}{2^{\binom{n}{2}}}.

On the other hand, the derangements with the lowest rate in this situation are those where the standard cycle form of w has as many cycles as possible, meaning that all cycles are transpositions except possibly for a single 3-cycle in the case when n is odd. If n is even, then the rate of w is

\frac{1}{2^{n/2}} ,  (11)

whereas if n is odd, then the rate of w is

\frac{3}{2^{(n+1)/2}} .  (12)

Notice that varying the number of cycles has the opposite effect in Examples 7.7 and 7.8. Thus we cannot do much to improve Corollary 7.6. Also, observe that expressions (10) and (11) agree (when n is even), as they ought to do. Expressions (10) and (12) disagree (when n is odd), because the 3-cycle in the former situation can be written in decreasing order, whereas the 3-cycle in the latter situation can be written in increasing order.

Acknowledgements

We would like to thank Freyja and Patrek, our other recent collaborations, for allowing us to take the time to finish this paper.

References

[1] A. Björner, Posets, regular CW complexes and Bruhat order, European J. Combin. 5 (1984), 7–16.

[2] A. Björner and M. Wachs, On lexicographically shellable posets, Trans. Amer. Math. Soc. 277 (1983), 323–341.

[3] A. Claesson, S. Kitaev, K. Ragnarsson, and B. E. Tenner, Boolean complexes for Ferrers graphs,

   arXiv:0808.2307.

[4] R. Ehrenborg and E. Steingrímsson, The excedance set of a permutation, Adv. Appl. Math. 24 (2000), 284–299.

[5] F. D. Farmer, Cellular homology for posets, Math. Japon. 23 (1978/79), 607–613.

[6] A. Hatcher, Algebraic Topology, Cambridge University Press, Cambridge, 2002.

[7] J. Jonsson and V. Welker, Complexes of injective words and their commutation classes, Pacific J. Math. 243 (2009), 313–329.

[8] K. Ragnarsson and B. E. Tenner, Homotopy type of the boolean complex of a Coxeter system, Adv. Math. 222 (2009), 409–430.

[9] V. Reiner and P. Webb, The combinatorics of the bar resolution in group cohomology, J. Pure Appl. Algebra 190 (2004), 291–327.

[10] N. J. A. Sloane, The on-line encyclopedia of integer sequences, published electronically at

   http://www.research.att.com/~njas/sequences/.

[11] B. E. Tenner, Pattern avoidance and the Bruhat order, J. Combin. Theory, Ser. A 114 (2007), 888–905.

Department of Mathematical Sciences, DePaul University, Chicago, Illinois

  E-mail address: kragnars@math.depaul.edu, bridget@math.depaul.edu