COUNTING THE INTERIOR POINTS OF A POINT CONFIGURATION

PAUL H. EDELMAN AND VICTOR REINER

Abstract. We prove a formula conjectured by Ahrens, Gordon, and McMahon for the number of interior points for a point configuration in ℝ^{d}. Our method is to show that the formula can be interpreted as a sum of Euler characteristics of certain complexes associated with the point configuration, and then compute the homology of these complexes. This method extends to other examples of convex geometries. We sketch these applications, replicating an earlier result of Gordon, and proving a new result related to ordered sets.

1. Introduction

Let A be a collection of points in ℝ^{d} whose affine span is all of ℝ^{d}. Let int(A) be the set of points of A that lie in the interior of its convex hull, conv(A). Call a subset K of A free if conv(K) ∩ A = K and the set of vertices of conv(K) is equal to K. In a recent paper Ahrens, Gordon and McMahon [1, Conjecture 4.1] conjectured the following beautiful formula for |int(A)|, and proved it for point configurations A in ℝ^{2}:

Theorem 1.1.

|int(A)| = (−1)^{(d−1)} ∑_{Kfree}(−1)^{|K|}|K|.

We prove this formula in its full generality in Section 3. D. Klain [14, Proposition 6.3] has recently proven this formula independently.

The work of Ahrens, et. al. is part of a larger project of extending matroid invariants to greedoids [11, 12]. Recent work has focused on generalizing Crapo’s β invariant, originally defined for matroids [6], to the more general structure of a greedoid [10]. In the special case of greedoids which are convex geometries, the definition of the β invariant reduces to essentially the right-hand side of Theorem 1.1 [10]. Theorem 1.1 gives a combinatorial interpretation to the β invariant of those convex geometries which are based on Euclidean point configurations. Given this background, it is not surprising that Ahrens, et. al. use deletion-contraction arguments to establish their formula for d = 2.

Our point of view is more in the tradition of a topological approach to matroid theory [4], as we now explain. One can rewrite the right-hand side in Theorem 1.1 as follows:

(−1)^{(d−1)} ∑_{Kfree}(−1)^{|K|}|K| = (−1)^{(d−1)} ∑_{Kfree} ∑_{a∈K}(−1)^{|K|}

= (−1)^{(d−1)} ∑_{a∈A} χ̃_{a}

The second author was partially supported by a Sloan Foundation Fellowship and a University of Minnesota McKnight-Land Grant Fellowship.

where

χ̃_{a} = ∑_{K free, a∈K}(−1)^{|K|}.

We will prove Theorem 1.1 by showing (see Lemmata 3.4,3.5) that

χ̃_{a} = \begin{cases}(−1)^{d−1} & if a ∈ int(A) \\ 0 & otherwise. \end{cases}

The latter computation is achieved by interpreting χ̃_{a} as the reduced Euler characteristic of a certain simplicial complex (the link of a in the simplicial complex of free sets of A), and then analyzing the topology of these complexes. In contrast, Klain [14] computes these Euler characteristics directly using valuation theory for polytopes.

The paper is organized as follows. In the next section we establish some general facts from combinatorial topology and polytope theory necessary for the proof. In Section 3 we prove Theorem 1.1. Section 4 uses similar techniques to evaluate the generalized β invariant for other convex geometries. Section 5 discusses some open problems.

2. Preliminaries

In this section we establish some background results from topological combinatorics that will be used throughout the paper. For much of this material an excellent reference is [3].

Let Δ be an abstract simplicial complex on the finite ground set X. That is, Δ is a collection of subsets of X, called simplices, with the property that

σ ⊆ τ ∈ Δ

implies that σ ∈ Δ. For −1 ≤ i ≤ |X| − 1 let f_{i} be the number of i-dimensional faces of Δ, i.e.,

f_{i} = |{σ ∈ Δ : |σ| = i + 1}|.

