CONVEX, ACYCLIC, AND FREE SETS OF AN ORIENTED MATROID

PAUL H. EDELMAN, VICTOR REINER, AND VOLKMAR WELKER

Abstract. We study the global and local topology of three objects associated to a simple oriented matroid: the lattice of convex sets, the simplicial complex of acyclic sets, and the simplicial complex of free sets. Special cases of these objects and their homotopy types have appeared in several places in the literature.

The global homotopy types of all three are shown to coincide, and are either spherical or contractible depending on whether the oriented matroid is totally cyclic.

Analysis of the homotopy type of links of vertices in the complex of free sets yields a generalization and more conceptual proof of a recent result counting the interior points of a point configuration.

1. Introduction

An oriented matroid M of rank r is a combinatorial abstraction of a finite collection of vectors spanning ℝ^{r} (a realizable oriented matroid), or a finite collection of points that affinely span affine (r − 1)-space (an acyclic, realizable oriented matroid) – see [4] for examples, as well as terminology and background on oriented matroids.

To any simple oriented matroid M, there are several natural and well-studied partial orders, cell complexes, simplicial complexes, and topological spaces one can associate. The purpose of this paper is to study three more such objects:

▷ the semilattice of convex sets L_{conv}(M),

▷ the simplicial complex of acyclic sets Δ_{acyclic}(M), ▷ the simplicial complex of free sets Δ_{free}(M).

Our first main result is: Theorem 1. L_{conv}(M) \ {∅}, Δ_{acyclic}(M) and Δ_{free}(M), are all homotopy equivalent. Furthermore they are homotopy equivalent to a

