COMPLEXES OF NOT i-CONNECTED GRAPHS

ERIC BABSON, ANDERS BJÖRNER, SVANTE LINUSSON, JOHN SHARESHIAN, AND VOLKMAR WELKER

Abstract. Complexes of (not) connected graphs, hypergraphs and their homology appear in the construction of knot invariants given by V. Vassiliev [V1, V2, V3]. In this paper we study the complexes of not i-connected k-hypergraphs on n vertices. We show that the complex of not 2-connected graphs has the homotopy type of a wedge of (n − 2)! spheres of dimension 2n − 5. This answers one of the questions raised by Vassiliev [V3] in connection with knot invariants. For this case the S_{n}- action on the homology of the complex is also determined. For complexes of not 2-connected k-hypergraphs we provide a formula for the generating function of the Euler characteristic, and we introduce certain lattices of graphs that encode their topology. We also present partial results for some other cases. In particular, we show that the complex of not (n − 2)-connected graphs is Alexander dual to the complex of partial matchings of the complete graph. For not (n − 3)-connected graphs we provide a formula for the generating function of the Euler characteristic.

1. Introduction

In this paper we study the homotopy type and homology of simplicial complexes whose simplices are the edge sets of not i-connected graphs and hypergraphs on n vertices. The case i = 1 is already well understood (see Proposition 2.1), and here we begin the examination of the topological structure of such complexes for i ≥ 2.

Although our point of view is mainly combinatorial, our original motivation for studying these complexes comes from the theory of Vassiliev invariants in knot theory. By determining the homotopy type of the complex of not 2-connected graphs on n vertices we answer a question posed by V. Vassiliev in [V3], where he presents a new approach to Vassiliev knot invariants using a filtration of the simplicial resolution of the space of not-knots as in [V2]. More precisely, he studies the space Σ of maps f : S^{1} → ℝ^{3} such that f(S^{1}) has multiple points or cusps. The simplicial resolution Σ̃ of Σ is obtained roughly speaking as follows: singular knots are resolved by blowing up each r-fold self-intersection to an (\binom{r}{2} − 1)-simplex, and similarly for the set of cusps. A suitable filtration (see [V3]) of Σ̃, combinatorially defined in terms of these

Key words and phrases. Connected graphs, complexes of graphs, matching, homotopy type, simplicial resolution, knot invariant, S_{n}-character.

Babson, Björner, Linusson and Welker were partially supported by MSRI. Babson was supported by a National Science Foundation postdoctoral fellowship. Linusson was supported by a Swedish Natural Sciences Research Council (NFR) postdoctoral fellowship. Welker was supported by Deutsche Forschungsgemeinschaft (DFG). Research at MSRI is supported in part by NSF grant DMS-9022140.

simplices, gives rise to a spectral sequence that contains the homology of the complex of not 2-connected graphs on n vertices as a basic ingredient.

Our work continues the already fruitful interaction between the theory of Vassiliev invariants and questions in topological and homological combinatorics of graph complexes (see [V1]). The study of complexes of not i-connected graphs has intriguing combinatorial and algebraic aspects as well. For example, such aspects become apparent when considering the complex of not (n − 2)-connected graphs on n vertices. In Section 7 this complex is shown to be Alexander dual to the complex of partial matchings of the complete graph on n vertices. These matching complexes, along with complexes of partial matchings of bipartite graphs, have previously been studied for other reasons, see [BLVZ]. In each case for which we calculate the Betti numbers, we detect nontrivial homology. For (n−3)-connected graphs (see Section 8) and for most complexes of not 2-connected hypergraphs (see Section 6) we have been unable to compute the Betti numbers explicitly, but we do determine the generating function of their reduced Euler characteristics. The homology is seen to be nontrivial in almost all of these cases.

Surprisingly, these non-vanishing phenomena are suggested by a result motivated by a conjecture in complexity theory. The conjecture states that complexes of graphs on n vertices having some non-trivial monotone graph property – like being not iconnected – are evasive (see for example [KSS]). Kahn, Saks & Sturtevant [KSS] showed that non-evasive complexes are contractible. In many naturally arising cases, including those examined here, the converse is true and evasive complexes in fact have non-vanishing reduced Euler characteristics.

In Section 4 we study the action of the symmetric group on the complex of not 2-connected graphs induced by its natural action on the vertices. This action induces a representation of S_{n} on the homology groups of the complex, which we determine. Using the representation, we deduce upper bounds on the number of Vassiliev invariants of a given bi-order. This representation coincides with a recently well studied representation which appears in the work of Robinson & Whitehouse [RW, Wh], Kontsevich [K], Getzler & Kapranov [GK], Mathieu [Ma], Hanlon & Stanley [H2, HS] and Sundaram [Su].

Acknowledgment: We are grateful to V. Vassiliev for inspiring discussions and hints, which sparked our interest and initiated this research. All computer calculations presented in this paper were performed using a Mathematica^{\begin{matrix}c \\ ◯ \end{matrix}} package designed by Vic Reiner and a C-Program by Frank Heckenbach.

2. Preliminaries

We now introduce the basic concepts used in this paper. By a graph G = (V (G), E(G)) we mean a loopless graph without multiple edges on the vertex set V (G) and with edge set E(G) ⊆ \binom{V (G)}{2}. Our standard vertex set will be the set [n] := \{1, 2, …, n\}. A graph G is called connected if for any two distinct vertices v, v′ ∈ V (G) there is a path from v to v′ in G, that is, a sequence of edges {v_{1}, v_{2}}, {v_{2}, v_{3}}, …, {v_{l−1}, v_{l}} ∈ E(G) such that v = v_{1} and v′ = v_{l}. Such a path will sometimes be denoted by v_{1}, v_{2}, …, v_{l}. The size of a graph G is |V (G)|.

A graph G is called i-connected, for a number i such that 0 < i < |V (G)|, if for any j vertices v_{1}, …, v_{j} ∈ V (G), j < i, the graph G′ that is obtained from G by deleting the vertices v_{1}, …, v_{j} and their adjacent edges is connected. Equivalently, G is i-connected if and only if for every pair v, v′ of not adjacent vertices there are at least i paths from v to v′ that are pairwise vertex disjoint except at their endpoints.

A graph with at least i + 1 vertices which is not i-connected is also called (i-1)- separable, and a 1-separable (that is, not 2-connected) graph will often be called just separable. Of course, if G = (V (G), E(G)) is a graph that is not i-connected for some i ≥ 1 then for any subset E′ ⊆ E(G) the graph G′ = (V (G), E′) on the same vertex set is not i-connected either. Hence if we fix an n-element vertex set V and identify a graph with the set of its edges, then we may regard the set of not i-connected graphs on V as a simplicial complex.

Definition: Δ_{n}^{i} is the complex of not i-connected graphs on n vertices.

For a graph G and a vertex v we denote by G − v the graph that is obtained from G by deleting the vertex v from its set of vertices and deleting all edges emerging from v from the set of edges. If v and w are two distinct vertices of G then we denote by vw the two-element set {v, w}, by G \ vw the graph (V (G), E(G) \ {vw}), and by G + vw the graph (V (G), E(G) ∪ {vw}). Note that (by definition) if xy ∈ E(G) then G + xy = G and if xy ∉ E(G) then G \ xy = G. A subset V′ ⊆ V (G) of the vertex-set of a graph G = (V (G), E(G)) is called a cutset if the graph obtained from G by deleting the vertices in V′ and all adjacent edges is not connected. In particular, a graph is i-separable if and only if there is a cutset of cardinality i. A cutset of cardinality 1 is also called a cutpoint.

More generally, one may consider complexes of not i-connected k-uniform hypergraphs. Recall that a k-uniform hypergraph on a vertex set V is a subset E of the set of k-element subsets \binom{V}{k} of V. We will call the k-uniform hypergraphs k-graphs for short. Note that a 2-graph is just a graph. A k-graph is called i-connected if its underlying 2-graph is i-connected. The underlying 2-graph of a k-graph E is the graph on V whose edge set contains a k-clique on {v_{1}, …, v_{k}} for each hyperedge {v_{1}, …, v_{k}} ∈ E.

Definition: Δ_{n,k}^{i} is the complex of all not i-connected k-graphs on n vertices.

Cutsets and cutpoints are defined analogously for k-graphs as they were for graphs. For the notation related to simplicial complexes and partially ordered sets – posets

for short – used in this paper, we refer the reader to Section 10.

Let us now review some known results. For i = 1 we have that Δ_{n}^{1} and Δ_{n,k}^{1} are the complexes of disconnected graphs, resp., disconnected k-graphs. The topology of Δ_{n,k}^{1} is well understood up to homotopy type.

Proposition 2.1. Let n ≥ 2. Then (i) The complex Δ_{n}^{1} is homotopy equivalent to a wedge of (n−1)! spheres of dimen-

sion n − 3. In particular, H̃_{i}(Δ_{n}^{1}) = 0 for i ≠ n − 3 and H̃_{n−3}(Δ_{n}^{1}) ≅ ℤ^{(n−1)!}. (ii) The complex Δ_{n,k}^{1} is homotopy equivalent to a wedge of spheres of dimensions

n − (k − 2) · t − 3, 1 ≤ t ≤ ⌊\frac{n}{k}⌋. In particular, the homology of Δ_{n,k}^{i} is free and concentrated in dimensions n − (k − 2) · t − 3, 1 ≤ t ≤ ⌊\frac{n}{k}⌋.

Part (i) follows from well-known properties of partition lattices (see [B, BWa, St2]) together with the crosscut theorem (see [B]). An alternative proof is provided in [V1]. Part (ii) was established by Björner and Welker in [BWe]. See Theorem 4.5 and Section 7.8 of [BWe] for exact numerical information on the homology of Δ_{n,k}^{1}.

The character of the symmetric group for the representation on H̃_{n−3}(Δ_{n}^{1}) was determined by Stanley in [St2] in terms of the character of S_{n} on the homology of the partition lattice. These two characters are equal by an equivariant version of the crosscut theorem. The character of the symmetric group on the homology of Δ_{n,k}^{1} was given by Sundaram & Wachs [SW].

Unless otherwise explicitly stated, all homology groups in this paper have integer coefficients.

3. Homology and homotopy type of Δ_{n}^{2}

The main theorem of this section gives a complete description of the homotopy type of Δ_{n}^{2}.

Theorem 3.1. Let n ≥ 3. Then Δ_{n}^{2} has the homotopy type of a wedge of (n − 2)! spheres of dimension 2n − 5.

Remark: This result was circulated for several months as a conjecture. During that time, the Euler characteristic of Δ_{n}^{2} was calculated by Rodica Simion [Si]. The theorem was proved independently and simultaneously, almost to the day, by V. Turchin in Moscow, in a homology version [V3] that is equivalent to our result by some general arguments from homotopy theory.

For any natural number k, let B_{k} be the Boolean algebra on k elements (i.e., the lattice of subsets of a k-element set) and let Π_{k} be the lattice of partitions of a k-set into subsets, ordered by refinement. It is well-known that Δ(\overline{B_{k}}) — being the barycentric subdivision of a simplex boundary — is homeomorphic to a (k − 2)- sphere, and that Δ(\overline{Π_{k}}) ≃ Δ_{k}^{1} has the homotopy type of a wedge of (k − 1)! spheres of dimension k − 3 (see Proposition 2.1 (i) and its references). These facts imply the following.

Lemma 3.2. Δ(\overline{B_{k} × Π_{k}}) has the homotopy type of a wedge of (k − 1)! spheres of dimension 2k − 3.

Proof: Let ∅ and [k] be the least element and top element of B_{k}, and let 1| ⋯ |k and |1 ⋯ k| be the least and top elements of Π_{k}. Apply the Homotopy Complementation Formula 10.3 (ii) to p = (∅, |1 ⋯ k|). The set of complements of p in B_{k} × Π_{k} consists of the single element q = ([k], 1| ⋯ |k). Obviously, Δ((ˆ0, q)) ≅ Δ(\overline{B_{k}}) and Δ((q, ˆ1)) ≅ Δ(\overline{Π_{k}}). Then by Formula 10.3 (i) we have