For any x ∈ X, we define three associated subcomplexes, the link of x in Δ, the star of x in Δ, and the deletion of x in Δ by

lk_{Δ}(x) = {σ − x | x ∈ σ ∈ Δ }
st_{Δ}(x) = {σ ∈ Δ | {x} ∪ σ ∈ Δ }
del_{Δ}(x) = {σ ∈ Δ | x ∉ σ }.

It is clear from the definitions that

(1) st_{Δ}(x) ∪ del_{Δ}(x) = Δ

and

(2) del_{Δ}(x) ∩ st_{Δ}(x) = lk_{Δ}(x).

For a given simplicial complex Δ, let H̃_{i}(Δ) = H̃_{i}(Δ, ℤ) be the reduced homology groups of Δ with coefficients in ℤ, for i ≥ 0. By the universal coefficient theorem [15, Section 55], H̃_{·}(Δ) determines the homology of Δ with any other constant coefficients. The reduced Euler characteristic χ̃(Δ) is defined by

χ̃(Δ) = ∑_{i≥−1}(−1)^{i} f_{i} = ∑_{i≥0}(−1)^{i} dim_{ℚ} H̃_{i}(Δ, ℚ).

where we note that f_{−1} = 1.

The following lemma will be necessary in what follows

Lemma 2.1. Let Δ be a contractible simplicial complex on the ground set X and x ∈ X. For all i ≥ 0

H̃_{i}(lk_{Δ}(x)) ≅ H̃_{i}(del_{Δ}(x)).

Consequently

χ̃(lk_{Δ}(x)) = χ̃(del_{Δ}(x))

= ∑_{x∈σ∈Δ}(−1)^{|σ|}.

Proof. Associated to (1) and (2) is a Mayer-Vietoris exact sequence [15, Theorem 25.1]

⋯ → H̃_{i+1}(Δ) → H̃_{i}(lk_{Δ}(x)) → H̃_{i}(del_{Δ}(x)) ⊕ H̃_{i}(st_{Δ}(x)) → H̃_{i}(Δ) → ⋯

Note that both Δ and st_{Δ}(x) are contractible, the former by hypothesis and the latter since st_{Δ}(x) is a cone. Therefore the above sequence reduces to

⋯ → 0 → H̃_{i}(lk_{Δ}(x)) → H̃_{i}(del_{Δ}(x)) → 0 → ⋯

which proves the first assertion. The next equation follows immediately and the last equation is immediate from the definition of the reduced Euler characteristic.

Let P be a poset. We can associate with P its simplicial complex of chains Δ(P), i.e., the collection of totally ordered subsets of P. When we speak of P having a certain topological property, we are really referring to the topology of the geometric realization of Δ(P). If P has both a maximum element ˆ1 and a minimum element ˆ0, then its proper part is \overline{P} = P − \{ˆ0, ˆ1\}. If x ∈ P then let P_{≤x} = \{y ∈ P | y ≤ x \}. The following lemmata are essentially due to Quillen [16]. See also [3, 10.5, 10.12].

Lemma 2.2. Suppose Q and P are posets and f : Q → P is an order-preserving map. If for all x ∈ P the fibers f^{−1}(P_{≤x}) are contractible then f induces a homotopy equivalence between Q and P.

Lemma 2.3. Let f : P → P be an order-preserving map such that f(x) ≥ x for all x ∈ P. Then f induces a homotopy equivalence between P and f(P).

Remark 2.4. In our applications of Lemma 2.2, we will often let Q be a simplicial complex Δ viewed as a partially ordered set, where the partial order on the simplices is by containment. The conclusions drawn will technically be about the order complex of this poset, which is the barycentric subdivision sd(Δ) of Δ. However, it is well-known [15, Section 15] that sd(Δ) is homeomorphic to Δ, so the same conclusions can be drawn about Δ.