\{ \begin{matrix}sphere 𝕊^{r(M)−1} & if M is totally cyclic \\ point & otherwise, \end{matrix}

where r(M) is the rank of the oriented matroid M.

Several special cases of these objects and their homotopy types have arisen previously in the literature.

• In the special case of an affine point configuration, the semilattice L_{conv}(M) is the lattice of convex sets in the usual convex geometry (see [9] and Section 5 below) associated to the point configuration. In this case, the complex Δ_{free}(M) appeared in a conjecture of Ahrens, Gordon, and MacMahon [1] on a formula for the number of interior points in the point set. Their conjecture was proven in [10], using the topology of links of vertices in Δ_{free}(M) (and independently, in a purely enumerative fashion by Klain [16]).

Work of Reiner was partially supported by NSF grant DMS-9877047. Work of Edelman done while at University of Minnesota.

• In the case where the oriented matroid M is acyclic, but not necessarily realizable, M still carries the structure of a convex geometry that was first introduced by Las Vergnas [18], and L_{conv}(M) was studied further by Edelman [7] – see [4, p. 152, Exercises 3.9, 3.10].

• In the case where M is antiparallel-closed (see Section 3 below), the topology of Δ_{acyclic}(M) was studied by Edelman [8], and used to give a proof for the oriented matroid generalization [4, Theorem 4.6.1] of Zaslavsky’s formula for the number of chambers cut out by an arrangement of hyperplanes.

• A further special case arises in the work of Björner and Welker [3] on the topology of complexes of directed graphs. There the complex Δ_{acyclic}(M) appears as the complex of acyclic directed graphs, and L_{conv}(M) appears as the lattice of all posets. Both are shown to be homotopy equivalent to spheres, which we generalize in Theorem 15 below.

The contents of the paper are as follows. Section 2 gives definitions and reviews terminology in order to prove Theorem 1. We next investigate the homotopy type of local structures within the objects in question; that is, intervals and order filters within L_{conv}(M) and links of faces within Δ_{acyclic}(M) and Δ_{free}(M). Section 3 deals with local structures in L_{conv}(M) and Δ_{acyclic}(M). Here we find that, as in Theorem 1, the homotopy types are essentially identical (Proposition 11), albeit arbitrarily complicated (Proposition 14). However, in the special case where M is antiparallel closed, the homotopy type of these two local structures is either spherical or contractible (Theorem 15).

Section 4 deals with links in Δ_{free}(M), which turn out to be more subtle. After reviewing some of the theory of convex geometries [9], we closely examine the link of a vertex e in Δ_{free}(M), and relate it to the simplification of the oriented matroid contraction M/e. Recall that the simplification Simp(M) of an oriented matroid M is obtained from M by removing all loops and considering each parallelism class as a single element. Theorem 2. link_{Δ_{free}(M)}(e) is a collapse (and hence a strong deformation retract) of Δ_{free}(Simp(M/e)).

In Section 5, we apply Theorem 2 to prove a generalization (Theorem 23) of the conjecture of Ahrens, Gordon and MacMahon [1] mentioned above. We generalize their result from point configurations in real affine d-space (that is, realizable acyclic oriented matroids) to all oriented matroids. In the process, we greatly simplify the topological proof of their conjecture in [10], by avoiding an excursion into Gale transforms.

2. Global homotopy type and cyclicity

The goal of this section is to establish terminology, define the objects of study, and prove Theorem 1.

Recall that an oriented matroid M on ground set E may be specified by its collection of covectors, which are functions f : E → {+, 0, −}, satisfying the covector axioms [4, p.159]. Throughout we assume that M is simple, i.e. it contains no parallel elements (although antiparallel elements are allowed) and no loops. We will refer to a covector as being positive if all of its entries are +, non-negative if all of its entries are + or 0, and similarly for negative and non-positive. We will also refer to the positive support f^{−1}(+) of a covector f. We say M is acyclic or acyclically oriented if some covector f is positive, and say that M is totally cyclic or totally cyclically oriented if (0, …, 0) is the only non-negative covector. Note that these possibilities are mutually exclusive, but not exhaustive. For example, the oriented matroid realized by the vector configuration A = {(1, 0), (−1, 0), (0, 1)} in ℝ^{2} is neither acyclic nor totally cyclic.

Say that a subset A ⊆ E is acyclic if there exists some covector of M which takes only the value + on A (equivalently, the restriction M|_{A} is an acyclic oriented matroid). When A is acyclic, define the convex hull conv(A) to be the set of e in E having the property that every covector f which is identically + on A also has f(e) = +. Say that an acyclic set A is convex if conv(A) = A. The extreme points ex(A) of an acyclic set A are defined to be the points a in A such that a ∉ conv(A − {a}). It can be shown that conv(ex(A)) = conv(A) [18, 7]. A convex set A is free if ex(A) = conv(A)(= A). When we wish to emphasize the underlying oriented matroid M, we will annotate these operators with subscripts: ex_{M}(A), conv_{M}(A).

Define L_{conv}(M) to be the poset (actually a meet-semilattice) of convex subsets of E ordered by inclusion, and let Δ_{acyclic}(M) (resp. Δ_{free}(M)) denote the simplicial complexes of acyclic (resp. free) subsets of E. We write L_{conv}^{∘}(M) for L_{conv}(M) \ {∅}.

A  ^{a}^{d}  ^{d}^{c}^{b}  ^{abc}^{ab}^{a}  _{∅}^{bc}^{b}  ^{c}^{L_{conv}(M)}^{ad}  ^{cd}  ^{Δ_{acyclic}(M)}^{b} ^{d}^{a}  ^{c}  ^{Δ_{free}(M)}^{b}^{a}  ^{c}^{d}

Figure 1: Convex, free and acyclic sets for the oriented matroid M given by the point configuration A.

It is easy to see that every proper lower interval [ˆ0, x] in L_{conv}(M) is the poset of convex sets in a convex geometry, and hence is a meet-distributive lattice; that is, a lattice in which every coatomic interval is Boolean; see [9] and Section 4 below. This convex geometry was first considered by Las Vergnas [18],[4, p. 152, Exercise 3.9].

When M is not acyclic, it is easy to see that L_{conv}(M) will not have joins, and hence not be a lattice. Although one might think to adjoin a top element ˆ1 to make it a lattice, this lattice L_{conv}(M) ∪ {ˆ1} would not be meet-distributive, as it is not even ranked in general. Consider for example the case of the realizable oriented matroid M corresponding to the vector configuration A = {a = (1, −1), b = (1, 0), c = (1, 1), d = (−1, 0)} in ℝ^{2} (see Figure 1). This has maximal convex subsets {abc, ad, cd}, leading to maximal chains in L_{conv}(M) of lengths 3, 2, 2 respectively. For this reason, we refrain from adjoining a top element to L_{conv}(M).

In preparation for the proof of Theorem 1, we review some notation and facts from combinatorial topology – see [2] and [4, Appendix 4.7] for more background. When referring to the topology of a simplicial complex, we mean the topology of its geometric realization. When referring to the topology of a poset P we mean the topology of its order complex. The order complex of a poset is the simplicial complex whose simplices are the linearly ordered subsets of P. For an element p ∈ P we denote by P_{≤p} the poset {q ∈ P : q ≤ p }. Analogously defined are the posets P_{<p}, P_{≥p} and P_{>p}. When P is a lattice (resp. meet-semilattice) we denote by ˆ0 and ˆ1 (resp. ˆ0) its unique minimal and maximal (resp. unique minimal) element.

We will make frequent use of the following well-known tools. Lemma 3 (Quillen Fiber Lemma). [4, Lemma 4.7.29] If f : P → Q is an orderpreserving map of posets with f^{−1}(Q_{≤q}) contractible for all q in Q, then f induces a homotopy equivalence of P and Q. Dually, the same holds if f^{−1}(Q_{≥q}) is contractible for all q in Q. □ Lemma 4. Let {p_{i}}_{i=1}^{k} be a collection of elements of a poset P with the property that each subposet P_{<p_{i}} is contractible. Then the inclusion P −{p_{i}}_{i=1}^{k} ↪ P induces a homotopy equivalence.

Proof. Assume the p_{i} are indexed so that p_{i} < p_{j} implies i > j, and then apply the Quillen Fiber Lemma, Lemma 3, to each inclusion

P − {p_{i}}_{i=1}^{j} ↪ P − {p_{i}}_{i=1}^{j−1}.
□

Lemma 5. [2, Corollary (10.12)] Let f : P → P be a closure operator; that is, f is order-preserving, idempotent, and f(p) ≥ p for all p in P. Then f induces a strong deformation retraction of P onto its image f(P), the subposet of closed sets. □ Lemma 6. [2, Theorem (10.8)] Let L be a finite lattice which is not atomic, i.e. the atoms of L have join strictly smaller than ˆ1. Then L \ {ˆ0, ˆ1} is contractible. Dually, the same holds if L is not coatomic. □

We can now recall and prove Theorem 1 from the introduction.

Theorem 1. L_{conv}^{∘}(M), Δ_{acyclic}(M) and Δ_{free}(M) are all homotopy equivalent. Furthermore they are homotopy equivalent to a

\{ \begin{matrix}sphere 𝕊^{r(M)−1} & if M is totally cyclic \\ point & otherwise. \end{matrix}

Proof. (cf. [3, proof of Theorem 2.2]) We first note that L_{conv}^{∘}(M) is a strong deformation retract of Δ_{acyclic}(M), since the map A ↦ conv(A) is a closure operator on the poset of acyclic sets ordered by inclusion, whose subposet of closed sets is L_{conv}^{∘}(M).

We next show that L_{conv}^{∘}(M) and Δ_{free}(M) are homotopy equivalent. Note, that whenever a convex set A is not free, the closed interval [∅, A] below it in L_{conv}(M) is not coatomic, and hence the open interval (∅, A) is contractible by Lemma 6. So by Lemma 4 one can remove the non-free sets from L_{conv}^{∘}(M) without affecting the homotopy type, leaving a subposet isomorphic to the poset of nonempty faces of Δ_{free}(M). Since the order complex of the face poset of a simplicial complex is isomorphic to the barycentric subdivision of that complex, what remains is homeomorphic to Δ_{free}(M).

It is left to verify that Δ_{acyclic}(M) has the asserted homotopy type, for which we will use the Folkman-Lawrence topological representation theorem [4, §5.2]. This says that M has a representation by oriented pseudospheres lying on a (r(M) − 1)- sphere, denoted by 𝕊^{r(M)−1}, in which the covectors are the sign patterns of the cells in the cellular decomposition with respect to the positive and negative hemispheres of each pseudosphere.

Let U denote the subset of 𝕊^{r(M)−1} covered by the union of the open positive hemispheres. The Folkman-Lawrence Theorem [4, §5.2] implies that this is a good covering in the sense that all intersections of spaces in the covering are contractible, and by definition, the nerve of this covering is exactly Δ_{acyclic}(M). Hence by the Nerve Theorem [2, (10.7)], Δ_{acyclic}(M) is homotopy equivalent to the union U ⊂ 𝕊^{r(M)−1}.

When M is totally cyclic, we claim that the union U is all of 𝕊^{r(M)−1}. Note, that any cell not in U must correspond to a non-zero non-positive covector in M, and hence (by the negation axiom [4, Axiom L1, p. 159] for covectors) M would have a non-negative covector, contradicting total cyclicity.

In the remaining case where M is not totally cyclic, we first identify the complement 𝕊^{r(M)−1} − U. This comes from the following observation, which must be known, but we were unable to find in the literature.

Proposition 7. For any oriented matroid M with ground set E, there is a unique flat V ⊂ E having the property that

• the contraction M/V is acyclic, and

• the restriction M|_{V} is totally cyclic. Furthermore, let f be the covector of M defined by

f(e) = \begin{cases}0 & e ∈ V \\ + & e ∈ E − V \end{cases}

which is guaranteed to exist by the acyclicity of M/V. Then 𝕊^{r(M)−1} − U is the closure of the cell whose covector is −f.

Proof. Given M, note that for any two non-negative covectors f, g, the perturbation axiom [4, p. 159, Axiom L2] implies that there is a covector f ∘ g in M which is non-negative and whose positive support is exactly the union of the positive supports f^{−1}(+) ∪ g^{−1}(+). This implies that there is a unique non-negative covector f having maximum positive support under inclusion. Setting V := f^{−1}(0) to be the zero set of f, it is easy to check this pair (V, f) satisfies the conditions of the proposition, and the conditions of the proposition uniquely define V and f as above.

For the second assertion of the proposition, note that any cell in 𝕊^{r(M)−1} − U must correspond to a non-positive covector. Maximality of f then implies that any such cell is in the closure of the one corresponding to −f. □

We will use the following lemma to deduce that U is contractible (see [12] for definitions concerning collapsibility of CW-complexes).

Lemma 8. [6, Lemma 2.5] Let M be a regular-CW PL-manifold without boundary, and X, Y two subcomplexes of M. If X can be transformed to Y by a finite sequence of elementary collapses and anti-collapses within M, then M − X is homotopy equivalent to M − Y.

By [4, Theorem 5.2.1 (iii)] and [4, Prop. 4.7.26], 𝕊^{r(M)−1} is a regular-CW PLsphere. This implies that the barycentric subdivision M = Sd(𝕊^{r(M)−1}) is a regular-CW PL-sphere as well. Denote by σ the cell 𝕊^{r(M)−1} − U, and take X to be Sd(σ) and Y the barycenter vertex of X. Since σ is a closed cell, it follows that X is a cone with apex equal to the vertex Y and base equal to Sd(Bd(σ)). It is easy to see that any cone, such as X, can be collapsed to its apex vertex Y: order the non-empty faces not containing Y in weakly decreasing order of their dimension as F_{1}, F_{2}, …, and then F_{i} is a free face contained in the unique maximal face F_{i} ∪ {Y } after F_{1}, F_{2}, …, F_{i−1} have been collapsed. Hence by Lemma 8 the space U is homotopy equivalent to 𝕊^{r(M)−1} − Y, which is clearly contractible. □

Remark 9. The first assertion from Proposition 7 has an enumerative consequence concerning re-orientations of a fixed oriented matroid M on a ground set E, and the Tutte polynomial T_{M}(x, y) of the underlying matroid M. It is known [5, Prop. 6.2.11(iv), Prop. 6.3.17, Example 6.3.28] that the number of

• re-orientations of M is 2^{|E|} = T_{M}(2, 2),

• acyclic re-orientations of M is T_{M}(2, 0),

• totally cyclic re-orientations of M is T_{M}(0, 2).

Therefore, Proposition 7 implies

T_{M}(2, 2) = ∑_{flats V of M} T_{M|_{V}} (0, 2) T_{M/V} (2, 0).

This is a special case of a recent Tutte polynomial identity (see [11, 17])

T_{M}(x, y) = ∑_{flats V of M} T_{M|_{V}} (0, y) T_{M/V} (x, 0).

Question 10. Like the semilattices L_{conv}(M), there are many instances in the literature of semilattices having well-behaved lower intervals whose global topology is also wellbehaved, e.g., the geometric semilattices considered by Wachs and Walker [21], or the B_{n}-semimodular lattices from [20].

Is there some more general family of topologically well-behaved semilattices encompassing all of these examples?

3. Local topology of L_{conv}(M) and Δ_{acyclic}(M)

Having established the global homotopy type of the three objects

L_{conv}^{∘}(M), Δ_{acyclic}(M), Δ_{free}(M)

we next study the homotopy type of “local structures” within them. For the meetsemilattice L_{conv}(M), local structures mean open intervals (A, B) for nested convex sets A ⊂ B, and (principal) order filters L_{conv}(M)_{>A}. For Δ_{acyclic}(M) and Δ_{free}(M) local structures mean the links of faces. Recall that the link of a face F in a simplicial complex Δ is defined as

link_{Δ}(F) := {G ∈ Δ : F ∩ G = ∅, F ∪ G ∈ Δ}.

The present section deals with the topology of local structures within L_{conv}(M) and Δ_{acyclic}(M), leaving Δ_{free}(M) for the next section.

For intervals (A, B) in L_{conv}(M), the fact that lower intervals are always meetdistributive lattices determines their homotopy types as follows (see Lemma 16 below): in a meet-distributive lattice, an interval [A, B] is either

• isomorphic to a Boolean algebra 2^{B−A}, in which case the open interval (A, B) is homeomorphic to 𝕊^{|B−A|−2}. This occurs exactly when B − A is contained in the extreme points ex(B) in the associated convex geometry; that is, when A contains all the non-extreme points of B.

• not coatomic, in which case the open interval (A, B) is contractible by

Lemma 6 (and actually turns out to be a shellable ball). In light of this, it only remains to determine the homotopy type of order filters

L_{conv}(M)_{>A}. This turns out to be equivalent to studying links in Δ_{acyclic}(M): Proposition 11. If A ⊂ E is acyclic but not convex in M, then link_{Δ_{acyclic}(M)}(A) is a cone having apex given by any e in conv(A)−A. Consequently, it is contractible.

If A ⊂ E is convex in M, then the order filter L_{conv}(M)_{>A} is a strong deformation retract of link_{Δ_{acyclic}(M)}(A).

Proof. For the first assertion, note that the order complex of L_{conv}(M)_{>A} is the simplicial join of L_{conv}(M)_{>conv(A)} and the full simplex 2^{conv(A)−A}, since A ∪ B is acyclic if and only if conv(A) ∪ B is acyclic.

For the second assertion, consider

L_{conv}(M)_{>A} = {B ∈ L_{conv}(M) : A ⊂ B }

even in the case when A is not convex. The map B ↦ conv(A ∪ B) defined on the face poset of link_{Δ_{acyclic}(M)}(A) is a closure operator whose subposet of closed elements is L_{conv}(M)_{>A} (this is a generalization of the closure operator from the proof of Theorem 1). By Lemma 5 and the fact that the order complex of link_{Δ_{acyclic}(M)}(A) is homeomorphic to link_{Δ_{acyclic}(M)}(A), it follows that L_{conv}(M)_{>A} is a strong deformation retract of link_{Δ_{acyclic}(M)}(A). □

To understand the common homotopy type of L_{conv}(M)_{>A} and link_{Δ_{acyclic}(M)}(A) when A is convex, we introduce a subset of the Folkman-Lawrence sphere 𝕊^{r(M)−1} which has the same homotopy type. Let

I_{A} = ⋂_{e∈A} H_{e}^{+}

where H_{e}^{+} is the open positive pseudohemisphere labelled by e in the Folkman-Lawrence representation of M. Note that I_{A} is the interior of a ball by [4, Prop. 4.3.6], and hence contractible.

For each e′ ∉ A define I_{e′} = I_{A} ∩ H_{e′}^{+} and let

U_{A} = ⋃_{\begin{matrix}e′∉A \\ e′+A acyclic \end{matrix}} I_{e′}.

It follows from the definitions that link_{Δ_{acyclic}(M)}(A) is isomorphic to the nerve of the good covering

{I_{e′} : e′ ∉ A, e′ + A acyclic}

of U_{A}. Consequently we have:

Proposition 12. When A ⊂ E is convex, L_{conv}(M)_{>A} and link_{Δ_{acyclic}(M)}(A) are homotopy equivalent to U_{A}. □

It remains then for us to analyze the homotopy types of the spaces U_{A}. We begin with an easy sufficient condition for contractibility.

Lemma 13. If A is an acyclic set which is not f^{−1}(+) for some covector f of M, then U_{A} = I_{A}, a contractible set.

Consequently, if A is a convex set which is not of the form f^{−1}(+) for some covector, L_{conv}(M)_{>A} and link_{Δ_{acyclic}(M)}(A) are both contractible.

Proof. Suppose there is some point x of I_{A} −U_{A}, and let the unique cell of 𝕊^{r(M)−1} having x in its relative interior correspond to the covector f.

Since x is in I_{A}, we must have f(e) = + for all e ∈ A. For e ∉ A with e + A not acyclic, the definition of acyclicity forces f(e) ∈ {0, −}. For e ∉ A with e + A acyclic, the fact that x is not in U_{A} forces f(e) ∈ {0, −}. Hence f is a covector having f^{−1}(+) = A.

The second assertion of the lemma then follows from the previous proposition. □

Unfortunately, when A = f^{−1}(+) for some covector f, the homotopy type of these spaces can be arbitrarily complicated.

Proposition 14. For any finite simplicial complex Δ there exists a (realizable) oriented matroid M, and a convex subset A ⊂ E having U_{A} (and consequently also L_{conv}(M)_{>A} and link_{Δ_{acyclic}(M)}(A)) homotopy equivalent to Δ.

Proof. (Sketch) Let the vertex set of Δ be labelled {1, 2, …, r}, and let v_{1}, v_{2}, …, v_{r} be basis vectors for ℝ^{r}. Choose ϵ in the range (0, 1), and let M be the realizable oriented matroid corresponding to the vector configuration

A = {v_{1}, v_{2}, …, v_{r}} ∪ {v_{F} := ϵ ∑_{i∈F} v_{i} − ∑_{j∉F} v_{j}}_{F is a maximal face of Δ} .

Let A = {v_{1}, v_{2}, …, v_{r}}, which is easily seen to be convex, with I_{A} an open simplicial cell on the sphere 𝕊^{r−1}. We associate to a maximal face F of Δ the open set U(F) on the Folkman-Lawrence sphere corresponding to the union of all cells whose covector have value + on v_{1}, …, v_{r} and on v_{F}. One checks that {U(F)}_{F ∈Δ} is a good covering of U_{A}, whose nerve coincides with the nerve for the good covering of Δ by the closures of its maximal faces. Thus the Nerve Theorem [2, (10.7)] implies the assertion.

□

U({1, 2}) ∩ U({1, 3})  U({1, 2})  U({1, 2}) ∩ U({2, 3}) U({2, 3}) U({1, 3}) ∩ U({2, 3}) U({1, 3})

Figure 2: The covering of U_{A} from Proposition 14 for the simplicial complex Δ having maximal faces {{1, 2}, {1, 3}, {2, 3}}.

Although Proposition 14 is somewhat discouraging, in an important special case we can be much more precise. Say that M is antiparallel closed if for each e in M there is at least one element ē in E which is antiparallel to e; that is, {e, ē} form a positive circuit, or equivalently, every covector f has f(e) = + if and only if f(ē) = −. In the case where M is realized by an arrangement of vectors A, a sufficient condition for M to be antiparallel closed is that A is centrally symmetric, i.e., closed under negation.

In particular, root systems associated to finite reflection groups (see [14, §1.2]) are examples of antiparallel closed oriented matroids. Convex subsets of root systems were studied in [19] (see also [20]). It is easy to see that for the root system of type A_{n−1} consisting of all vectors {e_{i} − e_{j} : 1 ≤ i, j ≤ n}, convex subsets are equivalent to partially ordered sets on the numbers {1, 2, …, n}, with the extreme points ex(A) for a convex set A corresponding to the edges of the Hasse diagram of the associated poset. The semilattice L_{conv}(A_{n−1}) with a top element ˆ1 adjoined has been called the lattice of all posets, and its global and local homotopy type were studied by Björner and Welker [3], where it arose in their work on the topology of complexes of directed graphs. A similar study was undertaken for other root systems by Heckenbach [13]. The next result (and its proof) generalizes [3, Theorem 2.6], [13]. Theorem 15. Let M be an antiparallel closed oriented matroid, and A ⊂ E a convex set. Then link_{Δ_{acyclic}(M)}(A) and L_{conv}(M)_{>A} are homotopy equivalent to a

\{ \begin{matrix}sphere 𝕊^{r(M)−r(A)−1} & if A = f^{−1}(+) for some covector f \\ point & otherwise. \end{matrix}

Proof. Let L be the big face lattice [4, §4.1] of M and L^{∘} := L \ {ˆ0, ˆ1}. The map

ι : \begin{cases}L^{∘} & → & L_{conv}^{∘}(M) \\ f & ↦ & f^{−1}(+) \end{cases}

is easily seen to be order-preserving. It is also injective, since if ι(f) = A, one can recover f as follows:

f(e) = \begin{cases}+ & if e ∈ A \\ − & if e is antiparallel to an element of A \\ 0 & otherwise. \end{cases}

In proving the theorem, we may assume by Lemma 13 that we are in the case where A = f^{−1}(+) for some covector f, so that ι(f) = A. In this case, injectivity of ι implies that it restricts to a map from

ι : L_{>f}^{∘} → L_{conv}^{∘}(M)_{>A}.

It suffices to show that this restricted ι induces a homotopy equivalence, since L_{>f}^{∘} is the open interval above a face of dimension r(A)−1 in a shellable (r(M)−1)- sphere.

To apply the Fiber Lemma 3 to ι, we must show that for an arbitrary convex set B containing A, the subposet

ι^{−1}(L_{conv}(M)_{>B}) = {f ∈ L^{∘} : B ⊊ f^{−1}(+)}

is contractible. But [4, Prop. 4.3.6] shows that this is the poset of non-empty interior faces of a shellable ball, and hence is contractible. □

4. Local topology of Δ_{free}(M)

In this section we examine links in the complex Δ_{free}(M). These links turn out to be somewhat subtle in general, and we will be mainly interested in analyzing the homotopy type of links of vertices for use in the next section. On the other hand, we can say a little bit more, and some of this remains true at the higher level of generality given by convex geometries. As has already been noted, the set of convex sets of an acyclic oriented matroid is a special case of a convex geometry. So we give here a brief review of some of the theory of convex geometries- for a more detailed introduction see [9].

Let E be a finite set, and L a collection of subsets of E that contains ∅ and E and is closed under intersection. We can alternatively think of L as a closure operator on E defined by

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

We will say that L is anti-exchange if given any set C in L, and two unequal points p and q in E, neither in C, one has that

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

When L is anti-exchange, it will be called a convex geometry, and the subsets in L or, equivalently, those subsets A of E such that L(A) = A will be called convex sets. Let L_{conv}(L) be the lattice of convex sets of L ordered by containment and L_{conv}^{∘}(L) := L_{conv}(L) \ {∅}. This is a meet-distributive lattice, which is ranked by r(A) = |A|. Conversely, every meet-distributive lattice is isomorphic to L_{conv}(L) for some convex geometry L.

There are two ways to construct new convex geometries from L: restriction and contraction. If C is convex then let L|_{C} denote the restriction of the convex geometry L to the ground set C; that is, for A ⊂ C,

L|_{C}(A) = L(A) ∩ C.

Let L/C be the contraction defined as a closure by

L/C(A) = L(C ∪ A) − C

for all A ⊆ E − C.

An element a ∈ A with a ∉ L(A − {x}) is called an extreme point of A. Denote the set of extreme points of A by ex(A). It is a property of convex geometries that conv(ex(A)) = conv(A) [9]. Call a convex set C free if ex(C) = C. The set of free sets of a convex geometry form a simplicial complex denoted here Δ_{free}(L).

The following result on the topology of a meet-distributive lattice L_{conv}(L) (and hence also of its intervals) was already mentioned in the beginning of this section, and will be used further below. We sketch the proof for the sake of completeness.

Lemma 16. [9, Theorem 4.10] Let L be a convex geometry on a ground set E and let L = L_{conv}(L) be its lattice of convex sets. Then L^{∘} is homeomorphic to a

\begin{cases}ball 𝔹^{|E|−2} & if E ≠ ex(E) \\ sphere 𝕊^{|E|−2} & if E = ex(E) \end{cases} □

Proof. Meet-distributivity implies lower-semimodularity and hence shellability [2, (11.10 (iv))]. It also implies that intervals of length 2 have either 3 or 4 elements. Consequently L is either a ball or sphere by [4, Prop. 4.7.22] [2, Theorem 11.4].

If E = ex(E) then L is a Boolean algebra of rank |E|. Hence the order complex of L^{∘} is the barycentric subdivision of the boundary of an (|E| − 2)-simplex, which is a sphere.

If E ≠ ex(E) then L is not coatomic, so L^{∘} must be contractible by Lemma 6, and hence a ball. □

Before we can analyze Δ_{free}(L) in more detail we need the following simple lemma. Recall that the restriction of a simplicial complex Δ to a subset A of the ground set is the simplicial complex

Δ|_{A} := {B ∈ Δ | B ⊆ A }.

Lemma 17. In any convex geometry L, if A is a convex set contained in the extreme points of L then

(a)

link_{Δ_{free}(L)}(A) = Δ_{free}(L/A)

(b)

Δ_{free}(L)|_{E−A} = Δ_{free}(L|_{E−A})

as simplicial complexes on the ground set E − A.

Proof. Let B ⊂ E be disjoint from A.

(a): By definition of contraction, A ∪ B is convex in L if and only if B is convex in L/A. Therefore

B ∈ link_{Δ_{free}(L)}(A) ⇔ ex_{L}(A ∪ B) = A ∪ B
⇔ e ∉ L((A ∪ B) − e) ∀e ∈ A ∪ B
⇔ e ∉ L((A ∪ B) − e) − A ∀e ∈ B
⇔ ex_{L/A}(B) = B
⇔ B ∈ Δ_{free}(L/A).

Note that the reverse direction of the third equivalence uses the fact that A is free. (b): By definition of restriction , B = B ∩ (E − A) is convex in L|_{E−A} if and only if B is convex in L. Note that since A is a set of extreme points, we have e ∉ L(B) for e ∈ A. Therefore

B ∈ Δ_{free}|_{E−A} ⇔ ex_{L}(B) = B
⇔ e ∉ L(B − e) ∀e ∈ B
⇔ e ∉ L|_{E−A}(B − e) ∀e ∈ B
⇔ ex_{L|_{E−A}}(B) = B
⇔ B ∈ Δ_{free}(L|_{E−A}).
□

We next review some definitions related to collapsing within simplicial complexes; a good reference is Glaser [12]. A face G in a simplicial complex is called free if G is not maximal and is contained in a unique maximal face of Δ (we hope that no confusion results from the conflict of well-established terminologies here; a free set in a convex geometry or oriented matroid has nothing to do with a free face of a simplicial complex). If G is a free face of Δ one calls Δ[G] := Δ−{F ∈ Δ : G ⊆ F } an elementary collapse of Δ. A subcomplex Γ of Δ is called a collapse of Δ if there is a sequence G_{0}, …, G_{n} such that

• Δ_{0} = Δ,

• Δ_{i+1} = Δ_{i}[G_{i}] is an elementary collapse for i = 0, 1, …, n.
• Δ_{n+1} = Γ.

If Γ = ∅ is a collapse of Δ then Δ is called collapsible. By [12], if Γ ≠ ∅ is a collapse of Δ then Γ is a strong deformation retract of Δ. In particular, if Δ ≠ ∅ is collapsible then Δ is contractible. There is a particularly nice sufficient condition for collapsibility known as non-evasiveness (see [15]): a simplicial complex Δ on ground set V is called non-evasive if either |V | = 1 and Δ is a single vertex, or there is a v ∈ V such that link_{Δ}(v) and Δ|_{V −v} are both non-evasive on the ground set V \ v. Theorem 18. Let L be a convex geometry on ground set E, A a convex set of extreme points and Δ_{free} its simplicial complex of free sets. Then link_{Δ_{free}}(A) is non-evasive, and hence collapsible and contractible.

Proof. By Lemma 17 we know that link_{Δ_{free}}(A) = Δ_{free}(L/A). Hence we may assume A = ∅, and we need only show that Δ_{free} itself is non-evasive.

If ex(E) = E, then Δ_{free} is a simplex and there is nothing to prove. For an extreme point e ∈ E we have by Lemma 17 that link_{Δ_{free}}(e) = Δ_{free}(L/e) and Δ_{free}|_{E−e} = Δ_{free}(L|_{E−e}). Thus by induction on the cardinality of the ground set it follows that link_{Δ_{free}}(e) and Δ_{free}|_{E−e} are non-evasive. □

Corollary 19. If M is an acyclic oriented matroid and A ⊂ ex(M) is convex, then link_{Δ_{free}(M)}(A) is collapsible and hence contractible. □

We will need the following topological fact in the proof Theorem 2. Call a face F of a simplicial complex Δ exposed if link_{Δ}(F) is collapsible. Define the deletion and star of F in Δ as follows:

del_{Δ}(F) : = {G ∈ Δ : G ⊉ F }
star_{Δ}(F) : = {G ∈ Δ : G ∪ F ∈ Δ }

Proposition 20. If F is an exposed face in Δ then del_{Δ}(F) is a collapse of Δ.

Proof. Let G_{0}, …, G_{n} be a sequence of faces of link_{Δ}(F) such that Γ_{0} = link_{Δ}(F), Γ_{i+1} = Γ_{i}[G_{i}] is an elementary collapse, and Γ_{n+1} = ∅.

Then G_{0} ∪ F, …, G_{n} ∪ F is a sequence of faces of Δ such that Γ′_{0} = Δ, Γ′_{i+1} = Γ′_{i}[G_{i} ∪ F], is an elementary collapse, and Γ′_{n+1} = del_{Δ}(F). □

We now return to the discussion of links of vertices in Δ_{free}(M) for a simple oriented matroid M. Our immediate goal is to compare link_{Δ_{free}(M)}(e) with Δ_{free}(Simp(M/e)). We begin with some observations about the relationship between the convex hull operator in M and in Simp(M/e). Recall that M/e is defined to be an oriented matroid on ground set E − e, having covectors given by the restrictions to E − e of those covectors f of M with f(e) = 0, and Simp(M/e) is its simplification.

Note that an acyclic set containing e never contains an antiparallel to e, i.e. those elements which give rise to loops in M/e. Also note that since M is simple, in each parallelism class ℭ of M/e there is a unique element e_{ℭ} such that {e, e_{ℭ}} is free in M. For this reason, we can consider Simp(M/e) as an oriented matroid over the ground set E_{Simp(M/e)} consisting of the elements e_{ℭ}, where ℭ runs through the non-loop paralellism classes of M/e. One can check that link_{Δ_{free}}(e), which by definition is a simplicial complex over the ground set E − e, in fact only contains simplices from E_{Simp(M/e)}. Proposition 21. If A ⊂ E_{Simp(M/e)} is convex in Simp(M/e) then

(a) A is convex in M,

(b) A + e is convex in M, and

(c) ex_{Simp(M/e)}(A) + e ⊂ ex_{M}(A + e).

Proof. For part (a), we must show conv_{M}(A) = A. Rephrased, we must show that if e′ in E − A has the property that every covector f of M with f identically + on A also has f(e′) = +, then e′ is in A. First note that this property for e′ implies e′ ≠ e: since A is convex in Simp(M/e) implies A is acyclic in Simp(M/e), there must be some covector f of M with f(e) = 0 and f identically + on A.

It is then easy to see that e′ lies in conv_{Simp(M/e)}(A): any covector f of M with f(e) = 0 (that is, a covector of Simp(M/e)) which is identically + on A will have f(e′) = + by a particular case of our assumption on e′. Hence e′ ∈ conv_{Simp(M/e)}(A) = A, so A is convex in M.

For part (b), we must show conv_{M}(A + e) = A + e. Rephrased, we must show that if e′ in E −A−e has the property that every covector f of M with f identically + on A + e also has f(e′) = +, then e′ is in A + e. We will show that e′ lies in conv_{Simp(M/e)}(A) = A in this case. To see this, assume g is a covector of M with g(e) = 0 (that is, a covector of Simp(M/e)) which is identically + on A. We must show g(e′) = +. Since e′ is not parallel to e (else A would not have been convex in Simp(M/e)), there is some covector h of M having h(e′) = − and h(e) = +. Then the covector g ∘ h of M, guaranteed to exist by the perturbation axiom [4, Axiom L2], will be identically + on A since g was, and have (g ∘ h)(e) = +. The property assumed for e′ implies (g ∘ h)(e′) = +. Since h(e′) = −, this implies g(e′) = +, as desired.

For part (c), note that e lies in ex_{M}(A + e) by parts (a) and (b). Given a in ex_{Simp(M/e)}(A), we know conv(A) and conv(A)−a are both convex in Simp(M/e). Hence by part (b), conv(A)+e, conv(A)+e−a are both convex in M. This implies a is in ex_{M}(conv(A) + e), so a is in ex_{M}(A + e). □

It immediately follows from Proposition 21 that Δ_{free}(Simp(M/e)) is a subcomplex of link_{Δ_{free}(M)}(e). We can now recall and prove Theorem 2 from the introduction.

Theorem 2. link_{Δ_{free}(M)}(e) is a collapse (and hence a strong deformation retract) of Δ_{free}(Simp(M/e)) .

Proof. Call a subset A in link_{Δ_{free}(M)}(e)−Δ_{free}(Simp(M/e)) unwanted. Our strategy will be to collapse away the unwanted faces from link_{Δ_{free}(M)}(e) in stages.

To be more precise, let Δ_{0} := link_{Δ_{free}(M)}(e). Having defined Δ_{i−1}, let A_{i} be an unwanted face in Δ_{i−1} with Ā_{i} := conv_{Simp(M/e)}(A_{i}) of maximum cardinality. Then let F_{i} := ex_{Simp(M/e)}(A_{i}), and define Δ_{i} := del_{Δ_{i−1}}(F_{i}). We claim that F_{i} is an unwanted face of Δ_{i}. If not, then F_{i} is an element of Δ_{free}(Simp(M/e)), and hence is convex in Simp(M/e). But this would imply

F_{i} = conv_{Simp(M/e)}(F_{i}) = conv_{Simp(M/e)}(A_{i}) = Ā_{i} ⊃ A_{i},

contradicting the fact that A_{i} is unwanted.

We claim further that F_{i} is always an exposed face in Δ_{i−1}, which would complete the proof via Lemma 20. To prove this claim, we must show that link_{Δ_{i−1}}(F_{i}) is collapsible . Let M′ denote the restriction M|_{Ā_{i}+e} of the matroid M to the subset Ā_{i} + e. Collapsibility of link_{Δ_{i−1}}(F_{i}) follows from Corollary 19 and the following three subclaims:

Subclaim 1: link_{Δ_{i−1}}(F_{i}) = link_{Δ_{free}(M′)}(F_{i} + e). Subclaim 2: M′ is acyclically oriented (so that it gives rise to a convex geometry). Subclaim 3: F + e ⊂ ex_{M′}(Ā_{i} + e) (= ex(M′)).

Subclaims 2 and 3 are easy. To see Subclaim 2, note that Ā_{i} is convex in Simp(M/e) by definition, implying Ā_{i} + e is convex in M by Proposition 21 part (b). Hence Ā_{i} + e is acyclic in M.

To see Subclaim 3, note that the extreme elements of Ā_{i} + e in M′ are the same as its extreme elements in M, since we’ve already seen that Ā_{i} + e is convex in M. Then F_{i} + e ⊂ ex_{M}(Ā_{i} + e) by Proposition 21 part (c).

For Subclaim 1, we show that the left-hand and right-hand sides are contained in each other. Given F in the right-hand side, we have that F ∩ (F_{i} + e) = ∅ and F ∪ F_{i} + e is free in M′ = M|_{Ā_{i}+e}. Since Ā_{i} + e is convex, this implies F ∪ F_{i} + e is also free in M, so F is in the left-hand side.

Given F in the left-hand side, we have F ∩ F_{i} = ∅ and F ∪ F_{i} ∈ Δ_{i−1}. Note that F ∪ F_{i} is unwanted since F_{i} is. Then

Ā_{i} = conv_{Simp(M/e)}(A_{i}) = conv_{Simp(M/e)}(F_{i}) ⊂ conv_{Simp(M/e)}(F ∪ F_{i})

implies that the last inclusion must actually be an equality, otherwise we would contradict the maximality of Ā_{i}. Thus F ∪ F_{i} ⊂ Ā_{i}. To show that F lies in the right-hand side, we must show F ∪ F_{i} + e is free in M′ = M|_{Ā_{i}+e}. We know that F ∪ F_{i} + e is free in M since

F ∈ link_{Δ_{i−1}}(F_{i}) ⊂ link_{Δ_{0}}(F_{i}) = link_{Δ_{free}(M)}(F_{i} + e).

Therefore F ∪ F_{i} + e is also free in M′. □

5. Application: counting interior elements

The goal of this section is Theorem 23 below. As mentioned earlier, in the case of a realizable acyclically oriented matroid, this result was conjectured in [1], and proven in [10] and [16]. Aside from the fact that Theorem 23 generalizes the main result of [10], the proof below simplifies conceptually the topological proof given there.

Say that an element e ∈ E is interior if the contracted matroid M/e is totally cyclic. Note that in the case where M is the (realizable, acyclically oriented) oriented matroid corresponding to an affine point configuration A, the element e will be interior exactly when it corresponds to a point of A which lies in the relative interior of the convex hull of A. Also note that when M is itself totally cyclic, every element e in E is interior.

The definition of interior elements together with Theorems 1 and 2 immediately imply

Corollary 22. For any e in E, we have that link_{Δ_{free}(M)}(e) is homotopy equivalent to a

\{ \begin{matrix}sphere 𝕊^{r(M)−2} & if e is interior \\ point & otherwise. \end{matrix}

Define the β invariant of M by

β(L_{conv}(M)) := ∑_{A∈L_{conv}(M)} μ(ˆ0, A) rank_{L_{conv}(M)}(A)

where μ(−, −) denotes the Möbius function in L_{conv}(M).

Theorem 23. For any oriented matroid M,

β(L_{conv}(M)) = (−1)^{r(M)−1}#{interior elements e in E}.

Proof. For a convex set A, the interval [ˆ0, A] in L_{conv}(M) is meet-distributive, and hence coatomic if and only if A is free, in which case it is a Boolean algebra of rank |A|. Consequently, we have

β(L_{conv}(M)) := ∑_{A∈L_{conv}(M)} μ(ˆ0, A) rank_{L_{conv}(M)}(A)

= ∑_{free A⊆E}(−1)^{|A|}|A|

= ∑_{e∈E} ∑_{\begin{matrix}A free \\ e∈A \end{matrix}} (−1)^{|A|}

= ∑_{e∈E} −χ̃(link_{Δ_{free}(M)}(e))

where here χ̃ denotes reduced Euler characteristic. The result then follows from Corollary 22, since χ̃ is a homotopy invariant that vanishes for a point, and satisfies χ̃(𝕊^{r}) = (−1)^{r}. □

6. Acknowledgement

The authors thank Lou Billera for asking a question that led to this work, and Xun Dong for suggesting the use of Lemma 8 to shorten the proof of Theorem 1. They also thank Christos Athanasiadis and Frank Sottile for pointing out the necessary assumption of simplicity on the oriented matroid M. The second and third authors thank the Mathematisches Forschungsinstitut Oberwolfach for its hospitality during the 1999 conference on commutative algebra where some of this work was completed.

References

[1] C. Ahrens, G. Gordon and E. McMahon, Convexity and the beta invariant, Discrete Comput. Geom. 22 (1999), 411–424.

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

[3] A. Björner and V. Welker, Complexes of directed graphs, SIAM J. Discrete Math. 12 (1999), 413–424 (electronic).

[4] A. Björner, M. Las Vergnas, B. Sturmfels, N. White and G.M. Ziegler, Oriented matroids, Encyclopedia of Mathematics 46, Cambridge University Press, Cambridge, 1993.

[5] T. Brylawski and J. Oxley, The Tutte polynomial and its applications, in Matroid applications, Encyclopedia Math. Appl. 40, pp. 123–225, Cambridge University Press, Cambridge, 1992.

[6] X. Dong, Alexander duality for projections of polytopes, preprint, 2000 (available at

www.math.umn.edu/˜ xdong).

[7] P. H. Edelman, The lattice of convex sets of an oriented matroid, J. Combin. Theory Ser. B 33 (1982), 239–244.

[8] P. H. Edelman, The acyclic sets of an oriented matroid, J. Combin. Theory Ser. B 36 (1984), 26–31.

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

[10] P.H. Edelman and V. Reiner, Counting the interior points of a point configuration, Discrete and Comput. Geom. 23 (2000), 1–13.

[11] G. Etienne, On the Möbius algebra of geometric lattices, Europ. J. Combin. 19 (1998), 921–933.

[12] L.C. Glaser, Combinatorial Geometry Theory I, van Nostrand, New York, 1970.

[13] F. Heckenbach, Doctoral Thesis, Universität Erlangen, in preparation.

[14] J. E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics 29, Cambridge University Press, Cambridge, 1990.

[15] J. Kahn, M. Saks and D. Sturtevant, A topological approach to evasiveness, Combinatorica 4 (1984), 297–306.

[16] D. Klain, An Euler relation for valuations on polytopes, Adv. Math. 147 (1999), 1–34.

[17] W. Kook, V. Reiner, D. Stanton, A convolution formula for the Tutte polynomial, J. Combin. Theory Ser. B 76 (1999), 297-299.

[18] M. Las Vergnas, Convexity in oriented matroids, J. Combin. Theory Ser. B 29 (1980), 231– 243.

[19] V. Reiner, Quotients of Coxeter complexes and P-partitions, Ph.D. thesis, MIT, 1990.

[20] V. Reiner, Signed posets, J. Combin. Theory Ser. A 62 (1993), 324–360.

[21] M. Wachs and J.W. Walker, On geometric semilattices, Order 2 (1986), 367–385.

Department of Mathematics, Vanderbilt University, Nashville TN 37240, USA

   E-mail address, P.H. Edelman: edelman@math.vanderbilt.edu

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

Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, 35032 Marburg, Germany

   E-mail address, V. Welker: welker@mathematik.uni-marburg.de