Δ(\overline{B_{k} × Π_{k}}) ≃ Σ(Δ(\overline{B_{k}}) ∗ Δ(\overline{Π_{k}})).

Since the join of a wedge of n spheres of dimension i with a wedge of m spheres of dimension j is homotopy equivalent to a wedge of nm spheres of dimension i+j+1 (see for example [BWe, Lemma 2.5 (ii)]) the assertion follows. Recall that suspension can be regarded as a join with a 0-sphere and that the join operation is associative.

Thus, in order to prove Theorem 3.1 it suffices to demonstrate that Δ_{n}^{2} is homotopy equivalent to Δ(\overline{B_{n−1} × Π_{n−1}}). In order to state more precisely what we will prove, we make the following definitions.

Definition: For x ∈ [n] and any graph G on [n], N_{G}(x) is the neighborhood of x in G, i.e. N_{G}(x) = {y ∈ [n] : xy ∈ E(G)}, and π(x, G) is the partition of the set [n] \ {x} determined by the connected components of G − x.

Definition: ϕ : \overline{Lat(Δ_{n}^{2})} → \overline{B_{n−1} × Π_{n−1}} is the map of posets given by G ↦ (N_{G}(1), π(1, G)), and ϕ^{∗} : Δ(\overline{Lat(Δ_{n}^{2})}) → Δ(\overline{B_{n−1} × Π_{n−1}}) is the simplicial map induced by ϕ.

Note that if G is a graph on [n] such that N_{G}(1) = {2, …, n} and G−1 is connected, then G is 2-connected. On the other hand, if N_{G}(1) = ∅ and π(1, G) = 2|3| … |n then G is the empty graph. Thus ϕ is well-defined. It is clear that ϕ is order preserving, so ϕ^{∗} is well-defined. We can now state the key technical result, from which (in view of Lemma 3.2) Theorem 3.1 follows.

Lemma 3.3. The simplicial map ϕ^{∗} is a homotopy equivalence.

To prove Lemma 3.3 we use Quillen’s Fiber Lemma (see Proposition 10.1). In our situation this says that if for each (S, π) ∈ \overline{B_{n−1} × Π_{n−1}} the order complex of the poset ϕ_{≤}^{−1}(S, π) = \{G ∈ \overline{Lat(Δ_{n}^{2})} : ϕ(G) ≤ (S, π)\} is contractible, then ϕ^{∗} is a

homotopy equivalence. If π ≠ |2 ⋯ n| then ϕ_{≤}^{−1}((S, π)) has a top element, namely the graph G such that 1t is an edge of G for t ∈ S and G induces the complete graph on each block of π. So assume that π = |2 ⋯ n|. If |S| ≤ 1 then there is also a top element in ϕ_{≤}^{−1}((S, π)), namely the graph G which induces a clique on {2, …, n} and has N_{G}(1) = S. If S = {2, …, n} then (S, π) does not lie in the proper part of B_{n−1} × Π_{n−1}. In summary, it remains to consider the fibers ϕ_{≤}^{−1}(S, π) for pairs (S, π) such that π = |2 ⋯ n| and S ⊆ {2, …, n} with 2 ≤ |S| ≤ n − 2. To handle these remaining cases, we make the following definitions.

Definition:

(1) For 2 ≤ k ≤ n − 1, Δ(k) = {G ∈ Δ_{n}^{2} : N_{G}(1) ⊆ {2, …, k}}.

(2) For 3 ≤ k ≤ n − 1, Δ(k − 1, k) = {G ∈ Δ(k − 1) : G + 1k ∈ Δ(k)}.

Note that if (S, π) = ({2, …, k} , |2 ⋯ n|) then Δ(k) = ϕ_{≤}^{−1}(S, π). Also, Δ(k − 1, k) consists of those graphs in Δ(k − 1) which do not become 2-connected when the edge 1k is added.

By the above discussion and the fact that the natural action of S_{n} on Lat(Δ_{n}^{2}) is order preserving, Lemma 3.3 follows immediately from the next lemma.

Lemma 3.4. For 2 ≤ k ≤ n − 1, Δ(k) is contractible.

The proof of Lemma 3.4 proceeds by induction on k, the case k = 2 having been handled above. The inductive proof is therefore achieved by the combination of the following two lemmas.

Lemma 3.5. Let 3 ≤ k ≤ n − 1. If Δ(k − 1) and Δ(k − 1, k) are contractible, then so is Δ(k).

Proof: Let ⋆(1k) be the subcomplex of Δ(k) consisting of graphs that either contain the edge 1k or else can be extended within Δ(k) to contain 1k. Then ⋆(1k) is a cone with base Δ(k − 1, k) and apex 1k, and we have

Δ(k) = Δ(k − 1) ∪ ⋆(1k),
Δ(k − 1, k) = Δ(k − 1) ∩ ⋆(1k).

Thus, Δ(k) is a union of two contractible complexes with contractible intersection, and hence Δ(k) is itself contractible (see e.g. [B, Lemma 10.3]).

Lemma 3.6. For 3 ≤ k ≤ n − 1, Δ(k − 1, k) is contractible.

To prove Lemma 3.6 we will use a special case of Forman’s discrete Morse theory (see [F], and for this case also [Ch]). The following works for regular cell complexes, but we will only need the simplicial case. Definition: Let Σ be a simplicial complex.

(1) D(Σ) is the digraph whose vertex set is Σ and whose edges are the edges in the Hasse diagram of Lat(Σ) \ {ˆ1}, all directed downward.

(2) For any set X of edges in D(Σ), D_{X}(Σ) is the digraph obtained from D(Σ) by reversing the direction of the edges in X, so these edges are directed upward while the remaining edges are directed downward.

Before we can formulate the following lemma we have to recall some basic facts about collapsibility (see for example [B]). Given a simplicial complex Σ, a face σ ∈ Σ is called free if σ is not maximal and is contained in a unique maximal face of Σ. If σ is free in Σ then passing from Σ to the complex Σ \ {τ : τ ⊇ σ} is called an elementary collapse of Σ. If we can obtain a single vertex by applying a sequence of elementary collapses to a complex Σ, then Σ is called collapsible. Since it is easily seen that an elementary collapse of Σ is a strong deformation retraction it follows that collapsible complexes are contractible.

Proposition 3.7. Let Σ be a simplicial complex. If D(Σ) contains a perfect matching M such that D_{M}(Σ) is acyclic, then Σ is collapsible.

Proof: This is a special case of Corollary 3.5 of [F], and this case is easily proved by induction on |Σ|. If Σ = {∅, {x}} then the claim is clearly true. If |Σ| > 2, let x be a source in D_{M}(Σ), which must exist since D_{M}(Σ) contains no directed cycle. It is easy to see that x must be a free face of Σ which is properly contained in a unique face y ∈ Σ. Now Σ is collapsible to the complex obtained by removing x and y, and we can apply the inductive hypothesis.

We call a perfect matching of the type described in Proposition 3.7 an acyclic perfect matching on D(Σ). Our goal is to produce an acyclic perfect matching on D(Δ(k − 1, k)). The following easy result will be useful.

Lemma 3.8. Let Σ be a simplicial complex, let M be a matching on D(Σ) and let F_{0} → F_{1} → … → F_{r} → F_{0} be a directed cycle in D_{M}(Σ). Then there is some dimension d such that dim(F_{i}) ∈ {d, d + 1} for all i ∈ [r].

Proof: If the F_{i} have more than two distinct dimensions then some F_{i} must be incident to two upward directed edges. This contradicts the fact that M is a matching, and the result follows immediately.

Before proceeding with the proof of Lemma 3.6 we make some technical definitions. Definition: Consider separable graphs on the vertex set [n].

(1) We denote the set of cutpoints of such a graph G by Cut(G).

(2) For fixed k ∈ {3, …, n − 1}, let (a) I(k) := {G ∈ Δ(k − 1, k) | N_{G}(1) = ∅}.

(b) J(k) := {G ∈ Δ(k − 1, k) | N_{G}(1) ≠ ∅ and Cut(G + 1k) ≠ {1}}.

(c) F (k) := {G ∈ Δ(k − 1, k) | Cut(G + 1k) = {1}}.

Note that Δ(k − 1, k) is the disjoint union of I(k), J(k) and F (k), and that both I(k) and I(k) ∪ J(k) are subcomplexes of Δ(k − 1, k).

The following lemma implies Lemma 3.6, and therefore completes the proof of Theorem 3.1.

Lemma 3.9. For any k ∈ {3, …, n − 1}, D(Δ(k − 1, k)) admits an acyclic perfect matching.

Proof: This proof will be carried out in three steps. We will construct an acyclic perfect matching first for D(I(k)), then for D(I(k) ∪ J(k)), and finally for D(Δ(k − 1, k)).

Step 1: D(I(k)) admits an acyclic perfect matching.

Note that I(k) contains a unique maximal face, namely the complete graph on {2, …, n}. Thus I(k) is a simplex and it is easy to see that the matching M = {G + 23 → G \ 23|G ∈ I(k)} is an acyclic perfect matching on D(I(k)).

Step 2: D(I(k) ∪ J(k)) admits an acyclic perfect matching.

It suffices to show that there exists a matching M^{∗} consisting of edges between elements of J(k) which covers all the elements of J(k), and such that D_{M^{∗}}(I(k)∪J(k)) is acyclic. If M^{∗} is such a matching, let M^{∘} be an acyclic perfect matching on D(I(k)) and set M = M^{∗} ∪ M^{∘}. Then M is a perfect matching on D(I(k) ∪ J(k)) which contains no edges between I(k) and J(k), so that any directed cycle in D_{M}(I(k)) cannot cover points from both I(k) and J(k). It follows immediately that M is acyclic.

Now let G ∈ J(k) and let c ∈ Cut(G + 1k), c ≠ 1. Let x = min {N_{G}(1)}. If xk ∈ E(G) then clearly G \ xk ∈ J(k). If c ∉ {x, k} then since 1k and 1x are edges of G + 1k, x and k lie in the same connected component of (G + 1k) − c. If c ∈ {x, k} then clearly c is a cutpoint of G + xk + 1k. In any case, c ∈ Cut(G + xk + 1k) and G + xk ∈ J(k).

Let M^{∗} consist of all edges G + xk → G \ xk, where x is determined as above. Clearly M^{∗} is a matching which covers all points in J(k). Assume for contradiction that A_{1} → B_{1} → A_{2} → B_{2} → … → B_{r} → A_{1} is a directed cycle in D_{M^{∗}}(I(k)∪J(k)). Clearly all the A_{i} and all the B_{i} are in J(k), and by Lemma 3.8 we may assume that for each i there are edges α_{i} and β_{i} such that B_{i} = A_{i} + α_{i} and A_{i+1} = B_{i} \ β_{i}. Thus A = A + α_{1} \ β_{1} + … + α_{r} \ β_{r} and {α_{i}} = {β_{i}}. By the definition of M^{∗}, no α_{i} = x_{i}k contains 1, so no β_{i} contains 1. It follows that N_{A_{1}}(1) = N_{B_{1}}(1) = N_{A_{2}}(1) = … = N_{B_{r}}(1). By the choice of the x_{i}’s this forces α_{1} = α_{2} = … = α_{r}, which is clearly impossible.

Step 3: D(Δ(k − 1, k)) admits an acyclic perfect matching.

As in Step 2, it suffices to produce a matching M^{∗} on edges connecting elements of F (k) which covers all points in F (k) and such that D_{M^{∗}}(Δ(k − 1, k)) is acyclic.

Let G ∈ F (k). Then (G+1k)−1 splits into connected components C_{1}, …, C_{s} such that for each i ∈ [s] the subgraph of G + 1k induced on V (C_{i}) ∪ {1} is 2-connected. We may assume that n ∈ V (C_{1}). Note that since k < n, 1n ∉ G + 1k. Define S(G) to be the set of all x ∈ V (C_{1}) ∩ N_{G+1k}(1) such that there is a path P = 1, x, …, n in G + 1k with P ∩ N_{G+1k}(1) = {x}.