The last general facts that we will employ concern Gale transforms of point configurations. Let A = {a_{1}, …, a_{n}} ⊆ ℝ^{d} be a collection of points whose affine span is all of ℝ^{d} and let conv(A) denote the polytope which is the convex hull of A. List a_{1}, …, a_{n} as columns of a matrix and append a row of ones to obtain the (d + 1) × n matrix M_{A}. The null space of M_{A} is the set of all affine dependencies among the points in A, i.e., vectors (λ_{1}, …, λ_{n}) such that ∑_{i=1}^{n} λ_{i} a_{i} = 0 and ∑_{i=1}^{n} λ_{i} = 0. Let A^{∗} be an (n − d − 1) × n matrix whose rows form a basis for this space and denote its columns by v_{1}^{∗}, …, v_{n}^{∗}. This collection A^{∗} of points in ℝ^{n−d−1} is a Gale transform of A. The correspondence between v_{i} and v_{i}^{∗} extends naturally to subsets of A and A^{∗}. For any subset B ⊆ A, denote by aff(B) the affine span of B. The principal property of Gale transforms is

Lemma 2.5. [13, Section 5.5] Let F be a proper subset of A. Then

aff(F) ∩ conv(A − F) = ∅

if and only if

0 ∈ relint(conv(A − F)^{∗}).

That is, F is exactly the set of points of A that lie on a face of conv(A) if and only if (A − F)^{∗} has 0 in its relative interior.

One should observe that any set of n points in ℝ^{n−d−1} that has 0 in its relative interior is the Gale transform of some set of n points in ℝ^{d}. For an interesting survey of the uses of Gale transforms, see [2].

Lemma 2.6. Let A be a point configuration in ℝ^{d}, P = conv(A), and A^{∗} its Gale transform. Let N be the poset of proper subsets A of A^{∗}, ordered by containment, such that

0 ∉ relint(conv(A)).

Then N has the same integral homology as the (n − d − 2)-sphere, and hence

χ̃(N) = (−1)^{n−d−2}.

Proof. Let 2^{A^{∗}} be the collection of all subsets of A^{∗}. Considering its proper part \overline{2^{A^{∗}}} as partially ordered by inclusion, its order complex is the barycentric subdivision of the boundary of an (n−1)-simplex, and hence is homeomorphic to an (n−2)-sphere. Lemma 2.5 implies that 2^{A^{∗}} − N is isomorphic as a poset to the opposite of the face lattice of P. Thus the order complex of \overline{2^{A^{∗}} − N} is the barycentric subdivision of the boundary complex of P, and hence is homeomorphic to a (d − 1)-sphere. It follows from [5, Lemma 4.7.27] that N is a deformation retract of the space \overline{2^{A^{∗}} − N}, which is to say the complement of a (d − 1)-sphere in an (n − 2)-sphere. It then follows from Alexander duality [15, Theorem 71.1] that N has the homology of an (n − d − 2)-sphere.

The poset N which appears in the previous proof is, roughly speaking, the poset of subsets of A which do not form boundary faces of conv(A). In [17] it was asked whether it has the homotopy type of a (n − d − 2)-sphere and not just the same homology groups. This question was answered in the affirmative by X. Dong [7].

3. Proof of Theorem 1.1

In this section we prove the conjecture of Ahrens, et. al.. Our discussion in this section will be only in terms of the geometric structure of point configurations in ℝ^{d}, although there are natural generalizations to the more abstract situation of convex geometries. We take up those more general questions in the next section.

Let A = {a_{1}, …, a_{n}} be a point configuration in ℝ^{d}. Given a subset A of A we define the closure of A, A^{c}, to be

A^{c} = conv(A) ∩ A.

It is clear that this is a true closure operator on the subsets of A, that is, it is idempotent, inclusion-preserving, and A ⊆ A^{c}. The closed sets under this operator will be called the convex sets of A. Let L = L(A) be the lattice of convex sets of A ordered by inclusion and \overline{L} its proper part, that is, \overline{L} = L − \{∅, A\}.