We claim that |S(G)| > 1. Indeed, let 1, x, …, n be a shortest path from 1 to n in G + 1k. Clearly x ∈ S(G). Since the subgraph of G + 1k induced on V (C_{1}) ∪ {1} is 2-connected and x ≠ n, there exists a path from 1 to n in this graph which does not contain x. Let 1, y, …, n be a shortest such path. Then y ∈ S(G).

Let x, y be the two smallest elements of S(G). If xy ∉ G then clearly G+xy ∈ F (k) and S(G+xy) = S(G). Now assume xy ∈ G and let H be the subgraph of G\xy+1k induced on V (C_{1}) ∪ {1}. If d is a cutpoint of H then x and y are in different components of H − d (otherwise d is a cutpoint of the subgraph of G + 1k induced on V (C_{1}) ∪ {1}). However, there is a cycle 1, x, …, y, 1 in H. Thus there is no such cutpoint d and H is 2-connected. It follows that G\xy ∈ F (k) and S(G\xy) = S(G).

Now, let M^{∗} consist of the edges G + xy → G \ xy where x, y are determined as above. Then M^{∗} is a matching which consists of edges connecting points in F (k) and covers all points in F (k). It remains to show that D_{M^{∗}}(Δ(k − 1, k)) is acyclic.

Assume for contradiction that A_{1} → B_{1} → A_{2} → … → B_{r} → A_{1} is a directed cycle in D_{M^{∗}}(Δ(k − 1, k)). As in Step 2, we may assume that there are edges α_{i} and β_{i} such that B_{i} = A_{i} + α_{i}, A_{i+1} = B_{i} \ β_{i} and {α_{i}} = {β_{i}}.

By the definition of M^{∗}, each α_{i} connects two elements of N_{B_{i}+1k}(1) = N_{A_{i}+1k}(1), so no β_{i} contains 1. Thus N_{A_{i}}(1) = N_{B_{j}}(1) for all i, j, and each β_{i} connects two elements of N_{B_{i}+1k}(1) = N_{A_{i+1}+1k}(1). Write α_{1} = xy. Then β_{1} ≠ xy, and in A_{2} + 1k, x and y are still the two smallest neighbors of 1 which are contained in paths from 1 to n which intersect N_{A_{2}+1k}(1) exactly once. Thus α_{2} = xy = α_{1}, giving the desired contradiction.

4. The character for the action of S_{n} on H̃_{2n−5}(Δ_{n}^{2})

In view of Theorem 3.1 it is natural to investigate the representation of the symmetric group S_{n} on the only non-zero homology group of Δ_{n}^{2}, induced by the obvious action. In this section we consider homology with complex coefficients, hence all representations are over ℂ. In many of the computations below, we actually determine character values for the representation of S_{n} on the only non-zero homology group of Δ(\overline{Lat(Δ_{n}^{2})}), which is easily seen to be the same as the representation described above.

Definition:

(i) We denote by ω_{n}^{2} the character of S_{n} given by g ↦ T race(g, H̃_{2n−5}(Δ_{n}^{2})). (ii) Let C_{n} be a cyclic subgroup of S_{n} generated by a full n-cycle. We denote by

ℓie_{n} the character of S_{n} induced from the character on C_{n} which takes the value e^{\frac{2πi}{n}} on a fixed generator. It is well known (see e.g. [Re, Chapter 8]) that ℓie_{n} is the character of S_{n} on the multigraded piece of the free Lie algebra generated by n variables.

For the rest of this section we let S_{n−1} be the stabilizer of the point 1 in the natural action of S_{n} on the set [n].

Theorem 4.1. The character ω_{n}^{2} is given by

ω_{n}^{2} = ℓie_{n−1} ↑_{S_{n−1}}^{S_{n}} −ℓie_{n}.

The proof will follow a sequence of lemmas establishing the main steps.

Lemma 4.2. If g ∈ S_{n−1} then ω_{n}^{2}(g) = ℓie_{n−1}(g).

Proof: It is easily seen that the map ϕ : \overline{Lat(Δ_{n}^{2})} → \overline{B_{n−1} × Π_{n−1}}, defined in the previous section, commutes with the actions of S_{n−1} on the two posets. Thus the induced map on homology is S_{n−1}-equivariant and is an S_{n−1}-module isomorphism by Lemma 3.3. Thus, the characters of S_{n−1} on the homology of Δ_{n}^{2} and on the homology of Δ(\overline{B_{n−1} × Π_{n−1}}) coincide. By an equivariant version of Proposition 10.3 (see [We]), Δ(\overline{B_{n−1} × Π_{n−1}}) has the S_{n−1}-homotopy type of Σ(Δ(\overline{B_{n−1}}) ∗ Δ(\overline{Π_{n−1}})), where the group S_{n−1} acts diagonally on Δ(\overline{B_{n−1}}) ∗ Δ(\overline{Π_{n−1}}). Thus the character of S_{n−1} on the homology of Δ(\overline{B_{n−1} × Π_{n−1}}) is given by the product of the characters of S_{n−1} on H̃_{∗}(Δ(\overline{B_{n−1}})) and H̃_{∗}(Δ(\overline{Π_{n−1}})). The character of S_{n−1} on H̃_{∗}(Δ(\overline{B_{n−1}})) is rather easily seen to be the sign-character of S_{n−1} (see [St2]). The character of S_{n−1} on H̃_{∗}(Δ(\overline{Π_{n−1}})) was determined in [St2] as sign_{n−1} · ℓie_{n−1}. This implies the assertion.

Since every element of S_{n} which has a fixed point is conjugate to an element of S_{n−1}, it remains to determine ω_{n}^{2}(g) for all fixed-point-free g ∈ S_{n}.

Definition: Let g ∈ S_{n}. We denote by L^{g} the poset of faces of Δ_{n}^{2} which are fixed by g, and by g^{∗} the element of S_{n+1} which fixes n + 1 and acts as g does on [n].

Write ˆ0 for the empty graph in L^{g}, which is the unique minimum element of L^{g}, and for any poset P let μ_{P} be the Möbius function on P.

Lemma 4.3. For g ∈ S_{n}, ω_{n}^{2}(g) = ∑_{G∈L^{g}} μ_{L^{g}}(ˆ0, G).

Proof: It is well-known (see e.g. [B, (13.5)]) that if a group acts on a bounded poset P then for any group element g we have

μ_{P^{g}}(ˆ0, ˆ1) = ∑_{i}(−1)^{i}T r(g, H̃_{i}(Δ(\overline{P}))).

In the case under consideration, the only nonzero reduced homology group is the one in dimension 2n − 5, so the lemma follows immediately from the definition of the Möbius function.

The next two lemmas will be used to determine ω_{n}^{2}(g) when g is fixed-point-free.

Lemma 4.4. Let G be a graph whose automorphism group acts transitively on V (G). If G is connected then G is 2-connected.

Proof: Let v be a leaf of some spanning tree in the connected graph G. Then v is not a cutpoint. Since Aut(G) is transitive on vertices there cannot be any other cutpoints. Hence G is 2-connected.

Lemma 4.5. Let g ∈ S_{n} be fixed-point-free. Write g as a product of disjoint cycles, g = g_{1} … g_{r}. Let V_{i} = supp(g_{i}). Let G ∈ L^{g} be connected and let x ∈ Cut(G) with x ∈ V_{j}. Then there exists some connected component C of G − x such that V_{j} \ {x} ⊆ C and C ∩ V_{i} ≠ ∅ for all i ∈ [r].

Proof: Let G_{j} be the graph on V_{j} such that an edge yz is in E(G_{j}) if yz ∈ E(G) or if there is a path P from y to z in E(G) such that P ∩ V_{j} = {y, z}. Since G is connected, so is G_{j}. Also, the group generated by g_{j} is a group of automorphisms of G_{j} which acts transitively on V_{j}. By Lemma 4.4, G_{j} is 2-connected. It follows that all elements of V_{j} \ {x} are in the same connected component of G − x. Now for i ≠ j, let P be a path of shortest length connecting some y ∈ V_{i} with some z ∈ V_{j}. If z = x replace P with g(P). Now P contains no vertices from V_{i} ∪V_{j} other than y and z ≠ x. Thus P is a path in G − x and y lies in the component of G − x containing V_{j} \ {x}.

We can now determine the values of ω_{n}^{2} on fixed-point-free elements of S_{n}.

Lemma 4.6. Let g ∈ S_{n} be fixed-point-free. Then ω_{n}^{2}(g) = −ω_{n+1}^{2}(g^{∗}).

Proof: As usual we write ˆ0 for the empty graph. By Lemma 4.3 we have

ω_{n+1}^{2}(g^{∗}) = ∑_{G∈L^{g^{∗}}} μ_{L^{g^{∗}}}(ˆ0, G).

Let M^{g} be the poset of all graphs on [n] which are fixed by g. Note that if G ∈ L^{g^{∗}} then G − (n + 1) ∈ M^{g}. For F ∈ M^{g} let D(F) be the set of all G ∈ L^{g^{∗}} such that G − (n + 1) = F. We have

ω_{n+1}^{2}(g^{∗}) = ∑_{F ∈M^{g}} ∑_{G∈D(F)} μ_{L^{g^{∗}}}(ˆ0, G).

Any G ∈ L^{g^{∗}} is a union of ⟨g^{∗}⟩-orbits on \binom{[n+1]}{2}. Let o(G) be the number of such orbits. It is easy to see that μ_{L^{g^{∗}}}(ˆ0, G) = (−1)^{o(G)}. Let p(G) be the number of such orbits containing edges covering the point n + 1. Applying the previous argument to M^{g}, we get for any F ∈ M^{g}

∑_{G∈D(F)} μ_{L^{g^{∗}}}(ˆ0, G) = μ_{M^{g}}(ˆ0, F) ∑_{G∈D(F)}(−1)^{p(G)}.

We will examine this sum for each F ∈ M^{g}, looking separately at the cases where F is disconnected, connected but not 2-connected, and 2-connected. Write g as a product of disjoint cycles, g = g_{1} … g_{r} and let V_{i} = supp(g_{i}). Note that if v ∈ V_{i} and G ∈ L^{g^{∗}} with {v, n + 1} ∈ G, then the ⟨g^{∗}⟩-orbit containing {v, n + 1} consists of the edges {w, n + 1} for all w ∈ V_{i}, and is contained in E(G). Also, p(G) is simply the number of such orbits. Let O(g) be the set of all such orbits, and for S ⊆ O(g) let G(S) be the graph induced on the edges which are contained in elements of S. For F ∈ M^{g} define

Σ(F) := {S ⊆ O(g) : F ∪ G(S) ∈ L^{g^{∗}}} .

Note that Σ(F) is a simplicial complex on O(g). Let P (F) = Lat(Σ(F)) \ \left\{{ \atop ˆ1}\right\}. By the above arguments we have

∑_{G∈D(F)} μ_{L^{g^{∗}}}(ˆ0, G) = μ_{M^{g}}(ˆ0, F) ∑_{S∈P (F)} μ_{P (F)}(ˆ0, S).

We now examine the three cases.

Case 1: F is not connected.

Then P (F) is the Boolean algebra on O(g), since n + 1 is a cutpoint of F ∪ G(S) for all S ⊆ O(g). It follows immediately that

∑_{G∈D(F)} μ_{L^{g^{∗}}}(ˆ0, G) = 0.

Case 2: F is connected but not 2-connected.

We will use the block decomposition described in Proposition 5.1 of the following section. Given a connected but not 2-connected graph F ∈ M^{g}, let T (F) be the bipartite graph whose vertices are the vertices of F and the blocks of F, with {v, W_{i}} an edge if and only if v ∈ W_{i}. It is easy to see that T (F) is a tree and that ⟨g⟩ is a group of automorphisms of T (F) which preserves each part of the given bipartition. It follows that g fixes a vertex of T (F) (see [L]). Since g fixes no vertex of F, g must fix some block B of F. This means that there is some nonempty J ⊂ [r] such that B = ∪_{j∈J}V_{j}. Let S be the set of all orbits in O(g) which contain edges that include vertices in B. We will show that every maximal element of P (F) contains S, from which it follows immediately that