If C is a convex set of A, a point a ∈ C is called an extreme point of C if a is vertex of the polytope conv(C). Let ex(C) be the set of extreme points of C. A convex set C is said to be free if ex(C) = C. Let Free = Free(A) be the collection of free sets of A, and note that Free is a simplicial complex.

Lemma 3.1. Let A be a point configuration and L(A) be its lattice of convex sets. Then \overline{L} triangulates an

\begin{cases}(|A| − 2) − ball & if A ≠ ex(A) \\ (|A| − 2) − sphere & if A = ex(A) \end{cases}

Proof. This follows from [8, Theorem 4.10], but for the sake of completeness we sketch the proof here. In the case where A = ex(A), note that L is a Boolean algebra on the set A whose proper part has order complex equal to the barycentric subdivision of an (|A| − 1)-simplex, i.e., it triangulates an (|A| − 2) − sphere .

If A ≠ ex(A) the meet of the coatoms of L is the convex set A − ex(A) which lies in \overline{L}. It follows from [3, Crosscut Theorem (10.8)] that \overline{L} is contractible.

Lemma 3.2. Let A be a point configuration and Free its simplicial complex of free sets. Then Free is contractible.

Proof. If ex(A) = A, then Free is just a simplex and hence is contractible. Thus, we may assume that ex(A) ≠ A, so that the inclusion map ι is a map from Free to \overline{L}. We wish to apply Lemma 2.2 treating the simplicial complex Free as its poset of faces as discussed in Remark 2.4. We then need to analyze the structure of the fibers ι^{−1}(L_{≤C}) for each C ∈ \overline{L}. It is easy to check that ι^{−1}(L_{≤C}) = Free(C) (where here C is considered as a point configuration), and hence is contractible by induction on the number of points. Hence, by Lemma 2.2, Free has the same homotopy type as \overline{L}. By Lemma 3.1, \overline{L} is contractible if A ≠ ex(A), and so the lemma is proven.

Let

β(A) = ∑_{K∈Free}(−1)^{|K|}|K|.

Our definition of β(A) differs from that of Ahrens, et. al. by a minus sign [1, Definition 2.2]. For our purposes this is the more convenient convention.

Lemma 3.3. If A is a point configuration then

β(A) = ∑_{a∈A} χ̃(del_{Free}(a)).

Proof. As noted in Lemma 2.1

χ̃(del_{Free}(a)) = ∑_{a∈K∈Free}(−1)^{|K|}

since Free is contractible by Lemma 3.2. Thus

∑_{a∈A} χ̃(del_{Free}(a)) = ∑_{a∈A} ∑_{a∈K∈Free}(−1)^{|K|}

= ∑_{K∈Free}(−1)^{|K|}|K|

= β(A).

From Lemma 3.3, we see that it is sufficient to understand the topology of each deletion del_{Free}(a) in order to evaluate β(A). That is what we endeavor to do in the rest of this section. Let P = conv(A). We will assume that dim(P) = d and thus the interior of P is the same as its relative interior. Let bdy(P) denote the points of A lying in the boundary of conv(A), that is, bdy(P) := A − int(A).

Lemma 3.4. Let x ∈ A and suppose that x ∈ bdy(P). Then del_{Free}(x) is contractible. As a consequence χ̃(del_{Free}(x)) = 0.

Proof. If x is on the boundary of P then it is contained in the relative interior of a unique face F of P. Let F = F ∩ A. Define a new point configuration B by

B = F ∪ {t}

where t is a new point in ℝ^{d} that is affinely independent of the points in F. The map f from A to B defined by

f(a) = \begin{cases}a & if a ∈ F \\ t & otherwise. \end{cases}

induces a map f̂ from subsets of A to subsets of B by f̂(A) = {f(a) | a ∈ A}. It is easy to check that f̂ restricts to a map from del_{Free(A)}(x) to del_{Free(B)}(x). In order to apply Lemma 2.2 we will view both of these simplicial complexes as their posets of faces as discussed in Remark 2.4.