∑_{G∈D(F)} μ_{L^{g^{∗}}}(ˆ0, G) = 0.

Let G ∈ D(F) and let c ∈ Cut(G). Since F is connected, c ≠ n + 1. Also, if N_{G}(n + 1) ≠ ∅ then since g is fixed-point-free c must be a cutpoint of F. If N_{G}(n + 1) = ∅ then every x ∈ [n] cuts G, so in any case we may assume c ∈ Cut(F). Let c ∈ V_{i}. By Lemma 4.5, there is some connected component C of F − c which contains V_{i} \ {c} and at least one element of each V_{j}. Since B is 2-connected and B ∩ C ≠ ∅, we must have B ⊆ C.

We will now show that c must be a cutpoint of G ∪ S. If N_{G}(n + 1) = ∅ then adding S to G simply moves the previously isolated point n + 1 into the connected component of G−c which contains C. However, there is a component of F −c besides C, which remains separated from C in G − c. Now, assume that N_{G}(n + 1) ≠ ∅. Then there exists some set I such that N_{G}(n + 1) = ∪_{i∈I}V_{i}. The component of G − c containing C contains elements of each V_{i}, and it follows that n + 1 must also be in this component. Thus, adding S to G does not reduce the number of components of G − c.

Case 3: F is 2-connected.

In this case the only G ∈ D(F) is that for which N_{G}(n+1) = ∅. Indeed, since each V_{i} has at least two elements we cannot have |N_{G}(n + 1)| = 1, and the claim follows. Thus

∑_{G∈D(F)} μ_{L^{g^{∗}}}(ˆ0, G) = μ_{M^{g}}(ˆ0, F).

Let K^{g} be the set of 2-connected graphs in M^{g}. Combining the information from the three cases we have shown that

ω_{n+1}^{2}(g^{∗}) = ∑_{F ∈K^{g}} μ_{M^{g}}(ˆ0, F).

By definition of the Möbius function and the fact that M^{g} has a maximum element, we have

∑_{F ∈K^{g}} μ_{M^{g}}(ˆ0, F) = − ∑_{F ∈L^{g}} μ_{L^{g}}(ˆ0, F) = −ω_{n}^{2}(g),

and the proof is complete.

Proof of Theorem 4.1: Set ρ_{n} = ℓie_{n−1} ↑_{S_{n−1}}^{S_{n}} −ℓie_{n}. We must show that ρ_{n}(g) = ω_{n}^{2}(g) for all g ∈ S_{n}.

By the definition of induced characters, if g ∈ S_{n} is not the product of disjoint cycles of the same length then ℓie_{n}(g) = 0. We will assume from now on that any g ∈ S_{n} which fixes a point is contained in S_{n−1} (so by our convention it fixes the point 1).

By the definition of induced characters and Theorem 3.1, we have

ρ_{n}(id) = (n − 2)! [S_{n} : S_{n−1}] − (n − 1)! = (n − 2)! = ω_{n}^{2}(id).

If g ≠ id and g has at least two fixed points, then ℓie_{n−1}(g) = ℓie_{n}(g) = 0, so ρ_{n}(g) = ω_{n}^{2}(g) by Lemma 4.2.

If g ≠ id has exactly one fixed point, then ℓie_{n}(g) = 0. For h ∈ S_{n} we have g^{h} := h^{−1}gh ∈ S_{n−1} if and only if h ∈ S_{n−1}. By the definition of induced characters and Lemma 4.2,

ρ_{n}(g) = ℓie_{n−1} ↑_{S_{n−1}}^{S_{n}} (g) = \frac{1}{(n − 1)!} ∑_{h∈S_{n−1}} ℓie_{n−1}(g^{h}) = ℓie_{n−1}(g) = ω_{n}(g).

If g ∈ S_{n} has no fixed points then ℓie_{n−1} ↑_{S_{n−1}}^{S_{n}} (g) = 0 and ρ_{n}(g) = −ℓie_{n}(g). As before, let g^{∗} be the element of S_{n+1} which fixes n + 1 and acts as g does on [n]. We have shown above that ω_{n+1}^{2}(g^{∗}) = ℓie_{n}(g). Hence, by Lemma 4.6, ρ_{n}(G) = ω_{n}^{2}(g).

According to Vassiliev, the number of linearly independent knot invariants of biorder (n, n − 1), modulo lower bi-order invariants, is bounded from above by the multiplicity of the trivial representation in the restriction of ω_{n}^{2} to the cyclic group C_{n} generated by (12 ⋯ n). See [V3] for all details. As a corollary of Theorem 4.1 we obtain a formula for this multiplicity. We write ⟨ξ, 1⟩ for the multiplicity of the trivial character in any character ξ of C_{n}.

Corollary 4.7.

⟨ω_{n}^{2} ↓_{C_{n}}^{S_{n}}, 1⟩ = (n − 2)! − \frac{1}{n} ∑_{d|n} μ(d)ϕ(d)(\frac{n}{d} − 1)! d^{\frac{n}{d} −1}

Proof: As a consequence of a result by Hanlon [H1] (see also [St2]), it is straightforward to show that

⟨ℓie_{n} ↓_{C_{n}}^{S_{n}}, 1⟩ = \frac{1}{n} ∑_{d|n} μ(d)ϕ(d)(\frac{n}{d} − 1)!d^{\frac{n}{d} −1},

where μ is the usual number-theoretic Möbius function and ϕ is Euler’s function. On the other hand,

⟨ℓie_{n−1} ↑_{S_{n−1}}^{S_{n}}↓_{C_{n}}^{S_{n}}, 1⟩ = \frac{1}{n} ∑_{g∈C_{n}} ℓie_{n−1} ↑_{S_{n−1}}^{S_{n}} (g) = \frac{1}{n} ℓie_{n−1} ↑_{S_{n−1}}^{S_{n}} (id) = (n − 2)!.

Now the assertion follows immediately from Theorem 4.1.

The values of w_{n} = ⟨ω_{n}^{2} ↓_{C_{n}}^{S_{n}}, 1⟩ for small n are given in the table below.

\begin{matrix}n & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ w_{n} & 1 & 1 & 2 & 6 & 18 & 96 & 564 & 4, 072 & 32, 990 \end{matrix}

Table 1: Multiplicity w_{n} of the trivial character in ω_{n}^{2} ↓_{C_{n}}^{S_{n}}

The character ω_{n}^{2} and the tensor product of ω_{n}^{2} with the sign character have recently appeared in various different settings, see Section 9.4.

5. The lattice of block-closed graphs

In this section we will obtain information on the topology of Δ_{n,k}^{2} by producing a lattice Σ_{n,k} such that Δ(\overline{Σ_{n,k}}) is homotopy equivalent to Δ_{n,k}^{2} and examining the structure of Σ_{n,k}. For lattice and poset terminology not explained in Section 10 we refer to [St3].

We begin by recalling some elements of the well known structure theory of separable graphs, which appears e.g. in [L]. Definition: Let G be any graph. A block of G is a subset W of V (G) such that the subgraph of G induced on W is 2-connected or W is a singleton or a pair of points connected by an edge, and the subgraph of G induced on any proper superset of W is separable. We will say that G is block-closed if the subgraph induced on each block is a clique.

Given a graph G, say that e ≡ e′ for two of its edges e and e′ if they both lie in some circuit of G. This is easily seen to be an equivalence relation on E(G). If W is the set of nodes underlying an equivalence class then W is a block, and all non-singleton blocks correspond to equivalence classes of edges in this way. From this it is easy to derive the following basic facts about the “block decomposition” of G, see [L] for more details.

Proposition 5.1. Let G be a graph. Then there exists a unique decomposition of V (G) into blocks W_{1}, …, W_{r}, and if i ≠ j we have |W_{i} ∩ W_{j}| ≤ 1. Moreover, if B_{G} is the graph with vertex set {w_{1}, …, w_{r}} such that {w_{i}, w_{j}} ∈ E(B_{G}) if and only if |W_{i} ∩ W_{j}| = 1, then B_{G} is a forest (that is, B_{G} contains no cycles).

Note that if K is a k-graph with underlying graph G, then every block of G has size at least k or is a single vertex. Definition: Let K be a k-graph with underlying graph G, and let W_{1}, …, W_{r} be the blocks of G. We define K^{∗} to be the k-graph which induces the complete k-graph on each W_{i} and contains no other hyperedges. We also define Σ_{n,k} to be the poset of all graphs on vertex set [n] in which every block is either an isolated vertex or a clique of size at least k, ordered by inclusion.

The first part of the following lemma is immediate from the definition, and the second follows via a standard argument for closure operators on lattices.

Lemma 5.2. (i) The map K ↦ K^{∗} defines a closure operator on Lat(Δ_{n,k}^{2}) whose

image is isomorphic to Σ_{n,k}. (ii) Σ_{n,k} is a lattice.

The meet operation in the lattice Σ_{n,k} is intersection of edge-sets followed by deletion of the edges in all blocks of size smaller than k. Note that the elements of Σ_{n,2} are the block-closed graphs, and that we have a tower of embeddings as subposets (not sublattices):

Σ_{n,k} ⊆ ⋯ ⊆ Σ_{n,3} ⊆ Σ_{n,2}.

Hence, in view of the following result the topology of all the complexes Δ_{n,k}^{2} is encoded into the lattice Σ_{n,2} of block-closed graphs.

Theorem 5.3. The complexes Δ_{n,k}^{2} and Δ(\overline{Σ_{n,k}}) are homotopy equivalent.

Proof: K^{∗} is the complete graph (the top element of Σ_{n,k}) if and only if K is 2-connected. Hence, the map K ↦ K^{∗} restricts to a closure operator on \overline{Lat(Δ_{n,k}^{2})} whose image is isomorphic to \overline{Σ}_{n,k}. The theorem then follows from Corollary 10.2.

We will now investigate the structure of Σ_{n,k}. The next two lemmas follow immediately from the definition of Σ_{n,k}. We write ˆ0 for the empty graph, which is the minimum element of Σ_{n,k}, and ˆ1 for the complete graph, which is its maximum.

Lemma 5.4. Let G, H ∈ Σ_{n,k}. Then G covers H if and only if one of the following conditions holds:

(i) E(G) \ E(H) is a clique on k vertices belonging to k pairwise different components of H.

(ii) E(G) \ E(H) is a complete bipartite graph on parts A and B, and there is a

vertex v such that A ∪ {v} and B ∪ {v} are blocks in H. (iii) Only if k > 2: E(G) \ E(H) is a star (that is, a connected graph with at most

one vertex of degree more than one), and the vertices of degree one in this star form a block in H belonging to a component of H distinct from that of the center of the star.

The three types of coverings can informally be described as follows:

(i) select a vertex from each of k pairwise disjoint components of H and then create a k-clique on these vertices;

(ii) complete the union of two overlapping blocks of H to a clique; (iii) for k > 2: select a block and a vertex from different components of H and

complete their union to a clique. The lattices Σ_{n,k} are neither upper nor lower semimodular. However, they ex-

hibit a recursive structure on lower intervals, and certain upper intervals are upper semimodular, as the following lemma shows.

Lemma 5.5. Let G ∈ Σ_{n,k}.

(i) If G has r non-singleton blocks of sizes m_{1}, …, m_{r} then the interval [ˆ0, G] is isomorphic to the direct product Σ_{m_{1},k} × ⋯ × Σ_{m_{r},k}

(ii) If G is connected then the interval [G, ˆ1] is isomorphic to a direct product of partition lattices. More precisely, suppose that G has s cutpoints and that the i-th cutpoint lies in t_{i} ≥ 2 blocks. Then, [G, ˆ1] ≅ Π_{t_{1}} × ⋯ × Π_{t_{s}}.

The following description of the coatoms of Σ_{n,k}, that is, the elements which are covered by ˆ1, follows immediately from the two preceding lemmas.

Lemma 5.6. Let M be a coatom of Σ_{n,k}. Then one of the following conditions holds:

(i) M is connected and has two blocks of size l, m with k ≤ l ≤ m ≤ n − k + 1 and l + m = n + 1. In this case, the interval [ˆ0, M] is isomorphic to Σ_{l,k} × Σ_{m,k}.

(ii) M consists of an (n − 1)-clique and an isolated vertex. In this case, k > 2 and the interval [ˆ0, M] is isomorphic to Σ_{n−1,k}.

For any graph G let c(G) be the number of connected components, and b(G) the number of blocks of size ≥ 2.

Theorem 5.7. (i) The lattice Σ_{n,2} is graded with rank function

ρ(G) = 2n − 2c(G) − b(G).

In particular, its length is ρ(ˆ1) = 2n − 3. (ii) The lattice Σ_{n,3} is graded with rank function

ρ(G) = n − c(G) − b(G).

In particular, its length is ρ(ˆ1) = n − 2. (iii) If k > 3 and n < 2k − 1, then Σ_{n,k} is isomorphic to the lower-truncated Boolean

algebra {A ⊆ [n] : |A| ≥ k}∪{∅}. In particular, Σ_{n,k} is graded of length n−k+1. (iv) If k > 3 and n ≥ 2k − 1, then ℓ is the length of a maximal chain of Σ_{n,k} if and

only if

ℓ = (n − 2) − t(k − 3), for some 1 ≤ t ≤ ⌊\frac{n − 1}{k − 1}⌋.

In particular, Σ_{n,k} is of length n − k + 1 and is not graded.

(v) If k > 3 then G ∈ \overline{Σ_{n,k}} is contained in a chain of length n − k + 1 if and only if G consists of a clique of size l ≥ k and n − l isolated vertices.

Proof: For claims (i) and (ii) it suffices to check that the given rank functions increase by 1 for each type of covering given in Lemma 5.4 and take value zero at the empty graph. Claim (iii) is clear from the definition.

Claims (iv) and (v) are implied by the following description of the maximal chains in Σ_{n,k}. We will here view Σ_{n,k} as a subposet of Σ_{n,3}, and we let ρ denote the restriction of the rank function of claim (ii) from Σ_{n,3} to Σ_{n,k}.

A maximal chain from ˆ0 to ˆ1 in Σ_{n,k} is a sequence of covering steps. By Lemma 5.4 there are three possibilities for each step. The rank function ρ will increase by 1 for coverings of types (ii) or (iii), and by k − 2 for coverings of type (i). Hence, the length of a maximal chain must be n − 2 − t(k − 3), where t is the number of covering steps of type (i). Note that t ≥ 1 since the first covering in the chain must be of type (i), and that t ≤ ⌊\frac{n−1}{k−1}⌋ since each step of type (i) reduces the number of connected components by k − 1 and the total reduction of components along the whole chain is n − 1.

Now, suppose that 1 ≤ t ≤ ⌊\frac{n−1}{k−1}⌋. A maximal chain of length n − 2 − t(k − 3) is constructed as follows. First perform a sequence of t covering steps of type (i) producing the graph with k-cliques on the sets {1, …, k}, {k, …, 2k − 1}, … {(t − 1)k − (t − 2), …, tk − (t − 1)}. Then continue from there via a sequence of t − 1 covering steps of type (ii) leading to the graph with a (tk − (t − 1))-clique on the set [tk − (t − 1)]. Finally, n − (tk − (t − 1)) covering steps of type (iii) will lead to the complete graph. The total number of steps taken, i.e. the length of the constructed chain, is t + (t − 1) + n − (tk − (t − 1)) = n − 2 − t(k − 3).

The above result yields some nontrivial information about the topology of Δ_{n,k}^{2}. For instance, part (i) shows that the order complex of \overline{Σ_{n,2}} is pure of dimension 2n − 5.

With Theorem 5.3 this implies that the homology of Δ_{n,2}^{2} vanishes in dimensions greater than 2n − 5 and is free in dimension 2n − 5. Of course, in this case we already have more precise knowledge from Theorem 3.1. By similar reasoning we can conclude the following new information about the k = 3 case from part (ii) of Theorem 5.7.

Theorem 5.8. H̃_{i}(Δ_{n,3}^{2}) = 0 for all i > n − 4, and H̃_{n−4}(Δ_{n,3}^{2}) is free.

In the remaining cases the following can be deduced.

Theorem 5.9. Assume that k > 3.

(i) H̃_{i}(Δ_{n,k}^{2}) = 0 if i > n − k − 1 or n − k − 1 > i > n − 2k + 2. (ii) H̃_{n−k−1}(Δ_{n,k}^{2}) is free of dimension \binom{n−1}{k−1}. (iii) If n < 2k − 1 then Δ_{n,k}^{2} has the homotopy type of a wedge of \binom{n−1}{k−1} spheres of

dimension n − k − 1. (iv) If n = 2k −1 then Δ_{n,k}^{2} has the homotopy type of a wedge of spheres. This wedge

consists of \binom{n−1}{k−1} (n − k − 1)-spheres and \frac{1}{2}n\binom{n−1}{k−1} 1-spheres.

Proof: We use Theorem 5.3 without reference throughout the proof. Claim (i) follows immediately from Theorem 5.7(iii),(iv),(v). By Theorem 5.7(v), the subposet of Σ_{n,k} generated by chains of length n − k + 1 is isomorphic to the poset obtained by removing all sets of sizes 1, 2, …, k − 1 from the Boolean algebra B_{n}. Claims (ii) and (iii) now follow immediately from the rank selection results in [B, St2], along with Theorem 5.7(iii),(iv).

If n = 2k−1, let W be the set of vertices in Δ(\overline{Σ_{n,k}}) corresponding to graphs which consist of two k-cliques intersecting in a single vertex, and let Δ_{0} be the complex obtained by removing all simplices containing an element of W from Δ(\overline{Σ_{n,k}}). Then Δ_{0} is the order complex of the subposet of \overline{Σ_{n,k}} generated by chains of length n−k+1, and is therefore homotopy equivalent to a wedge of \binom{n−1}{k−1} (n − k − 1)-spheres, as above. If G ∈ Σ_{n,k} corresponds to an element w ∈ W, then by Lemma 5.4, (\overline{Σ_{n,k}})_{<G} consists of two graphs which contain a k-clique and n − k isolated vertices. It follows that link_{Δ(\overline{Σ_{n,k}})}(w) consists of two vertices in Δ_{0}. There is a homotopy equivalence between Δ_{0} and a wedge of \binom{n−1}{k−1} (n−k −1)-spheres which maps ∪_{w∈W} link_{Δ(\overline{Σ_{n,k}})}(w) to the wedge point. It is easy to see that |W | = \frac{1}{2}n\binom{n−1}{k−1}, and claim (iv) follows.

The homology of Δ_{n,3}^{2} has been computed for 4 ≤ n ≤ 7. It is concentrated in dimension n − 4, see Table 2.

\begin{matrix}n\i & 0 & 1 & 2 & 3 \\ 2 & 0 & 0 & 0 & 0 \\ 3 & 0 & 0 & 0 & 0 \\ 4 & ℤ^{3} & 0 & 0 & 0 \\ 5 & 0 & ℤ^{21} & 0 & 0 \\ 6 & 0 & 0 & ℤ^{180} & 0 \\ 7 & 0 & 0 & 0 & ℤ^{2010} \end{matrix}

Table 2: Homology groups H̃_{i}(Δ_{n,3}^{2})

We believe that the concentration of homology in dimension n−4 is true in general, see the discussion in Section 9.2. One approach to proving this could be via the following lemma. Recall that a graph is called a forest if it is free of circuits. This is equivalent to saying that every block in its block decomposition has at most two vertices.

Lemma 5.10. Suppose that the order complex of the open interval (G, ˆ1) in Σ_{n,2} is topologically (n − 5)-connected for every forest G. Then Δ_{n,3}^{2} is homotopy equivalent to a wedge of (n − 4)-spheres.

Proof: By Theorem 5.3 we may replace Δ_{n,3}^{2} by Δ(\overline{Σ_{n,3}}), which by Theorem 5.7(ii) is (n − 4)-dimensional. Hence by known reductions (see [B, (9.19)]) it suffices to prove that Δ(\overline{Σ_{n,3}}) is (n − 5)-connected. By Theorem 3.1 we know that \overline{Σ_{n,2}} is (n − 5)- connected, and we will show how to transfer this connectivity to the subposet \overline{Σ_{n,3}} under the given hypothesis.

Let P_{n} be the subposet of \overline{Σ_{n,2}} consisting of all elements which contain at least one block of size greater than two. The elements in \overline{Σ_{n,2}} \ P_{n} are the forests G, so a version of Quillen’s fiber lemma (see [B, Lemma 11.12]) together with our hypothesis about the intervals (G, ˆ1) shows that P_{n} is (n − 5)-connected.

Now, note that \overline{Σ_{n,3}} ⊆ P_{n}. Let ρ : P_{n} → \overline{Σ_{n,3}} be the map which sends H ∈ P_{n} to the subgraph obtained by removing from H all edges which are not contained in a block of size at least three. Then ρ is a lower closure operator on P_{n} (that is, a closure operator on P_{n} with the opposite order) whose image is \overline{Σ_{n,3}}. Hence, by Corollary 10.2 \overline{Σ_{n,3}} is (n − 5)-connected also.

We end this section with an easy result which shows that the homology of Δ_{n,k}^{2} vanishes in all sufficiently low dimensions. For this the posets Σ_{n,k} are not used.

Lemma 5.11. Let E be a k-graph on n vertices. If E is 2-connected, then E contains at least ⌈\frac{n}{k−1}⌉ hyperedges.

Proof: If E is 2-connected then for each k-edge X = {v_{1}, …, v_{k}} ∈ E there exist at least two v_{i} which are contained in some k-edge of E other than X. It follows easily that

n ≤ |E|(k − 1).

Corollary 5.12. The complex Δ_{n,k}^{2} is topologically (⌈\frac{n}{k−1}⌉ − 3)-connected, implying that H̃_{i}(Δ_{n,k}^{2}) = 0 for i = 0, 1, …, ⌈\frac{n}{k−1}⌉ − 3.

Proof: Let m = ⌈\frac{n}{k−1}⌉ − 2. By Lemma 5.11 Δ_{n,k}^{2} contains the full m-skeleton on its vertex set. The corollary follows immediately.

6. The Euler characteristic of the complex Δ_{n,k}^{2}

In Section 5 we were able to determine the homotopy type of Δ_{n,k}^{2} for k > 3 when n ≤ 2k − 1, but not for k = 3, nor for k > 3 and n > 2k − 1. Indeed, other than the connectivity result given in Corollary 5.12, in the case k = 3 our only information on the topology of Δ_{n,k}^{2} is given by Theorem 5.8 (unless n is very small), and in the case k > 3 and n > 2k − 1 we were only able to determine the homology group H̃_{n−k−1}(Δ_{n,k}^{2}).

In this section, we investigate the reduced Euler characteristic of Δ_{n,k}^{2}. We will determine a formula for the exponential generating function

M_{k}(x) := ∑_{n=1}^{∞} χ̃(Δ_{n,k}^{2})\frac{x^{n}}{n!} ,

for all k ≥ 2. That formula is stated in the following theorem.

Theorem 6.1. For k ≥ 2, we have

M′_{k} (x\frac{p_{k−1}(x)}{p_{k}(x)}) = ln (\frac{p_{k−1}(x)}{p_{k}(x)}) ,

where p_{k}(x) := 1 + x + \frac{x^{2}}{2!} + ⋯ + \frac{x^{k−1}}{(k−1)!}.

Theorem 6.1 gives another proof that χ̃(Δ_{n,2}^{2}) = −(n − 2)!. It also implies

M′_{3}(x) = ln (\frac{−x(x − 2)}{(x − 1) + \sqrt{2 − (x − 1)^{2}}} ) ,

which gives the sequence 0, 0, −1, 3, −21, 180, −2010, 27090, −430290, … for χ̃(Δ_{n,3}^{2}), cf. Table 2. To obtain these corollaries set y := x\frac{p_{k−1}(x)}{p_{k}(x)} and solve for x to get x = \frac{1}{1−y}