We now analyze the fibers of this restricted map f̂. For notational convenience, let

Γ = del_{Free(A)}(x)
Γ′ = del_{Free(B)}(x).

Suppose that K ∈ Γ′. We consider two cases in analyzing the fiber f̂^{−1}(Γ′_{≤K}). If t ∉ K, then

f̂^{−1}(Γ′_{≤K}) = {C ⊆ K | C ∈ Γ} ,

which has K as a maximum element, since K ∈ Γ′ and t ∉ K implies that K ∈ Γ. Hence this fiber is contractible.

If t ∈ K, then

f̂^{−1}(Γ′_{≤K}) = {C ∈ Γ | C ∩ F ⊆ K}
= Free((K − {t}) ∪ (A − F)),

(here (K − {t}) ∪ (A − F) is considered as a point configuration on its own). This fiber is then contractible by Lemma 3.2.

Thus the fibers f̂^{−1}(Γ′_{≤K}) are always contractible, and so by Lemma 2.2, we know that del_{Free(A)}(x) has the same homotopy type as del_{Free(B)}(x). Since the point t was affinely independent of all of the other points in B, we see that del_{Free(B)}(x) has t as a cone point, and hence is contractible. Thus del_{Free(A)}(x) is contractible and the lemma is proven.

We have left to consider the topology of del_{Free}(x) in the instance when x is in the interior of P.