and x = ^{\frac{y−1+\sqrt{2−(y−1)^{2}}}{2−y}} , when k = 2 and 3 respectively.

To prove Theorem 6.1 we will use the posets Σ_{n,k} defined in Section 5. Note that χ̃(Δ_{n,k}^{2}) = μ_{Σ_{n,k}}(ˆ0, ˆ1). We will write μ_{k}(G) for μ_{Σ_{n,k}}(ˆ0, G) and μ_{k}(n) for μ_{Σ_{n,k}}(ˆ0, ˆ1).

Let Π_{n,k} be the k-equal lattice, which is the lattice of partitions of [n] into subsets such that each subset has size one or at least k. Let τ_{k}(n) := μ_{Π_{n,k}}(ˆ0, ˆ1) for n ≥ k and τ_{k}(2) = ⋯ = τ_{k}(k − 1) = 0, but τ_{k}(1) = 1. The exponential generating function, T_{k}(x) := ∑_{n=1}^{∞} τ_{k}(n)\frac{x^{n}}{n!} , for the Möbius function of Π_{n,k} is known to be

T_{k}(x) = ln(p_{k}(x)),

where p_{k}(x) is as above. It was first calculated in [BL].

Let C be the set of connected graphs in Σ_{n,k}. Now let

σ : Σ_{n,k} \ C ⟶ Π_{n,k}

be the function which maps a disconnected graph in Σ_{n,k} to the partition determined by its connected components. It is easily seen that for each x ∈ Π_{n,k}, σ_{≤}^{−1}(x) has a unique maximum element and therefore has a contractible order complex. Thus by Proposition 10.1 and the definition of the Möbius function, we have

τ_{k}(n) = − ∑_{G∈Σ_{n,k}\C} μ_{k}(G) = ∑_{G∈C} μ_{k}(G).

Thus it suffices to concentrate on the connected but not 2-connected graphs. First we need a simple lemma.

Lemma 6.2. If G ∈ C has blocks W_{1}, …, W_{r} with |W_{i}| = w_{i}, then

μ_{k}(G) = ∏_{i=1}^{r} μ_{k}(w_{i}).

Proof: By Lemma 5.5 the interval [ˆ0, G] is isomorphic to the product poset Σ_{w_{1},k} × … × Σ_{w_{r},k}. The lemma now follows from the well known multiplicativity of the Möbius function.

Now define α_{k}(n) := ∑_{G∈C_{1}} μ_{k}(G), where C_{1} := {G ∈ C : n is not a cutpoint of G}.

Also, set α_{k}(1) = ⋯ = α_{k}(k − 1) = 0 and A_{k}(x) := ∑_{n=1}^{∞} α_{k}(n)\frac{x^{n}}{n!} .

Lemma 6.3. We have

A′_{k}(x) = ln (\frac{p_{k−1}(x)}{p_{k}(x)}) .

Proof: If n is a cutpoint of G ∈ C, let P_{1}, …, P_{t} be the connected components of G − n. Then for each i ∈ [t], n is not a cutpoint of the connected subgraph of G induced on P_{i} ∪ {n}. Using Lemma 6.2, we get the recursive formula

τ_{k}(n) = α_{k}(n) + \begin{matrix}⌊ & \frac{n−1}{k−1} & ⌋ \\ ∑ \\ t=2 \end{matrix} ∑_{P_{1}|...|P_{t}∈Π_{n−1}} α_{k}(|P_{1}| + 1) ⋯ α_{k}(|P_{t}| + 1),

where each summand in the double sum on the right counts the Möbius functions of all elements G ∈ C such that G − n has connected components P_{1}, …, P_{t}. By the definition of α_{k}(n) we can rewrite this formula as

τ_{k}(n) = ∑_{P_{1}|...|P_{t}∈Π_{n−1}} α_{k}(|P_{1}| + 1) ⋯ α_{k}(|P_{t}| + 1).

The exponential formula (Proposition 10.5) and easy power series manipulations then give

T′_{k}(x) = e^{A′_{k}(x)}.

Proof of Theorem 6.1: We will establish a recurrence relation for α_{k} involving μ_{k}. Let G ∈ C_{1} and let W be the block of G containing n. Then W is the unique maximal clique in G which contains n. Let S = W \{n}. Let B_{G} be the graph on the blocks of G defined in Proposition 5.1. Let T_{1}, …, T_{t} be the connected components of B_{G} −W and for each T_{i} let V_{i} be the set of vertices of G which are contained in a block that is contained in T_{i}. For each T_{i} there is a unique j_{i} ∈ S such that the subgraph of G induced on V_{i} ∪ {j_{i}} is a connected union of blocks of G. Conversely, any G ∈ C_{1} can be obtained by choosing S, T_{i} and j_{i} as above and then choosing graphs H_{i} on T_{i} ∪ {j_{i}} such that each H_{i} is either a clique of size at least k or isomorphic to a connected element of \overline{Σ}_{|T_{i}|+1,k}. These choices can all be made independently, so we get the recurrence relation

α_{k}(n) = ∑_{S⊎T =[n−1]} μ_{k}(|S| + 1) ∑_{T_{1}⊎...⊎T_{t}=T}(α_{k}(|T_{1}| + 1)|S|) ⋯ (α_{k}(|T_{t}| + 1)|S|).

We cannot apply the exponential formula directly at this point due to the factors |S| which appear on the right hand side of the above equation. However, we get

A′_{k}(x) = ∑_{n=1}^{∞} \frac{α_{k}(n)x^{n−1}}{(n − 1)!}

= ∑_{n=1}^{∞} ∑_{i=1}^{n−1} \binom{n − 1}{i}\frac{μ_{k}(i + 1)x^{i}}{(n − 1)!} ∑_{T_{1}|...|T_{t}∈Π_{n−i−1}}(α_{k}(|T_{1}| + 1)i) ⋯ (α_{k}(|T_{t}| + 1)i)x^{n−i−1}

= ∑_{i=1}^{∞} \frac{μ_{k}(i + 1)x^{i}}{i!} ∑_{n=i+1}^{∞} ∑_{T_{1}|...|T_{t}∈Π_{n−i−1}}(α_{k}(|T_{1}| + 1)i) ⋯ (α_{k}(|T_{t}| + 1)i)\frac{x^{n−i−1}}{(n − i − 1)!}

Applying the exponential formula, for each i we get

∑_{n=i+1}^{∞} ∑_{T_{1}|...|T_{t}∈Π_{n−i−1}}(α_{k}(|T_{1}| + 1)i) ⋯ (α_{k}(|T_{t}| + 1)i)\frac{x^{n−i−1}}{(n − i − 1)!} = e^{iA′_{k}(x)}.

Thus

A′_{k}(x) = ∑_{i=1}^{∞} \frac{μ_{k}(i + 1)x^{i}}{i!} e^{iA′_{k}(x)} = M′_{k} (xe^{A′_{k}(x)}) .

The theorem now follows from Lemma 6.3.

7. (n − 2)-connected graphs and matching complexes

Before we proceed to consider (n−2)-connected graphs, let us state some simple but useful facts about the general situation. What do maximal (i − 1)-separable graphs on the n element set [n] look like? Is is clear that each such graph is described by an (i − 1)-set A and a partition B ⊎ C of [n] \ A into two non-empty blocks B, C. The corresponding maximal (i − 1)-separable graph is the complete graph on [n] with all edges connecting B and C removed.

Now let G be an (n − 2)-connected graph on n vertices, so G ∉ Δ_{n}^{n−2}. Then by the above description of maximal (n − 3)-separable graphs the induced subgraph on any three vertices must contain at least two edges. Thus the complementary graph (i.e., the graph containing precisely the edges that are not in G) is a matching. The graphs on n vertices that are matchings form a simplicial complex, that we denote by M_{n}. We conclude the following. Proposition 7.1. The matching complex M_{n} is Alexander dual (in the sense of Proposition 10.4) to the complex Δ_{n}^{n−2}. In particular, there is an isomorphism

H̃_{i}(M_{n}) ≅ H̃^{\binom{n}{2}−i−3}(Δ_{n}^{n−2}).

The matching complexes M_{n} have attracted attention for various reasons. In [BLVZ, Theorem 4.1] the matching complex M_{n} is shown to be topologically (⌊\frac{n+1}{3}⌋− 2)-connected, which implies that H̃_{i}(M_{n}) = 0, for i = 0, …, ⌊\frac{n+1}{3}⌋ − 2. We thus get the following corollary. Corollary 7.2. The cohomology of Δ_{n}^{n−2} vanishes in dimensions i ≥ \binom{n}{2}−⌊\frac{n+1}{3}⌋−1.

The following table shows what we know about the homology groups H̃_{i}(M_{n}), based on the results of [BLVZ] for n ≤ 6 and n = 8, and our own computations.

n\i 0  1  2  3  4 5
2 0  0  0  0  0 0
3 ℤ^{2}  0  0  0  0 0
4 ℤ^{2}  0  0  0  0 0
5 0  ℤ^{6}  0  0  0 0
6 0  ℤ^{16}  0  0  0 0
7 0 torsion^{1}  ℤ^{20}  0  0 0
8 0  0  ℤ^{132}  0  0 0
9 0  0  ℤ^{42} ⊕ torsion^{2}  ℤ^{70}  0 0
10 0  0  torsion^{3}  ℤ^{1216}  0 0
11 0  0  0  ℤ^{1188} ⊕ torsion^{4} ℤ^{252} 0
12 0  0  0  torsion^{5}  ℤ^{12440} 0

Table 3: Homology groups H̃_{i}(M_{n}) of matching complexes

We see that the complexes Δ_{n}^{n−2} can have torsion, and that this phenomenon begins with Δ_{7}^{5}.

8. The Euler characteristic of the complex Δ_{n}^{n−3}

Consider the complex (Δ_{n}^{n−3})^{∗} which is the Alexander dual of Δ_{n}^{n−3}, and the exponential generating function of its reduced Euler characteristic

F_{n}^{n−3}(x) := ∑_{n≥0} χ̃((Δ_{n}^{n−3})^{∗})\frac{x^{n}}{n!} .

1There is ℤ_{3}-torsion of rank 1. No ℤ_{p}-torsion for p = 2, 5 ≤ p ≤ 17.

2There is ℤ_{3}-torsion of rank 8. No ℤ_{p}-torsion for p = 2, 5 ≤ p ≤ 17.

3There is ℤ_{3}-torsion of rank 1. No ℤ_{p}-torsion for p = 2, 5, 7.

4There is ℤ_{3}-torsion of rank 35. No ℤ_{p}-torsion for p = 2, 5, 7.

5There is ℤ_{3}-torsion of rank 56. No ℤ_{p}-torsion for p = 2, 5, 7.

The values of χ̃((Δ_{n}^{n−3})^{∗}) in the degenerate cases n ≤ 3 will appear from an explicitly calculated expansion below. We will express the reduced Euler characteristic of Δ_{n}^{n−3} in terms of an expression for this series.

Theorem 8.1. We have that:

F_{n}^{n−3}(x) = x − \frac{exp(\frac{x}{2(1+x)}) + x − \frac{1}{4}x^{2} − \frac{1}{8}x^{4}}{\sqrt{1 + x}} .

The exponential generating function of the reduced Euler characteristic of Δ_{n}^{n−3} is then the sum of the real and imaginary parts of −F_{n}^{n−3}(ix).

Proof: We will argue as we did for Δ_{n}^{n−2} in Section 7. If a graph G is (n − 3)- connected then the induced subgraph on any 4 of its vertices contains either a vertex of degree 3 or a path of length 3. Thus in the complementary graph the induced subgraph on any 4 vertices is either contained in a 3-cycle or in a path of length 3. In particular, there are no 4-cycles and no vertices of degree 3 in the complementary graph. Thus the connected components of the complementary graph are paths of any length and cycles of length different from 4. Moreover, any graph in which every connected component is a cycle not of length 4 or a path is the complement of an (n − 3)-connected graph, so (Δ_{n}^{n−3})^{∗} consists of all such graphs. There are exactly n!/2 different paths of length n and (n − 1)! different n-cycles on an n-element vertex set. Now a direct application of the Exponential Formula 10.5 gives the result for the generating function of (Δ_{n}^{n−3})^{∗}. The remaining assertion follows from the fact that when passing from Δ_{n}^{i} to its Alexander dual the Euler characteristic changes by a factor of −(−1)^{n(n−1)/2}.