Lemma 3.5. Let x ∈ A and suppose that x ∈ int(P). Then del_{Free}(x) has the integral homology of a (d − 1)-sphere. As a consequence, χ̃(del_{Free}(x) = (−1)^{d−1}.

Proof. Suppose that x ∈ int(P). Define the poset CN(x) by

CN(x) = {K ∈ L |x ∉ relint(conv(K)) } .

Note that del_{Free}(x) ⊆ CN(x) and so we can consider the inclusion map

ι : del_{Free}(x) → CN(x).

Again we will view del_{Free}(x) as its poset of faces in order to apply Lemma 2.2 as discussed in Remark 2.4.

Claim 3.6. The fibers ι^{−1}(CN(x)_{≤K}) are contractible for every K ∈ CN(x).

Proof of claim. There are two cases to consider. First, suppose that x ∉ K. Then we see that

ι^{−1}(CN(x)_{≤K}) = Free(K).

This follows since K ∈ L implies that any free subset of K is also a free subset of A, and x ∉ K implies that it is not in any subset of K. By Lemma 3.2, Free(K) is contractible and so we are done.

The second case is that x ∈ K. Then by the definition of CN(x), we have x ∈ bdy(conv(K)). From this we conclude that

ι^{−1}(CN(x)_{≤K}) = {C ∈ Free(K) | x ∉ C}
= del_{Free(K)}(x).

which is contractible by Lemma 3.4.

Continuing the proof of Lemma 3.5, since the fibers of ι are all contractible, Lemma 2.2 implies that del_{Free}(x) has the same homotopy type as CN(x). Consider another poset N(x) defined by

N(x) = {B ⊆ A | x ∉ relint(conv(B))} .

The difference between N(x) and CN(x) is that the subsets in N(x) need not be convex. The closure operator f(B) = B^{c} gives a map f from N(x) to itself, since

x ∉ relint(conv(B)) ⇒ x ∉ relint(conv(B^{c})).

The image of N(x) under the map f is exactly CN(x). Thus by Lemma 2.3 we have that N(x) has the same homotopy type as CN(x), and thus the same homotopy type as del_{Free}(x). It only remains to analyze the homology of N(x).

Translate the point configuration A so that x = 0. As observed at the end of last section, we can view A as the Gale transform of some point configuration A^{∗} in ℝ^{n−d−1}, since 0 is in the relative interior of A. Also note that our poset N(x) is now the same as the one denoted N in Lemma 2.6. Thus by Lemma 2.6 we conclude that N(x) has the same homology as a (d − 1)-sphere. Hence del_{Free}(x) has the homology of a (d − 1)-sphere, and the proof of Lemma 3.5 is complete.

Theorem 1.1 [see [1, Conjecture 4.1]] If A is a point configuration in ℝ^{d} then

β(A) = ∑_{K∈Free}(−1)^{|K|}|K| = (−1)^{d−1}|int(A)|,

i.e., (−1)^{d−1}β(A) equals the number of points in A which are in the interior of the convex hull of A.

Proof. The proof is immediate from Lemmata 3.3, 3.4 and 3.5

4. Convex geometries

In this section we discuss generalizations of Theorem 1.1 to more general convex geometries. Most of the framework discussed in Section 3 goes through for general convex geometries, but we lack at the moment completely general versions of Lemma 3.4 or Lemma 3.5. We can, however, prove analogues of these lemmata for other specific examples of convex geometries.

We begin with a brief description of the theory of convex geometries. For a more detailed introduction see [8], whose notation we follow. Let X be a finite set, and L a collection of subsets of X that contains ∅ and X and is closed under intersection. We can alternatively think of L as a closure operator on X defined by

L(A) = ⋂_{{C∈L | C⊇A}} C.

The subsets in L or, equivalently, those subsets A of X such that L(A) = A will be called convex sets. We will say that L is anti-exchange if given any convex set C, and two unequal points p and q in X, neither in C, one has that

q ∈ L(K ∪ {p}) ⇒ p ∉ L(C ∪ {q}).

A collection L of convex sets that is anti-exchange will be called a convex geometry. Let L(L) be the lattice of convex sets of L ordered by containment. Some examples of convex geometries are

Point configurations: The collection of convex subsets of a point set A in ℝ^{d}

(as described in the previous section) is a convex geometry, with X = A. Order convex sets: Let Q be a poset, and for any subset A ⊆ Q define

C_{Q}(A) = {q ∈ Q | ∃ a, a′ ∈ A, a ≤ q ≤ a′} .

The closure C_{Q} is anti-exchange, and we call the associated convex geometry with X = Q the order convex sets of Q, denoted C_{Q}.

Chordal graphs: Let G be a chordal graph on a vertex set V. That is, G is a graph such that every cycle of length longer than 4 has a chord. A subset C of V will be called m-convex if it contains every vertex on every chordless path between vertices in C. The collection L(G) of m-convex sets of a chordal graph is a convex geometry, with X = V [9].

If C is a convex set in a convex geometry L, a point x ∈ C is called an extreme point of C if x ∉ L(C − x). We denote the set of extreme points of C by ex(C). We will call a convex set free if ex(C) = C. The set of free sets of a convex geometry form a simplicial complex which we denote Free(L). The following lemmata are direct generalizations of Lemma 3.1 and Lemma 3.2.

Lemma 4.1. Let L be a convex geometry on a ground set X and L = L(L) be its lattice of convex sets. Then \overline{L} triangulates an

\begin{cases}(|X| − 2) − ball & if X ≠ ex(X) \\ (|X| − 2) − sphere & if X = ex(X) \end{cases}

Proof. See [8, Theorem 4.10].

Lemma 4.2. Let L be a convex geometry and Free its simplicial complex of free sets. Then Free is contractible.

Proof. The proof follows exactly the argument for Lemma 3.2.

As before we define

β(L) = ∑_{K∈Free(L)}(−1)^{|K|}|K|.

and note that because of Lemma 4.2, Lemma 3.3 still holds, i.e.,

β(L) = ∑_{x∈X} χ̃(del_{Free(L)}(x)). (3)

Although we do not have a uniform way of computing β(L) for all convex geometries, we can use the framework we have established to evaluate it for the examples of convex geometries we described above. We sketch those arguments here.

4.1. Order convex sets. Let Q be a poset and C_{Q} be the collection of order convex sets of Q. We call an element q ∈ Q a bottleneck if q is comparable to every element of Q, but q is neither a maximum nor a minimum element.

Lemma 4.3. Let Free = Free(C_{Q}) be the free sets of the convex geometry of order convex sets of Q. Then del_{Free}(q) has the homotopy type of the 0-sphere if q is a bottleneck, and is contractible otherwise.

Sketch of Proof. If q is a bottleneck define Q_{>q} ( resp. Q_{<q}) to be the points in Q strictly bigger than (resp. less than) q. It is easy to check that lk_{Free}(q) is the disjoint union of the two (non-empty) complexes Free(C_{Q_{>q}}) and Free(C_{Q_{<q}}), each of which is contractible by Lemma 3.2. Hence del_{Free}(q) has the homotopy type of the 0-sphere.

If q is not a bottleneck, then there are two possibilities. On the one hand, q might be a maximum or minimum element, in which case it is easy to see that del_{Free}(q) is the same as Free(C_{Q−{q}}), and hence is contractible by Lemma 3.2.

If q is not a bottleneck and is also neither a maximum nor a minimum element of Q, then there exist elements of Q which are bigger than q, smaller than q, and incomparable to q. Define a new four-element poset Q′ = {b, s, i, q′} (here b, s, i are mnemonic for “bigger”,“smaller”, “incomparable” to q) in which b ≥ q′ ≥ s and i is incomparable to any of the other three. One can easily check that del_{Free(C_{Q′})}(q′) is contractible since it is a cone with cone point i. The map f : Q → Q′ given by

f(x) = \begin{cases}b & if x > q \\ q′ & if x = q \\ s & if x < q \\ i & if x is incomparable to q. \end{cases}

induces a map from del_{Free(C_{Q})}(q) to del_{Free(C_{Q′})}(q′). One can check the relevant fibers f^{−1}(Q′_{≤y}) to see that they are all contractible, and thus del_{Free(C_{Q})}(q) has the homotopy type of del_{Free(C_{Q′})}(q′), and hence is contractible.

Corollary 4.4. Let Q be a poset and C_{Q} be the collection of order convex sets of Q. Then β(C_{Q}) is equal to the number of bottlenecks in Q.

Proof. From the previous lemma we see that

χ̃(del_{Free}(q)) = \begin{cases}1 & if q is a bottleneck \\ 0 & otherwise. \end{cases}

Apply this formula to (3).

4.2. Chordal graphs. Gordon has previously interpreted β(L(G)) for a chordal graph G in [10]. He did this by means of a deletion-contraction argument. Our topological approach gives a more detailed result.

Lemma 4.5. Let G be a connected chordal graph. A subset K of V is free in L(G) if and only if it induces a clique in G.

Proof. See [10, Lemma 5.1].

For each vertex v in G let c(v) be the number of connected components of G−v.

Lemma 4.6. Let G be a connected chordal graph and Free = Free(L(G)). For each vertex v in G, the complex del_{Free}(v) has the homotopy type of c(v) disjoint points.

Sketch of Proof. It is easy to show that del_{Free}(v) is just the disjoint union of Free(L(G′)) for each connected component G′ of G − v. By Lemma 4.2 these are all contractible so the lemma follows.

Recall that a block of a graph is a maximal subgraph which contains no cutvertex. We denote by b(G) the number of blocks in the graph G.

Corollary 4.7. [10, Theorem 5.1] Let G be a connected chordal graph. Then

β(L(G)) = b(G) − 1.

Proof. From the previous lemma we see that

χ̃(del_{Free}(v)) = c(v) − 1,

and so

β(L(G)) = ∑_{v∈G}(c(v) − 1).

It is then an elementary graph-theoretic fact [18, Problem 4.1.28] that

∑_{v∈G}(c(v) − 1) = b(G) − 1.

5. Open problems

In this section we discuss some open problems aimed toward generalizing Theorem 1.1 to all convex geometries. As a first step in this direction we formulate a conjecture that generalizes Lemma 3.4 for all convex geometries. Let L be a convex geometry on the ground set X. A subset A of X will be called independent if a ∉ L(A − a) for all a ∈ A. We will say that x depends on y if there exists an independent set A such that y ∈ A, x ∈ L(A) but x ∉ L(A − y). Let Dep(x) be the set of all points y such that x depends on y. The situation in which Dep(x) = X includes the following as special cases

• x ∈ int(A) for a point configuration,

• x is a bottleneck of a poset,

• x is a vertex for which c(v) = 1 in a chordal graph.

Conjecture 5.1 (cf. Lemmata 3.4, 4.3, and 4.6). For a convex geometry L on the ground set X, the complex del_{Free(L)}(x) is contractible unless Dep(x) = X.

The question of what happens if Dep(x) = X is much less clear, as the diversity of outcomes in Lemmata 3.5, 4.3, and 4.6 indicate. In this direction, we pose the following question.

Question 5.2. For any convex geometry L on the ground set X, and any point x with Dep(x) = X, does the complex del_{Free(L)}(x) have same integral homology as a bouquet of equidimensional spheres? Is it homotopy equivalent to a bouquet of equidimensional spheres?

References

[1] C. Ahrens, G. Gordon and E. McMahon,Convexity and the beta invariant, preprint, 1998.

[2] M. Bayer and C. Lee, Combinatorial aspects of convex polytopes, in Handbook on Convex Geometry (P. Gruber and J. Wills, eds.), North-Holland, Amsterdam, 1993, pp. 485–534.

[3] A. Björner, Topological methods, Handbook of Combinatorics (R. Graham, M. Grötschel, and L. Lovász, eds.), North Holland, Amsterdam, 1995, pp. 1819-1872.

[4] A. Björner, Homology and shellability of matroids and geometric lattices, in Matroid Applications (N. White, ed.), Encyclopedia of Mathematics and its Applications, Vol. 40, Cambridge Univ. Press, Cambridge, 1992, pp. 226-283.

[5] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler, Oriented Matroids, Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge University Press, Cambridge, 1993.

[6] H. Crapo, A higher invariant for matroids, J. Comb. Th.,2 (1967), 406–417.

[7] X. Dong, personal communication, 1999.

[8] P. H. Edelman and R. Jamison, The theory of convex geometries, Geom. Ded.,19 (1985), 247–270.

[9] M. Farber and R. Jamison, On local convexity in graphs, Discrete Math., 66 (1987), 231–247.

[10] G. Gordon, A β invariant for greedoids and antimatroids, Elect. J. Combin.,4 (1997), #R13.

[11] G. Gordon and E. McMahon, A greedoid polynomial which distinguishes rooted arborescences, Proc. Amer. Math. Soc. 107 (1989), 287–298.

[12] G. Gordon and E. McMahon, A greedoid characteristic polynomial, Contemp. Math. 197 (1996), 343-351.

[13] B. Grünbaum, Convex Polytopes, Interscience, London, 1967.

[14] D. Klain, An Euler relation for valuations on polytopes, preprint, 1999.

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

[16] D. Quillen, Homotopy properties of the poset of non-trivial p-subgroups of a group, Adv. in Math.,28 (1978), 101-128.

[17] V. Reiner, On some instances of the generalized Baues problem, preprint, 1998.

[18] D. B. West, Introduction to Graph Theory, Prentice-Hall, Upper Saddle River, 1996.

12 PAUL H. EDELMAN AND VICTOR REINER

School of Mathematics, University of Minnesota, Minneapolis, MN 55455 USA E-mail address, P. H. Edelman: edelman@math.umn.edu E-mail address, V. Reiner: reiner@math.umn.edu