The complex (Δ_{n}^{n−3})^{∗} has maximal simplexes of dimensions n − 1 and n − 2 only. It is easily collapsible to a pure complex of dimension n − 2. A Maple computation (see below) shows that neither the Euler characteristic of (Δ_{n}^{n−3})^{∗} nor the Euler characteristic of Δ_{n}^{n−3} alternate in sign, so the pure complexes are certainly not all Cohen-Macaulay. The calculation shows that

F_{n}^{n−3}(x) = −1 − x + \frac{1}{4}x^{4} + \frac{1}{20}x^{5} + \frac{1}{20}x^{6} − \frac{1}{27}x^{7} − \frac{1}{224}x^{8} − \frac{1}{480}x^{9} + O(x^{10}).

We have also studied the slightly larger complex of graphs which are the disjoint union of cycles and paths of any lengths (i.e., graphs with maximum vertex degree at most 2). This is also a reasonable generalization of the matching complex, which is the complex of all graphs with maximum vertex degree at most 1. The Euler characteristic of the corresponding Alexander dual has almost the same generating function as for (Δ_{n}^{n−3})^{∗}. That generating function is

x − \frac{exp(\frac{x}{2(1+x)}) + x − \frac{1}{4}x^{2}}{\sqrt{1 + x}} =

−1 − x + \frac{1}{8}x^{4} − \frac{3}{40}x^{5} + \frac{1}{20}x^{6} − \frac{1}{28}x^{7} − \frac{17}{896}x^{8} − \frac{7}{1920}x^{9} − \frac{23}{2400}x^{10} + O(x^{11}).

The maximal simplices in the cycles-and-paths complex have dimension n − 1 or n − 2, and the complex can be collapsed to a pure (n − 2)-dimensional complex. The generating function for the Euler characteristic shows that these collapsed complexes are not all Cohen-Macaulay.

9. Final Remarks

9.1. Homology and Topology of Δ_{n}^{i}. The results and computations presented in this paper suggest that there is probably no uniform statement that covers the topology of all complexes Δ_{n}^{i}. However, for i ≤ 2 the homotopy type calculations for Δ_{n}^{i} give very nice answers. This is consistent with the graph theoretical study of not i-connected graphs, where there is a good structure theory only when i ≤ 3 (see for example Chapter 6 of Lovász’ book [L], or the survey article by Oxley [O] and the references therein).

As mentioned, there is a structure theory for 3-connected graphs. The 3-connected graphs on n vertices for which neither the deletion nor the contraction of an edge leads to a 3-connected graph were classified by Tutte (see Theorem 2.3 in [O]) as “wheels” and “whirls,” both having 2n − 2 edges. Note that this does not provide a characterization of the deletion-minimally 3-connected graphs (the minimal non-faces of Δ_{n}^{3}), however it does show that no graph with less than 2n − 2 edges can be 3connected. Hence, Δ_{n}^{3} has a complete 2n − 4-skeleton, which shows that H̃_{i}(Δ_{n}^{3}) = 0 for i < 2n − 4. This fact together with the following table leads to an interesting conjecture.

\begin{matrix}n\i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 0 & 0 & 0 & 0 & ℤ^{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 5 & 0 & 0 & 0 & 0 & 0 & 0 & ℤ^{6} & 0 & 0 & 0 & 0 \\ 6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & ℤ^{36} & 0 & 0 \\ 7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & ℤ^{240} \end{matrix}

Table 4: Homology groups H̃_{i}(Δ_{n}^{3})

Conjecture 9.1: Δ_{n}^{3} has the homotopy type of a wedge of \frac{(n−3)(n−2)!}{2} spheres of dimension 2n − 4.

For general i the situation (concerning Δ_{n}^{i}) seems to be far more complicated. However, we would like to remark that for i = 2, 3 the known Betti numbers are (up to sign) the Lah-numbers L_{n−2,1} and L_{n−2,2} (see [Co, p.165-166]). This coincidence unfortunately fails for i = 4, which is easily seen by comparing L_{n−2,3} with χ̃(Δ_{n}^{4}) for n = 6. For i > 3 no good structure theory for i-connected graphs is known, and the results of Section 7 on (n − 2)-connected graphs indicate that the topology of Δ_{n}^{i} will not behave nicely for all i. Nevertheless, the Alexander Duality with the matching complexes M_{n} encourages a closer look at the complexes Δ_{n}^{n−2}. Surprisingly, the prime 3 seems to play a special role in the topology of these complexes. We have not detected p-torsion in the homology of Δ_{n}^{n−2} for any prime p ≠ 3.

Question 9.2: Does the homology of M_{n} have p-torsion for any prime p ≠ 3?

Even more surprising is the fact that the same prime 3 seems to play an analogous role for the matching complexes M_{n,n} on complete bipartite graphs K_{n,n}, also called chessboard complexes (see [BLVZ]).

n\i 0 1 2  3  4  5 6
1 0 0 0  0  0  0 0
2 ℤ 0 0  0  0  0 0
3 0 ℤ^{4} 0  0  0  0 0
4 0 0 ℤ^{15}  0  0  0 0
5 0 0 ℤ_{3}  ℤ^{56}  0  0 0
6 0 0 0 ℤ^{25} ⊕ torsion^{1}  ℤ^{210}  0 0
7 0 0 0  0  ℤ^{588} ⊕ torsion^{2} ℤ^{792} 0
8 0 0 0  0  torsion^{3}  ? ?

Table 5: Homology groups H̃_{i}(M_{n,n}) for the bipartite matching complexes

It is easy to see that M_{n,n} collapses to an (n − 2)-dimensional complex. Hence homology is free in dimension n − 2 and vanishes in higher dimensions. Looking at the table and the footnotes the following question naturally occurs.

Question 9.3: Is the homology of M_{n,n} free except for 3-torsion ?

9.2. Homology and Topology of Δ_{n,k}^{2}. For k-graph complexes the problem of determining the topology of the complex of separable k-graphs (the i = 2 case) seems to be the most important. The complexes Δ_{n,k}^{2} play the same role in the study of spaces of “knots” for which k-fold self-intersections are forbidden as the complexes Δ_{n}^{2} play for ordinary knots.

Question 9.4: What is the homology and homotopy type of Δ_{n,k}^{2} ?

The evidence from Section 5 leads us to anticipate the following answer for k = 3.

Conjecture 9.5: Δ_{n,3}^{2} is homotopy equivalent to a wedge of (n − 4)-spheres.

A natural approach to this question is through further combinatorial study of the lattices Σ_{n,k} defined in Section 5.

Conjecture 9.6: The lattice Σ_{n,k} is shellable.

This is open in all cases, except for the somewhat degenerate cases n < 2k−1 when Σ_{n,k} is a truncated Boolean algebra. If Conjecture 9.6 were verified for k = 2 it would reprove Theorem 3.1, and it would via Lemma 5.10 imply the truth of Conjecture 9.5. If Conjecture 9.6 were verified for k = 3 it would also imply the truth of Conjecture 9.5. If Conjecture 9.6 were verified for k > 3 it would via Theorem 5.7(iv) and the results of [BW] imply the truth of the following.

1There is ℤ_{3}-torsion of rank 10. No ℤ_{p}-torsion for p = 2, 5, 7

2There is ℤ_{3}-torsion of rank 66. No ℤ_{p}-torsion for p = 2, 5, 7

3There is ℤ_{3}-torsion of rank 1. This group is finite according to [FH].

Conjecture 9.7: If k > 3 and n ≥ 2k − 1, then Δ_{n,k}^{2} is homotopy equivalent to a wedge of spheres. Furthermore, the dimensions of the spheres are precisely n − 4 − t(k − 3) for 1 ≤ t ≤ ⌊\frac{n−1}{k−1}⌋.

9.3. Generating series of Euler characteristics. Let F_{i}(x) = ∑_{n≥0} χ̃(Δ_{n}^{i})\frac{x^{n}}{n!} and

G_{i}(x) = ∑_{n≥0} χ̃((Δ_{n}^{n−i})^{∗})\frac{x^{n}}{n!} . By the results presented in this paper we get the following

table:

i  F_{i}(x)  G_{i}(x)
1  ln(1 + x)  −1
2 (1 − x)log(1 − x) + 1 + x  −exp(x − \frac{x^{2}}{2} )
3  x − \frac{exp( \frac{x}{2(1+x)} )+x− \frac{1}{4} x^{2}− \frac{1}{8} x^{4}}{\sqrt{1+x}}

Table 6: Generating functions of the Euler characteristics of Δ_{n}^{i} and (Δ_{n}^{n−i})^{∗}

We cannot formulate a conjecture about the entries in this table for i > 3. Nevertheless, even though the actual homology computation may be too difficult, the generating series may be computable for a few more cases. Assuming a positive answer to Conjecture 9.1, we get

F_{3}(x) = (x − \frac{3}{2})log(1 − x) + 1 − \frac{3}{2}x + \frac{1}{4}x^{2}.

9.4. The representation of the symmetric group. All complexes Δ_{n,k}^{i} are invariant under the action of the symmetric group S_{n}. This action determines a linear representation of S_{n} on each homology group H̃_{j}(Δ_{n,k}^{i}). For fixed n, k and i, the alternating sum of the characters of the given representations is a virtual character of S_{n} that we denote by ω_{n,k}^{i}. For k = 2 and i = 1, 2 this is an actual character (up to sign) and satisfies

(−1)^{n+1}ω_{n+1,k}^{2} = (sign_{n}ω_{n,k}^{1}) ↑_{S_{n}}^{S_{n+1}} +sign_{n+1}ω_{n+1,k}^{1}.

From looking at the dimensions of the homology modules it is clear that the analogous formula for k ≥ 3 does not hold. We have also seen that homology of Δ_{n,k}^{i} is not torsion-free in general. On the other hand, [RR] has demonstrated that for the closely related matching complexes it is possible to determine the representations on the rational homology. Thus it is reasonable to ask:

Question 9.8: What is the character of S_{n} on each non-vanishing rational homology group of Δ_{n,k}^{i} ?

The character ω_{n}^{2} = ω_{n,2}^{2} determined in Section 4 has recently appeared in several different areas of mathematics. First in the work of C. A. Robinson & S. Whitehouse [RW] and S. Whitehouse [Wh] on gamma-homology of algebras and later in work of E. Getzler & M. Kapranov [GK] on operads, O. Mathieu [Ma] on hyperplane arrangements and symplectic geometry, in the work of M. Kontsevich [K] on Lie algebras and symplectic geometry, and in the work of P. Hanlon [H2], P. Hanlon & R.P. Stanley [HS] and S. Sundaram [Su] in a combinatorial and representationtheoretic context. It seems mysterious that the same character pops up in so many seemingly unrelated places.

Question 9.9: What are the deeper connections between the various contexts where the character ω_{n}^{2} appears ?

The analogous question for the character ω_{n,2}^{1} = sign_{n} · ℓie_{n} has been studied quite extensively (see for example [Ba, BaBe, Re]), and for that case much detailed information is known. An important aspect of the work in [Ba] and [BaBe] is the construction of explicit bases for the modules under consideration. Thus a first step towards an answer to Question 9.9 could be a solution of the following problem.

Problem 9.10: Describe a combinatorial basis for the homology of Δ_{n}^{2}.

A positive answer to the shellability conjecture 9.6 for k = 2 could via the induced shelling basis (see [BW]) lead to progress on Problem 9.10.

10. Notation and Tools

In this short section we will summarize the main tools that we use in the study of the complexes Δ_{n,k}^{i}. We refer the reader to the survey paper [B] for more details and references.

Let P be a finite partially ordered set – poset for short. If P has a unique minimum element ˆ0 and a unique maximum element ˆ1, we denote by \overline{P} the proper part of P, that is the poset obtained by removing from P the elements ˆ0 and ˆ1. By Δ(P) we denote the simplicial complex of all chains in P. The complex Δ(P) is called the order complex of P.

By convention we include the empty set ∅ in every simplicial complex. For any simplicial complex Δ, the face lattice Lat(Δ) is the poset of faces of Δ, ordered by inclusion and enlarged by an additional greatest element ˆ1. Then the order complex Δ(\overline{Lat(Δ)}) of the proper part of Lat(Δ) is homeomorphic to Δ. Indeed, Δ(\overline{Lat(Δ)}) is the barycentric subdivision of Δ.

For a poset P and p ∈ P we denote by P_{≤p} the sub-poset {p′ | p′ ∈ P; p′ ≤ p }. The posets P_{≥p}, P_{<p} and P_{>p} are analogously defined. For p ≤ p′ in P we denote by [p, p′] the closed interval P_{≥p} ∩ P_{≤p′} in P, and by (p, p′) the open interval P_{>p} ∩ P_{<p′}.

For a poset P we denote by μ_{P} the ℤ-valued Möbius function (see [St3]), defined recursively on the intervals of P by μ_{P} (x, x) = 1 and μ_{P} (x, y) = − ∑_{x≤z<y} μ_{P} (x, z) if

x < y.

By a map f : P → Q of posets we always mean a poset homomorphism (i.e., x ≤ y implies f(x) ≤ f(y)). For an element q ∈ Q we denote by f_{≤}^{−1}(q) the preimage of Q_{≤q} under f. The poset f_{≥}^{−1}(q) is analogously defined.

Proposition 10.1 (Quillen Fiber Lemma [Q]). Let f : P → Q be a map of posets. If Δ(f_{≤}^{−1}(q)) is contractible for all q ∈ Q then Δ(P) and Δ(Q) are homotopy equivalent.

A map f : P → P from a poset to itself is called a closure operator if f(x) ≥ x and f(f(x)) = f(x) for all x ∈ P. The Quillen Fiber Lemma immediately implies the fact that closure operators preserve the homotopy type.

Corollary 10.2 (Closure Lemma). Let f : P → P be a closure operator on the partially ordered set P. Then Δ(P) and Δ(f(P)) are homotopy equivalent.

If the poset P is a lattice (i.e., suprema, denoted by “∨”, and infima, denoted by “∧”, exist) then there is another tool for computing the homotopy type. Note that if P is a finite lattice then there is a least element ˆ0 and a largest element ˆ1 in P. For an arbitrary element p ∈ P we say that a ∈ P is a complement of p if p ∧ a = ˆ0 and p ∨ a = ˆ1.

Proposition 10.3 (Homotopy Complementation Formula [BWa] ).

(i) Let P be a poset and A ⊆ P an antichain. Assume Δ(P \ A) is contractible. Then Δ(P) is homotopy equivalent to

⋁_{x∈A} Σ(Δ(P_{<x}) ∗ Δ(P_{>x})).

(ii) Let P be the proper part of a lattice and let Co be the set of complements of some element p ≠ ˆ0, ˆ1. Then Δ(P \ Co) is contractible.

In the formulation of the proposition ⋁ denotes the wedge product, Σ denotes the suspension and ∗ denotes the join of topological spaces.

Our next tool is the combinatorial version of a standard duality theorem from algebraic topology.

Proposition 10.4 (Combinatorial Alexander Duality). Let Δ be a finite simplicial complex on vertex set V and define

Δ^{∗} = {B ⊆ V | V \ B ∉ Δ}.

Then

H̃_{i}(Δ) ≅ H̃^{|V |−i−3}(Δ^{∗}).

This is derived as follows. The usual Alexander duality theorem (see e.g. Munkres [Mu]) says that

H̃_{i}(A) ≅ H̃^{n−i−1}(S^{n} \ A)

for any compact subset A of the n-sphere S^{n}. In our situation, let P = 2^{V} \ {∅, V }. This truncated Boolean algebra is the proper part of the face lattice of the boundary complex of a simplex, so Δ(P) ≅ S^{|V |−2}. Now let A be the realization of Δ(\overline{Lat(Δ)}) as a subspace of Δ(P). It is easy to see that Δ(P \ \overline{Lat(Δ)}) is a strong deformation retract of S^{|V |−2} \ A, and since P \ \overline{Lat(Δ)} ≅ \overline{Lat(Δ^{∗})} the result follows.

Finally, we recall a result from enumerative combinatorics. For a number sequence

(a_{n})_{n≥0} the formal power series ∑_{n≥0} a_{n} \frac{x^{n}}{n!} is called its exponential generating function.

Proposition 10.5 (Exponential formula). Suppose that two functions a, b : ℕ ⟶ ℤ are given such that

b(n) = ∑_{S_{1}|···|S_{t}∈Π_{n}} a(|S_{1}|) ⋯ a(|S_{t}|), n ≥ 1,

where the sum ranges over all set partitions of [n] and a(0) = 0, b(0) = 1. Then the exponential generating functions A(x) := ∑_{n=0}^{∞} \frac{a(n)x^{n}}{n!} and B(x) := ∑_{n=0}^{∞} \frac{b(n)x^{n}}{n!} satisfy

B(x) = e^{A(x)}.

For the proof see [St1, St4].

References

[Ba] H. Barcelo. On the action of the symmetric group on the free Lie algebra and the partition lattice. J. Comb. Theory, Ser. A 55(1):93–129, 1990.

[BaBe] H. Barcelo and N. Bergeron. The Orlik-Solomon algebra on the partition lattice and the free Lie algebra. J. Comb. Theory, Ser. A 55(1):80–92, 1990.

[B] A. Björner. Topological methods. In: R. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics, pages 1819–1872. North-Holland, Amsterdam, 1995.

[BL] A. Björner and L. Lovász. Linear decision trees, subspace arrangements and Möbius functions. Journal of American Mathematical Society 7(3):677–706, 1994.

[BLVZ] A. Björner, L. Lovász, S. T. Vrećica, and R. T. Živaljević. Chessboard complexes and matching complexes. J. London Math. Soc. (2), 49(2):25–39, 1994.

[BW] A. Björner and M. L. Wachs. Shellable nonpure complexes and posets, I. Trans. Amer. Math. Soc., 348(4):1299–1327, 1996.

[BWa] A. Björner and J. W. Walker. A homotopy complementation formula for partially ordered sets. European J. Combin., 4(1):11–19, 1983.

[BWe] A. Björner and V. Welker. Homology of the “k-equal” manifolds and related partition lattices. Advances in Math., 110(2):277–306, 1995.

[Ch] M. K. Chari. On discrete Morse functions and combinatorial decompositions. Preprint, 1996.

[Co] L. Comtet. Analyse Combinatoire, Vol. I. Presses Universitaires de France, Paris, 1970. [English translation: Advanced Combinatorics, Reidel, Dordrecht, 1974.]

[F] R. Forman. Morse theory for cell complexes. Advances in Math., to appear.

[FH] J. Friedman and P. Hanlon. On the Betti numbers of chessboard complexes. Preprint, 1996.

[GK] E. Getzler and M. M. Kapranov. Cyclic operads and cyclic homology. In: Geometry, topology and physics, pp 167-201. International Press, Cambridge, MA, 1995.

[H1] P. Hanlon. The fixed-point partition lattices. Pacific J. Math., 96(2):319–341, 1981.

[H2] P. Hanlon. Otter’s method and the homology of homeomorphically irreducible k-trees. J. Combin. Theory Ser. A, 74(2):301–320, 1996.

[HS] P. Hanlon and R. P. Stanley. A q-deformation of a trivial symmetric group action. Trans. Amer. Math. Soc., to appear.

[K] M. Kontsevich. Formal (non)-commutative symplectic geometry. In: L. Corwin et al. (eds.) The Gelfand Mathematical Seminar, 1990–1992, pp. 173-187. Birkhäuser, Boston, 1993.

[KSS] J. Kahn, M. Saks and D. Sturtevant. A topological approach to evasiveness. Combinatorica, 4(4):279-306, 1984.

[L] L. Lovász. Combinatorial Problems and Exercises, 2nd edition. North-Holland, Amsterdam, 1993.

[Ma] O. Mathieu. Hidden S_{n+1}-actions. Comm. Math. Phys., 176(2):467–474, 1996.

[Mu] J. R. Munkres. Elements of Algebraic Topology. Addison-Wesley, Menlo Park, CA, 1984.

[O] J. Oxley. Structure theory and connectivity for matroids. in: J.E. Bonin et al (eds.) Matroid Theory, volume 197 of Contemp. Math., pp. 129–170. Amer. Math. Soc., Providence, RI, 1996.

[Q] D. Quillen. Homotopy properties of the poset of nontrivial p-subgroups of a group. Advances in Math., 28(2):101–128, 1978.

[RR] V. Reiner and J. Roberts. Resolutions and the homology of matching and chessboard complexes. In preparation.

[Re] C. Reutenauer. Free Lie Algebras. Oxford University Press. Oxford, 1993.

[Ro] C. A. Robinson. The space of fully grown trees. Technical report, Universität Bielefeld, 1992.

[RW] C. A. Robinson and S. Whitehouse. The tree representation of Σ_{n+1}. J. Pure Appl. Algebra, 111(1-3):245–253, 1996.

[Si] R. Simion. Personal communication, September 1996.

[St1] R. P. Stanley. Exponential structures. Stud. Appl. Math., 59(1):72-83, 1978.

[St2] R. P. Stanley. Some aspects of groups acting on finite posets. J. Combin. Theory Ser. A, 32(2):132–161, 1982.

[St3] R. P. Stanley. Enumerative Combinatorics, Vol 1. Wadsworth and Brooks/Cole. Monterey, CA, 1986.

[St4] R. P. Stanley. Enumerative Combinatorics, Vol 2. Book manuscript.

[Su] S. Sundaram. Homotopy of non-modular partitions and the Whitehouse module. Preprint, 1996.

[SW] S. Sundaram and M. Wachs. The homology representations of the k-equal partition lattice. Trans. Amer. Math. Soc., 349(3):935-945, 1997.

[V1] V. A. Vassiliev. Complexes of connected graphs. In: L. Corwin et al. (eds.), The Gelfand Mathematical Seminar, 1990-1992, pp. 223–235. Birkhäuser, Boston, 1993.

[V2] V. A. Vassiliev. Complements of Discriminants of Smooth Maps : Topology and Applications, revised edition, volume 98 of Transl. of Math. Monographs. Amer. Math. Soc., Providence, RI, 1994.

[V3] V. A. Vassiliev. Indices of complicated singular knots, homology of two-connected graphs, and calculation of finite order knot invariants. Preprint, 1997.

[We] V. Welker. Equivariant homotopy of posets and some applications to subgroup lattices. J. Combin. Theory Ser. A, 69(1):61–86, 1995.

[Wh] S. Whitehouse. The Eulerian representations of Σ_{n} as restrictions of representations of Σ_{n+1}. J. Pure Appl. Algebra, 115(3):309–321, 1996.

Eric Babson, Mathematical Sciences Research Institute, 1000 Centennial Drive, Berkeley, CA 94720-5070, USA.

  E-mail address: babson@msri.org

Anders Björner, Department of Mathematics, Royal Institute of Technology, S-100 44 Stockholm, Sweden

  E-mail address: bjorner@math.kth.se

Svante Linusson, Department of Mathematics, Stockholms Universitet, S-106 91 Stockholm, Sweden

  E-mail address: linusson@matematik.su.se

John Shareshian, Mathematical Sciences Research Institute, 1000 Centennial Drive, Berkeley, CA 94720-5070, USA.

  E-mail address: shareshi@msri.org

Volkmar Welker, Fachbereich 6, Mathematik, Universität GH-Essen, D-45117 Essen, Germany

  E-mail address: welker@exp-math.uni-essen.de