\documentclass{amsart}
\usepackage{epsf}
\usepackage{amscd}
\usepackage{amsmath, amssymb, amsthm}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\A}{{\mathcal A}}
\newcommand{\M}{{\mathcal M}}
\newcommand{\U}{{\mathcal U}}
\newcommand{\sphere}{{\mathbb S}}
\newcommand{\ball}{{\mathbb B}}
\newcommand{\conv}{\mathrm{conv}}
\newcommand{\supp}{\mathrm{supp}}
\newcommand{\ex}{\mathrm{ex}}
\newcommand{\link}{\mathrm{link}}
\newcommand{\free}{\mathrm{free}}
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\Simp}{\mathrm{Simp}}
\newcommand{\DP}{\Delta_{\mathrm{acyclic}}}
\newcommand{\DF}{\Delta_{\mathrm{free}}}
\newcommand{\del}{\mathrm{del}}
\newcommand{\str}{\mathrm{star}}
\newcommand{\Po}{\mathbf{P}}
\newcommand{\Li}{\mathcal L}
\newcommand{\La}{\mathbf{L}}
\newcommand{\Bd}{\mathrm{Bd}}
\newcommand{\sd}{\mathrm{Sd}}
\newcommand{\C}{\mathfrak{C}}
\begin{document}
\title{Convex, acyclic, and free sets of an oriented matroid}
\author{Paul H. Edelman}
\address{Department of Mathematics\\
Vanderbilt University\\
Nashville TN 37240, USA}
\email[P.H. Edelman]{edelman@math.vanderbilt.edu}
\author{Victor Reiner}
\address{School of Mathematics\\
University of Minnesota\\
Minneapolis, MN 55455, USA}
\email[V. Reiner]{reiner@math.umn.edu}
\author{Volkmar Welker}
\address{Fachbereich Mathematik und Informatik\\
Philipps-Universit\"at Marburg\\
35032 Marburg, Germany}
\email[V. Welker]{welker@mathematik.uni-marburg.de}
\thanks{Work of Reiner was partially supported by
NSF grant DMS-9877047. Work of Edelman done while at
University of Minnesota.}
\begin{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.
\end{abstract}
\maketitle
\section{Introduction}
\label{intro}
An oriented matroid $\M$ of rank $r$ is a combinatorial abstraction of a
finite collection of vectors spanning $\reals^r$
(a {\it realizable} oriented matroid),
or a finite collection of points that affinely span
affine $(r-1)$-space (an {\it acyclic}, realizable oriented matroid) --
see \cite{OMbook} 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:
\begin{enumerate}
\item[$\triangleright$] the semilattice of convex sets $L_{\conv}(\M)$,
\item[$\triangleright$] the simplicial complex of acyclic sets $\DP(\M)$,
\item[$\triangleright$] the simplicial complex of free sets $\Delta_{\free}(\M)$.
\end{enumerate}
Our first main result is:
\begin{theorem}
\label{main}
$L_{\conv}(\M) \setminus \{ \emptyset \}$, $\DP(\M)$ and $\Delta_{\free}(\M)$,
are all homotopy equivalent. Furthermore they are homotopy equivalent to a
$$
\begin{cases}
\text{ sphere }\sphere^{r(\M)-1} & \text{ if }\M\text{ is totally cyclic} \\
\text{ point }& \text{ otherwise,} \\
\end{cases}
$$
where $r(\M)$ is the rank of the oriented matroid $\M$.
\end{theorem}
Several special cases of these objects and their homotopy types have
arisen previously in the literature.
\begin{enumerate}
\item[$\bullet$]
In the special case of an affine point configuration,
the semilattice $L_{\conv}(\M)$ is the
lattice of convex sets in the usual {\it convex geometry} (see \cite{EJ} and
Section \ref{application-section} below) associated to the point configuration.
In this case, the complex $\Delta_{\free}(\M)$
appeared in a conjecture of Ahrens, Gordon, and MacMahon \cite{AGM}
on a formula for the number of interior points in the point set.
Their conjecture was proven in \cite{ER},
using the topology of links of vertices in $\Delta_{\free}(\M)$
(and independently, in a purely enumerative fashion by Klain \cite{Kl}).
\item[$\bullet$]
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 \cite{LV}, and $L_{\conv}(\M)$
was studied further by Edelman \cite{Ed1} -- see \cite[p. 152, Exercises 3.9, 3.10]{OMbook}.
\item[$\bullet$]
In the case where $\M$ is antiparallel-closed
(see Section \ref{local-topology-1} below),
the topology of $\DP(\M)$ was studied by Edelman \cite{Ed2}, and
used to give a proof for the oriented matroid generalization
\cite[Theorem 4.6.1]{OMbook} of Zaslavsky's
formula for the number of chambers cut out by an arrangement of hyperplanes.
\item[$\bullet$]
A further special case arises in the work of Bj\"orner and Welker \cite{BW} on
the topology of complexes of directed graphs. There the complex $\DP(\M)$
appears as the {\it complex of acyclic directed graphs}, and $L_{\conv}(\M)$
appears as the {\it lattice of all posets}. Both are shown to
be homotopy equivalent to spheres, which we generalize in
Theorem~\ref{antiparallel} below.
\end{enumerate}
The contents of the paper are as follows.
Section \ref{global-structures} 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
$\DP(\M)$ and $\DF(\M)$. Section \ref{local-topology-1} deals with
local structures in $L_{\conv}(\M)$ and $\DP(\M)$. Here we find that,
as in Theorem \ref{main}, the homotopy types are essentially identical
(Proposition~\ref{convexinterval}), albeit
arbitrarily complicated (Proposition~\ref{universality}).
However, in the special case where $\M$ is antiparallel
closed, the homotopy type of these two local structures is either
spherical or contractible (Theorem~\ref{antiparallel}).
Section \ref{local-topology-2} deals with
links in $\DF(\M)$, which turn out to be more subtle. After reviewing some of
the theory of convex geometries \cite{EJ}, we closely examine
the link of a vertex $e$ in $\DF(\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.
\begin{theorem}
\label{contraction-link}
$\link_{\DF(\M)}(e)$ is a collapse (and hence a strong deformation retract)
of $\DF(\Simp(\M/e))$.
\end{theorem}
In Section \ref{application-section}, we apply Theorem \ref{contraction-link}
to prove a generalization (Theorem \ref{application})
of the conjecture of Ahrens, Gordon and MacMahon \cite{AGM} 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 \cite{ER}, by avoiding an
excursion into Gale transforms.
\section{Global homotopy type and cyclicity}
\label{global-structures}
The goal of this section is to establish terminology,
define the objects of study, and prove Theorem \ref{main}.
Recall that an oriented matroid
$\M$ on ground set $E$ may be specified by its collection of
{\it covectors}, which are functions $f: E \rightarrow \{+,0,-\}$,
satisfying the covector axioms \cite[p.159]{OMbook}. Throughout we
assume that $\M$ is {\em simple}, i.e. it contains no parallel
elements (although antiparallel elements are allowed) and no loops.
We will refer to a covector as being {\em positive} if all of its
entries are $+$, {\em non-negative} if all of its entries are $+$ or $0$,
and similarly for {\em negative} and {\em non-positive}.
We will also refer to the {\it positive support} $f^{-1}(+)$
of a covector $f$.
We say $\M$ is {\it acyclic} or {\it acyclically oriented}
if some covector $f$ is positive, and say that $\M$ is {\em totally cyclic} or
{\it totally cyclically oriented} if $(0,\ldots,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 $\reals^2$ is neither acyclic nor totally cyclic.
Say that a subset $A \subseteq E$ is {\it 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 {\it 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 {\it convex} if $\conv(A) = A$. The {\it extreme points}
$\ex(A)$ of an acyclic set $A$ are defined to be the points $a$ in $A$
such that $a \not\in \conv(A-\{a\})$.
It can be shown that $\conv(\ex(A)) = \conv(A)$ \cite{LV, Ed1}.
A convex set $A$ is {\it 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 $\DP(\M)$ (resp. $\Delta_{\free}(\M)$)
denote the simplicial complexes of acyclic (resp. free) subsets of $E$.
We write $L^\circ_{\conv}(\M)$ for $L_{\conv}(\M) \setminus \{ \emptyset \}$.
\vskip1cm
\begin{picture}(0,0)%
\epsffile{pointed_fig1.ps}%
\end{picture}%
\setlength{\unitlength}{1579sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\begin{picture}(14017,3576)(286,-3106)
\put(1456,450){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}A\special{ps: grestore}}}}
\put(3376,-2626){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}~a\special{ps: grestore}}}}
\put(286,-1306){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}\hskip0.3cm d\special{ps: grestore}}}}
\put(8866,-1951){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}d\special{ps: grestore}}}}
\put(3361,-106){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}~c\special{ps: grestore}}}}
\put(3361,-1336){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}~b\special{ps: grestore}}}}
\put(5506,134){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}abc\special{ps: grestore}}}}
\put(4647,-991){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}ab\special{ps: grestore}}}}
\put(4726,-1876){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}a\special{ps: grestore}}}}
\put(6871,-3114){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\emptyset$\special{ps: grestore}}}}
\put(5850,-991){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}bc\special{ps: grestore}}}}
\put(5986,-2056){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}b\special{ps: grestore}}}}
\put(7150,-1950){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}c\special{ps: grestore}}}}
\put(6961,450){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$L_{\conv}(\M)$\special{ps: grestore}}}}
\put(7324,-766){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}ad\special{ps: grestore}}}}
\put(8491,-781){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}cd\special{ps: grestore}}}}
\put(9736,450){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\DP(\M)$\special{ps: grestore}}}}
\put(10400,-100){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}b\special{ps: grestore}}}}
\put(10711,-2837){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}d\special{ps: grestore}}}}
\put(9856,-1285){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}a\special{ps: grestore}}}}
\put(11611,-1292){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}c\special{ps: grestore}}}}
\put(12743,450){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\DF(\M)$\special{ps: grestore}}}}
\put(13100,-100){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}b\special{ps: grestore}}}}
\put(12541,-1278){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}a\special{ps: grestore}}}}
\put(14303,-1292){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}c\special{ps: grestore}}}}
\put(13433,-2851){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}d\special{ps: grestore}}}}
\end{picture}
\bigskip
\begin{center}
{\bf Figure 1:} Convex, free and acyclic sets for the oriented matroid $\M$ given by the
point configuration $A$.
\end{center}
\bigskip
It is easy to see that every proper lower interval
$[\hat{0},x]$ in $L_{\conv}(\M)$
is the poset of convex sets in a {\it convex geometry},
and hence is a {\it meet-distributive lattice}; that is, a lattice
in which every coatomic interval is Boolean; see \cite{EJ}
and Section \ref{local-topology-2} below.
This convex geometry was first considered by Las Vergnas
\cite{LV},\cite[p. 152, Exercise 3.9]{OMbook}.
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 $\hat 1$ to make it a lattice, this lattice
$L_{\conv}(\M)\cup \{\hat 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 $\reals^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 \ref{main}, we review some
notation and facts from combinatorial topology -- see \cite{Bj} and
\cite[Appendix 4.7]{OMbook} for more background.
When referring to the topology of a simplicial complex,
we mean the topology of its {\it geometric realization}.
When referring to the topology of a poset $P$ we mean the topology of
its {\it 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 \in P$ we denote by $P_{\leq p}$ the poset $\{
q \in P~:~q \leq p~\}$. Analogously defined are the posets $P_{< p}$,
$P_{\geq p}$ and $P_{> p}$.
When $P$ is a lattice (resp. meet-semilattice) we denote by $\hat{0}$ and
$\hat{1}$ (resp. $\hat{0}$) its unique minimal and maximal (resp. unique
minimal) element.
We will make frequent use of the following well-known tools.
\begin{lemma}[Quillen Fiber Lemma] \cite[Lemma 4.7.29]{OMbook}
\label{quillen}
If $f: P \rightarrow Q$ is an order-preserving map of posets
with $f^{-1}(Q_{\leq q})$ contractible for all $q$ in $Q$, then
$f$ induces a homotopy equivalence of $P$ and $Q$.
\noindent Dually, the same holds if $f^{-1}(Q_{\geq q})$ is contractible for all $q$ in $Q$.
\qed
\end{lemma}
\begin{lemma}
\label{remove-a-sequence}
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 \hookrightarrow P$
induces a homotopy equivalence.
\end{lemma}
\begin{proof}
Assume the $p_i$ are indexed so that $p_i < p_j$ implies $i>j$, and then
apply the Quillen Fiber Lemma, Lemma \ref{quillen}, to each inclusion
$$
P-\{p_i\}_{i=1}^{j} \hookrightarrow P-\{p_i\}_{i=1}^{j-1}.
$$
\end{proof}
\begin{lemma} \cite[Corollary (10.12)]{Bj}
\label{closure-operator}
Let $f: P \rightarrow P$ be a closure operator; that is,
$f$ is order-preserving, idempotent, and $f(p) \geq 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.
\qed
\end{lemma}
\begin{lemma} \cite[Theorem (10.8)]{Bj}
\label{crosscut}
Let $L$ be a finite lattice which is not atomic,
i.e. the atoms of $L$ have join strictly smaller than $\hat{1}$.
Then $L \setminus \{ \hat{0},\hat{1}\}$ is contractible.
\noindent Dually, the same holds if $L$ is not coatomic.\qed
\end{lemma}
We can now recall and prove Theorem \ref{main} from the introduction.
\vskip .1in
\noindent
{\bf Theorem \ref{main}}.
{\it
$L^\circ_{\conv}(\M), \DP(\M)$ and $\Delta_{\free}(\M)$
are all homotopy equivalent. Furthermore they are homotopy equivalent to a
$$
\begin{cases}
\text{ sphere }\sphere^{r(\M)-1} & \text{ if }\M\text{ is totally cyclic} \\
\text{ point }& \text{ otherwise.} \\
\end{cases}
$$
}
\begin{proof} (cf. \cite[proof of Theorem 2.2]{BW})
We first note that $L^\circ_{\conv}(\M)$ is a strong deformation retract of
$\DP(\M)$, since the map
$A \mapsto \conv(A)$ is a closure operator on the poset of
acyclic sets ordered by inclusion, whose subposet of closed sets
is $L^\circ_{\conv}(\M)$.
We next show that $L^\circ_{\conv}(\M)$ and $\Delta_{\free}(\M)$ are homotopy equivalent.
Note, that whenever a convex set $A$ is not free, the closed interval $[\emptyset,A]$
below it in $L_{\conv}(\M)$ is not coatomic, and hence the open
interval $(\emptyset,A)$ is contractible
by Lemma~\ref{crosscut}. So by Lemma \ref{remove-a-sequence}
one can remove the non-free sets from $L^\circ_{\conv}(\M)$
without affecting the homotopy type, leaving a subposet isomorphic to the
poset of non-empty faces of $\Delta_{\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 $\Delta_{\free}(\M)$.
It is left to verify that $\DP(\M)$
has the asserted homotopy type, for which we will
use the Folkman-Lawrence topological representation theorem
\cite[\S 5.2]{OMbook}. This says that $\M$ has a representation by oriented
pseudospheres lying on a $(r(\M)-1)$-sphere, denoted by $\sphere^{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
$\sphere^{r(\M)-1}$ covered by the union of the {\it open} positive hemispheres.
The Folkman-Lawrence Theorem \cite[\S 5.2]{OMbook} 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 $\DP(\M)$. Hence by the Nerve Theorem \cite[(10.7)]{Bj},
$\DP(\M)$ is homotopy equivalent to the union
$\U \subset \sphere^{r(\M)-1}$.
When $\M$ is totally cyclic, we claim that the union $\U$
is {\it all} of $\sphere^{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 \cite[Axiom L1, p. 159]{OMbook} 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 $\sphere^{r(\M)-1} - \U$. This comes from
the following observation, which must be known, but we were
unable to find in the literature.
\begin{proposition}
\label{canonical-decomposition}
For any oriented matroid $\M$ with ground set $E$, there is a unique flat
$V \subset E$ having the property that
\begin{enumerate}
\item[$\bullet$]
the contraction $\M/V$ is acyclic, and
\item[$\bullet$]
the restriction $\M|_V$ is totally cyclic.
\end{enumerate}
Furthermore, let $f$ be the covector of $\M$ defined by
$$
f(e) =
\begin{cases}
0 & e \in V \\
+ & e \in E-V\\
\end{cases}
$$
which is guaranteed to exist by the
acyclicity of $\M/V$. Then $\sphere^{r(\M)-1} - \U$
is the closure of the cell whose covector is $-f$.
\end{proposition}
\begin{proof}
Given $\M$, note that for any two non-negative covectors $f$, $g$, the
perturbation axiom \cite[p. 159, Axiom L2]{OMbook} implies that there
is a covector $f \circ g$ in $\M$ which is non-negative
and whose positive support is exactly the union of the positive supports
$f^{-1}(+) \,\, \cup \,\, 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
$\sphere^{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$.
\end{proof}
We will use the following lemma to deduce that $\U$ is
contractible (see \cite{Gla} for definitions concerning
collapsibility of CW-complexes).
\begin{lemma} \cite[Lemma 2.5]{xdong} \label{xdong} 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$.
\end{lemma}
By \cite[Theorem 5.2.1 (iii)]{OMbook} and
\cite[Prop. 4.7.26]{OMbook}, $\sphere^{r(\M)-1}$ is a regular-CW PL-sphere.
This implies that the barycentric subdivision $M = \sd(\sphere^{r(\M)-1})$ is a
regular-CW PL-sphere as well. Denote by $\sigma$ the cell $\sphere^{r(\M)-1} - \U$,
and take $X$ to be $\sd(\sigma)$ and $Y$ the barycenter vertex of $X$.
Since $\sigma$ is a closed cell, it follows that
$X$ is a cone with apex equal to the vertex $Y$ and base equal
to $\sd( \Bd(\sigma))$. 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,\ldots,$ and then $F_i$ is a free face contained
in the unique maximal face $F_i \cup \{Y\}$
after $F_1,F_2,\ldots,F_{i-1}$ have been collapsed.
Hence by Lemma \ref{xdong} the space $\U$ is
homotopy equivalent to $\sphere^{r(\M)-1} - Y$, which
is clearly contractible.
\end{proof}
\begin{remark} \rm \ \\
The first assertion from Proposition \ref{canonical-decomposition}
has an enumerative consequence concerning {\it re-orientations} of a
fixed oriented matroid $\M$ on a ground set $E$, and the {\it Tutte
polynomial} $T_M(x,y)$ of the underlying matroid $M$.
It is known \cite[Prop. 6.2.11(iv), Prop. 6.3.17, Example 6.3.28]{BO}
that the number of
\begin{enumerate}
\item[$\bullet$]
re-orientations of $\M$ is $2^{|E|} = T_M(2,2)$,
\item[$\bullet$]
acyclic re-orientations of $\M$ is $T_M(2,0)$,
\item[$\bullet$]
totally cyclic re-orientations of $\M$ is $T_M(0,2)$.
\end{enumerate}
Therefore, Proposition \ref{canonical-decomposition} implies
$$
T_M(2,2) = \sum_{\text{flats }V\text{ of }M} T_{M|_V}(0,2) \,\, T_{M/V}(2,0).
$$
This is a special case of a recent Tutte polynomial identity
(see \cite{Et,KRS})
$$
T_M(x,y) = \sum_{\text{flats }V\text{ of }M} T_{M|_V}(0,y) \,\, T_{M/V}(x,0).
$$
\end{remark}
\begin{question} \rm \ \\
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 well-behaved,
e.g., the {\it geometric semilattices} considered by Wachs and
Walker \cite{WW}, or the $B_n$-{\it semimodular} lattices from \cite{Re2}.
Is there some more general family of topologically well-behaved
semilattices encompassing all of these examples?
\end{question}
\section{Local topology of $L_{\conv}(\M)$ and $\DP(\M)$ }
\label{local-topology-1}
Having established the global homotopy type of the three objects
$$
L^\circ_{\conv}(\M), \ \ \DP(\M),\ \ \Delta_{\free}(\M)
$$
we next study the homotopy type of ``local structures'' within them.
For the meet-semilattice $L_{\conv}(\M)$, local structures mean open intervals
$(A,B)$ for nested convex sets $A \subset B$,
and (principal) order filters $L_{\conv}(\M)_{> A}$.
For $\DP(\M)$ and $\Delta_{\free}(\M)$
local structures mean the links of faces. Recall that the
{\it link} of a face $F$ in a simplicial complex $\Delta$
is defined as
$$
\link_{\Delta}(F) := \{ G \in \Delta: F \cap G = \emptyset, F \cup G \in \Delta\}.
$$
The present section deals with the topology of local structures within
$L_{\conv}(\M)$ and $\DP(\M)$, leaving $\Delta_{\free}(\M)$ for the next section.
For intervals $(A,B)$ in $L_{\conv}(\M)$, the fact that lower intervals
are always meet-distributive lattices determines their homotopy types
as follows (see Lemma \ref{convexgeomtopology} below):
in a meet-distributive lattice, an interval $[A,B]$ is either
\begin{enumerate}
\item[$\bullet$]
isomorphic to a Boolean algebra $2^{B-A}$, in which case the open interval
$(A,B)$ is homeomorphic to $\sphere^{|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$.
\item[$\bullet$]
not coatomic, in which case the open interval $(A,B)$ is contractible by
Lemma~\ref{crosscut} (and actually turns out to be a shellable ball).
\end{enumerate}
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 $\DP(\M)$:
\begin{proposition}\label{convexinterval}
If $A \subset E$ is acyclic but not convex in $\M$, then
$\link_{\DP(\M)}(A)$ is a cone having apex given by
any $e$ in $\conv(A)-A$. Consequently, it is contractible.
If $A \subset E$ is convex in $\M$, then the order filter
$L_{\conv}(\M)_{> A}$ is a strong deformation retract of $\link_{\DP(\M)}(A)$.
\end{proposition}
\begin{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 \cup B$ is acyclic if and only if $\conv(A) \cup B$
is acyclic.
For the second assertion, consider
$$
L_{\conv}(\M)_{> A} = \{ B \in L_{\conv}(\M)~:~A \subset B~\}
$$
even in the case when $A$ is not convex.
The map $B \mapsto \conv(A \cup B)$ defined on the face poset of
$\link_{\DP(\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~\ref{main}).
By Lemma~\ref{closure-operator} and the fact that the order
complex of $\link_{\DP(\M)}(A)$ is homeomorphic to $\link_{\DP(\M)}(A)$,
it follows that $L_{\conv}(\M)_{> A}$ is a strong deformation
retract of $\link_{\DP(\M)}(A)$.
\end{proof}
%Note, that $A \cup B$ is acyclic if and only if $\conv(A) \cup B$
%is acyclic. The first assertion when $A$ is not convex
%follows immediately from this.
%
%For the second assertion, note that when $A$ is convex,
%the closure operator $B \mapsto \conv(B)$ from the proof
%of Theorem~\ref{main} restricts to a map
%from $\link_{\DP(\M)}(A)$ onto $L_{\conv}(\M)_{> A}$.
%Lemma~\ref{closure-operator} again applies.
%\end{proof}
To understand the common homotopy type of
$L_{\conv}(\M)_{> A}$ and $\link_{\DP(\M)}(A)$ when $A$ is convex,
we introduce a subset of the Folkman-Lawrence sphere $\sphere^{r(\M)-1}$ which
has the same homotopy type. Let
\[
I_A= \bigcap_{e \in 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 \cite[Prop. 4.3.6]{OMbook}, and
hence contractible.
For each $e' \not\in A$
define $I_{e'}=I_A \cap H_{e'}^+$ and let
\[
\mathcal U_A=\bigcup_{\substack{e' \not\in A\\e'+A \text{ acyclic}}} I_{e'}.
\]
It follows from the definitions that $\link_{\DP(\M)}(A)$ is isomorphic to
the nerve of the good covering
\[
\left\{I_{e'}: e' \not\in A, \,\, e'+A \text{ acyclic}\right\}
\]
of $\mathcal U_A$. Consequently we have:
\begin{proposition}
When $A \subset E$ is convex,
$L_{\conv}(\M)_{> A}$ and $\link_{\DP(\M)}(A)$ are homotopy
equivalent to $\U_A$.\qed
\end{proposition}
It remains then for us to analyze the homotopy types of the spaces
$\U_A$. We begin with an easy sufficient condition
for contractibility.
\begin{lemma}
\label{acyclic-link}
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_{\DP(\M)}(A)$
are both contractible.
\end{lemma}
\begin{proof}
Suppose there is some point $x$ of $I_A-\U_A$, and let the unique cell
of $\sphere^{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 \in A$.
For $e \not\in A$ with $e + A$ not acyclic, the definition of
acyclicity forces $f(e) \in \{0,-\}$. For $e \not\in A$ with $e+A$ acyclic,
the fact that $x$ is {\it not} in $\U_A$ forces $f(e) \in \{0,-\}$.
Hence $f$ is a covector having $f^{-1}(+)=A$.
The second assertion of the lemma then follows from the previous proposition.
\end{proof}
Unfortunately, when $A=f^{-1}(+)$ for some covector $f$,
the homotopy type of these spaces can be arbitrarily complicated.
\begin{proposition}
\label{universality}
For any finite simplicial complex $\Delta$ there exists a (realizable) oriented
matroid $\M$, and a convex subset $A \subset E$ having
$\U_A$ (and consequently also $L_{\conv}(\M)_{> A}$ and $\link_{\DP(\M)}(A)$)
homotopy equivalent to $\Delta$.
\end{proposition}
\begin{proof}
(Sketch) Let the vertex set of $\Delta$ be labelled $\{1,2,\ldots,r\}$,
and let $v_1,v_2,\ldots,v_r$ be basis vectors for $\reals^r$.
Choose $\epsilon$ in the range $(0,1)$, and let $\M$ be the realizable
oriented matroid corresponding to the vector configuration
$$
\A = \{v_1,v_2,\ldots,v_r\} \cup
\left\{v_F := \epsilon \sum_{i \in F} v_i
- \sum_{j \not\in F} v_j\right\}_{F \text{ is a maximal face of }\Delta}.
$$
Let $A=\{v_1,v_2,\ldots,v_r\}$, which is easily seen to
be convex, with $I_A$ an open simplicial cell on the sphere $\sphere^{r-1}$.
We associate to a maximal face $F$ of $\Delta$ the open set $\U(F)$ on the
Folkman-Lawrence sphere corresponding to the union of all cells whose
covector have value $+$ on $v_1, \ldots, v_r$ and on $v_F$.
One checks that $\{\U(F)\}_{F \in \Delta}$ is a good covering
of $\U_A$, whose nerve coincides with the nerve for the good covering of
$\Delta$ by the closures of its maximal faces. Thus the Nerve
Theorem \cite[(10.7)]{Bj} implies the assertion.
%Label the vertices of the closed simplex $\overline{I_A}$ with
%$\{1,2,\ldots,r\}$ in such a way that the unique vertex
%which does {\it not} lie on $v_i^\perp$ is labelled $i$.
%We then claim that $\U_A$ is homotopy equivalent to $\Delta$.
%Rather than writing down an explicit homotopy, we hope that
%the reader will be convinced by drawing a few small examples.
\end{proof}
\vskip1cm
\begin{picture}(0,0)%
\epsffile{pointed_fig2.ps}%
\end{picture}%
\setlength{\unitlength}{2368sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\begin{picture}(8580,7197)(1141,-6526)
\put(1816,-6186){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{14.4}{\familydefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}${\mathcal U}(\{1,2\}) \cap {\mathcal U}(\{1,3\})$\special{ps: grestore}}}}
\put(5896,-6526){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{14.4}{\familydefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}${\mathcal U}(\{1,2\})$\special{ps: grestore}}}}
\put(8281,-4816){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{14.4}{\familydefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}${\mathcal U}(\{1,2\}) \cap {\mathcal U}(\{2,3\})$\special{ps: grestore}}}}
\put(8911,-331){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{14.4}{\familydefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}${\mathcal U}(\{2,3\})$\special{ps: grestore}}}}
\put(5311,300){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{14.4}{\familydefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}${\mathcal U}(\{1,3\}) \cap {\mathcal U}(\{2,3\})$\special{ps: grestore}}}}
\put(1141,-1250){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{14.4}{\familydefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}${\mathcal U}(\{1,3\})$\special{ps: grestore}}}}
\end{picture}
\bigskip
\begin{center}
{\bf Figure 2:} The covering of ${\mathcal U}_{\mathcal A}$ from
Proposition \ref{universality} for the simplicial complex $\Delta$
having maximal faces $\{\{1,2\},\{1,3\},\{2,3\}\}$.
\end{center}
\bigskip
Although Proposition \ref{universality} is somewhat discouraging,
in an important special case we can be much more precise.
Say that $\M$ is {\em antiparallel closed} if for each $e$ in $\M$
there is at least one element $\bar{e}$ in $E$ which is {\it antiparallel}
to $e$; that is, $\{e,\bar{e}\}$ form a positive circuit, or equivalently,
every covector $f$ has $f(e)=+$ if and only if $f(\bar{e})=-$. 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, {\it root systems} associated to finite reflection groups
(see \cite[\S 1.2]{Humphreys}) are examples of antiparallel closed oriented matroids.
Convex subsets of root systems were studied in \cite{Re1} (see also \cite{Re2}).
It is easy to see that for the root system of type $A_{n-1}$ consisting of all
vectors $\{e_i - e_j: 1 \leq i,j \leq n\}$, convex subsets are equivalent
to partially ordered sets on the numbers $\{1,2,\ldots,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 $\hat 1$ adjoined has
been called the {\it lattice of all posets}, and its global and local homotopy
type were studied by Bj\"orner and Welker \cite{BW},
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 \cite{Heckenbach}. The next result (and its proof) generalizes
\cite[Theorem 2.6]{BW}, \cite{Heckenbach}.
\begin{theorem}
\label{antiparallel}
Let $\M$ be an antiparallel closed
oriented matroid, and $A \subset E$ a convex set.
Then $\link_{\DP(\M)}(A)$ and $L_{\conv}(\M)_{> A}$ are homotopy equivalent
to a
$$
\begin{cases}
\text{ sphere }\sphere^{r(\M)-r(A)-1} & \text{ if }A=f^{-1}(+)\text{ for some covector }f \\
\text{ point }& \text{ otherwise.} \\
\end{cases}
$$
\end{theorem}
\begin{proof} Let $L$ be the big face lattice \cite[\S 4.1]{OMbook}
of $\M$ and $L^\circ := L \setminus \{ \hat{0}, \hat{1} \}$. The map
$$
\iota : \left\{
\begin{matrix}
L^\circ & \rightarrow & L^\circ_{conv}(\M) \\
f & \mapsto & f^{-1}(+)
\end{matrix}
\right. $$
is easily seen to be order-preserving. It is also injective, since if $\iota(f)=A$,
one can recover $f$ as follows:
\[
f(e)=
\begin{cases}
+ &\text{if }e\in A\\
- &\text{if }e\text{ is antiparallel to an element of }A\\
0 &\text{otherwise.}
\end{cases}
\]
In proving the theorem, we may assume by Lemma \ref{acyclic-link}
that we are in the case where $A=f^{-1}(+)$ for some covector $f$,
so that $\iota(f)=A$.
In this case, injectivity of $\iota$ implies that it restricts to a map from
$$
\iota: L^\circ_{> f} \rightarrow L^\circ_{conv}(\M)_{> A }.
$$
It suffices to show that this restricted $\iota$ induces a homotopy equivalence,
since $L^\circ_{> 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 \ref{quillen} to $\iota$, we must
show that for an arbitrary convex set $B$ containing $A$, the subposet
\[
\iota^{-1}(L_{conv}(\M)_{> B})=\{ f \in L^\circ: B \subsetneq f^{-1}(+) \}
\]
is contractible. But \cite[Prop. 4.3.6]{OMbook} shows that
this is the poset of non-empty interior faces of a shellable ball, and hence
is contractible.
\end{proof}
\section{Local topology of $\DF(\M)$}
\label{local-topology-2}
In this section we examine links in the complex $\DF(\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 \cite{EJ}.
Let $E$ be a finite set, and $\Li$ a collection of subsets of $E$
that contains $\emptyset$ and $E$ and is closed under intersection.
We can alternatively think of $\Li$ as a closure operator on $E$ defined by
\[
\Li(A)=\bigcap_{\{C \in \Li\,|\,C \supseteq A\}} C.
\]
We will say that $\Li$ is {\em anti-exchange} if given any set $C$ in $\Li$,
and two unequal points $p$ and $q$ in $E$, neither in $C$, one has that
\[
q \in \Li(C \cup \{p\})\quad \Rightarrow \quad p \not\in \Li(C \cup \{q\}).
\]
When $\Li$ is anti-exchange, it will be called a
{\em convex geometry}, and the subsets in $\Li$ or, equivalently, those subsets
$A$ of $E$ such that $\Li(A)=A$ will be called {\em convex sets}.
Let $\La_{\conv}(\Li)$ be the lattice of convex sets of
$\Li$ ordered by containment and $\La^\circ_{\conv}(\Li) := \La_{\conv}(\Li)
\setminus \{ \emptyset \}$. This is a meet-distributive lattice,
which is ranked by $r(A)=|A|$. Conversely, every meet-distributive
lattice is isomorphic to $\La_{\conv}(\Li)$ for some convex geometry $\Li$.
There are two ways to construct new convex geometries from $\Li$:
restriction and contraction. If $C$ is convex then let $\Li|_C$ denote the
{\it restriction} of the convex geometry $\Li$ to the ground set $C$;
that is, for $A \subset C$,
$$
\Li|_C (A) = \Li(A) \cap C.
$$
Let $\Li/C$ be the {\it contraction} defined as a closure by
\[
\Li/C(A)=\Li(C\cup A)-C
\]
for all $A \subseteq E-C$.
An element $a \in A$ with $a \not\in \Li(A-\{x\})$ is
called {\em 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)$
\cite{EJ}.
Call a convex set $C$ {\em free} if $\ex(C)=C$.
The set of free sets of a convex geometry
form a simplicial complex denoted here $\DF(\Li)$.
The following result on the topology of a meet-distributive lattice
$\La_{\conv}(\Li)$ (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.
\begin{lemma} \cite[Theorem 4.10]{EJ}
\label{convexgeomtopology}
Let $\Li$ be a convex geometry on a ground set $E$
and let $\La=\La_{\conv}(\Li)$ be its lattice
of convex sets. Then $\La^\circ$ is homeomorphic to a
\[
\begin{cases}
\text{ball }\ball^{|E|-2} & \text{ if }E \neq \ex(E) \\
\text{sphere }\sphere^{|E|-2} & \text{ if }E = \ex(E)
\end{cases} \qed
\]
\end{lemma}
\begin{proof}
Meet-distributivity implies lower-semimodularity and
hence shellability \cite[(11.10 (iv))]{Bj}. It also implies that intervals
of length 2 have either 3 or 4 elements. Consequently
$\Li$ is either a ball or sphere by \cite[Prop. 4.7.22]{OMbook} \cite[Theorem 11.4]{Bj}.
If $E = \ex(E)$ then $\La$ is a Boolean algebra of rank
$|E|$. Hence the order complex of $\La^\circ$ is the barycentric subdivision
of the boundary of an $(|E|-2)$-simplex, which is a sphere.
If $E \neq \ex(E)$ then $\La$ is not coatomic, so $\La^\circ$ must
be contractible by Lemma \ref{crosscut}, and hence a ball.
\end{proof}
Before we can analyze $\Delta_{\free}(\Li)$ in more detail we
need the following simple lemma. Recall that the {\it restriction} of a simplicial complex
$\Delta$ to a subset $A$ of the ground set is the simplicial complex
$$\Delta|_A := \{ B \in \Delta~|~B \subseteq A ~\}.$$
\begin{lemma} \label{linkres}
In any convex geometry $\Li$, if $A$ is a convex set contained in
the extreme points of $\Li$ then
\begin{enumerate}
\item[(a)]
$$\link_{\Delta_{\free}(\Li)}(A) =
\Delta_{\free}(\Li/A)
$$
\item[(b)]
$$
\Delta_{\free}(\Li)|_{E-A} = \Delta_{\free}(\Li|_{E-A})
$$
\end{enumerate}
as simplicial complexes on the ground set $E-A$.
\end{lemma}
\begin{proof}
Let $B \subset E$ be disjoint from $A$.
\noindent {(a):} By definition of contraction,
$A \cup B$ is convex in $\Li$ if and only if $B$ is convex in $\Li/A$.
Therefore
$$
\begin{aligned}
B \in \link_{\Delta_{\free}(\Li)}(A) &\Leftrightarrow
\ex_\Li(A \cup B) = A \cup B \\
&\Leftrightarrow e \not\in \Li((A \cup B) - e)
\,\, \forall e \in A \cup B \\
&\Leftrightarrow e \not\in \Li((A \cup B) - e) - A
\,\, \forall e \in B \\
&\Leftrightarrow \ex_{\Li/A}(B) = B \\
&\Leftrightarrow B \in \Delta_{\free}(\Li/A).
\end{aligned}
$$
Note that the reverse direction of the third equivalence uses the
fact that $A$ is free.
\noindent {(b):} By definition of restriction ,
$B = B \cap (E-A)$ is convex in $\Li|_{E-A}$ if
and only if $B$ is convex in $\Li$.
Note that since $A$ is a set of extreme points, we have
$e \not\in \Li(B)$ for $e \in A$.
Therefore
$$
\begin{aligned}
B \in \Delta_{\free}|_{E-A} &\Leftrightarrow
\ex_{\Li}(B) = B \\
&\Leftrightarrow e \not\in \Li(B-e) \,\, \forall e \in B \\
&\Leftrightarrow e \not\in \Li|_{E-A}(B-e) \,\, \forall e \in B \\
&\Leftrightarrow \ex_{\Li|_{E-A}}(B) = B \\
&\Leftrightarrow B \in \Delta_{\free}(\Li|_{E-A}).
\end{aligned}
$$
\end{proof}
We next review some definitions related to collapsing within
simplicial complexes; a good reference is Glaser \cite{Gla}.
A face $G$ in a simplicial
complex is called {\it free} if $G$ is not maximal
and is contained in a unique maximal face of $\Delta$ (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 $\Delta$ one calls
$\Delta[G] := \Delta - \{ F \in \Delta~:~ G \subseteq F ~\}$ an {\it elementary collapse}
of $\Delta$. A subcomplex $\Gamma$ of $\Delta$ is called a {\it collapse} of
$\Delta$ if there is a sequence $G_0 , \ldots, G_n$ such that
\begin{enumerate}
\item[$\bullet$]
$\Delta_0 = \Delta$,
\item[$\bullet$]
$\Delta_{i+1} = \Delta_i[G_i]$ is an elementary collapse
for $i=0,1,\ldots,n$.
\item[$\bullet$]
$\Delta_{n+1} = \Gamma$.
\end{enumerate}
If $\Gamma = \emptyset$ is a collapse of $\Delta$ then $\Delta$ is called
{\it collapsible}. By \cite{Gla}, if $\Gamma \neq \emptyset$ is a collapse of $\Delta$ then
$\Gamma$ is a strong deformation retract of $\Delta$. In particular, if $\Delta \neq \emptyset$
is collapsible then $\Delta$ is contractible. There is a particularly nice
sufficient condition for collapsibility known as
{\it non-evasiveness} (see \cite{KSS}):
a simplicial complex $\Delta$ on ground set $V$ is called non-evasive if either
$|V|=1$ and $\Delta$ is a single vertex,
or there is a $v \in V$ such that $\link_\Delta(v)$
and $\Delta|_{V-v}$ are both non-evasive on the ground set $V \setminus v$.
\begin{theorem}
\label{l:convexfree}
Let $\Li$ be a convex geometry
on ground set $E$, $A$ a convex set of extreme points and $\DF$ its simplicial complex of free sets.
Then $\link_{\DF}(A)$ is non-evasive, and hence collapsible and contractible.
\end{theorem}
\begin{proof}
By Lemma \ref{linkres} we know that
$\link_{\DF}(A) = \DF(\Li/A)$. Hence we may assume $A = \emptyset$,
and we need only show that $\DF$ itself is non-evasive.
If $\ex(E)=E$, then $\DF$ is a simplex and
there is nothing to prove. For an extreme point $e \in E$ we have by Lemma \ref{linkres}
that
$\link_{\DF}(e) = \DF(\Li/e)$ and $\DF|_{E-e} = \DF(\Li|_{E - e})$. Thus by induction
on the cardinality of the ground set it follows that $\link_{\DF}(e)$ and
$\DF|_{E-e}$ are non-evasive.
\end{proof}
%The next lemma deals with the topology of links of certain faces in
%$\DF(\Li)$ and will later be used to deal with the case of links of
%vertices in $\DF(\M)$.
\begin{corollary}\label{c:extreme}
If $\M$ is an acyclic oriented matroid and $A \subset \ex(\M)$
is convex, then $\link_{\DF(\M)}(A)$ is collapsible and hence contractible. \qed
\end{corollary}
We will need the following topological fact in the proof Theorem~\ref{contraction-link}.
Call a face $F$ of a simplicial complex $\Delta$ {\em exposed} if
$\link_\Delta(F)$ is collapsible. Define
the {\it deletion} and {\it star} of $F$ in $\Delta$ as follows:
$$
\begin{aligned}
\del_\Delta(F):& = \{ G \in \Delta ~:~ G \not\supseteq F ~\} \\
\str_\Delta(F):& = \{ G \in \Delta ~:~ G \cup F \in \Delta ~\}
\end{aligned}
$$
\begin{proposition}\label{l:exp} If $F$ is an exposed face in $\Delta$ then
$\del_\Delta(F)$ is a collapse of $\Delta$.
\end{proposition}
\begin{proof}
Let $G_0, \ldots, G_n$ be a sequence of faces of $\link_\Delta(F)$ such that
$\Gamma_0 = \link_\Delta(F)$, $\Gamma_{i+1} = \Gamma_i[G_{i}]$ is an
elementary collapse, and $\Gamma_{n+1} = \emptyset$.
Then $G_0 \cup F, \ldots, G_n \cup F$ is a sequence of faces of $\Delta$ such
that $\Gamma_0' = \Delta$, $\Gamma_{i+1}' = \Gamma_i'[G_{i} \cup F]$,
is an elementary collapse, and $\Gamma_{n+1}' = \del_\Delta(F)$.
\end{proof}
\vskip .2in
We now return to the discussion of links of vertices
in $\DF(\M)$ for a simple oriented matroid $\M$.
Our immediate goal is to compare $\link_{\DF(\M)}(e)$ with $\DF(\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 $\C$
of $\M/e$ there is a unique element $e_\C$ such that $\{ e, e_\C \}$ 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_\C$, where $\C$ runs through the non-loop paralellism
classes of $\M/e$.
One can check that $\link_{\DF}(e)$, which by definition is a simplicial
complex over the ground set $E - e$, in fact only contains simplices
from $E_{\Simp(\M/e)}$.
\begin{proposition}
\label{quotient-observations}
If $A \subset E_{\Simp(\M/e)}$ is convex in $\Simp(\M/e)$ then
\begin{enumerate}
\item[(a)] $A$ is convex in $\M$,
\item[(b)] $A+e$ is convex in $\M$, and
\item[(c)] $\ex_{\Simp(\M/e)}(A) + e \subset \ex_\M(A+e).$
\end{enumerate}
\end{proposition}
\begin{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' \neq 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' \in \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 \circ h$ of $\M$,
guaranteed to exist by the perturbation axiom
\cite[Axiom L2]{OMbook}, will be identically $+$ on $A$ since $g$ was,
and have $(g \circ h)(e)=+$. The property assumed for $e'$
implies $(g \circ 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)$.
\end{proof}
It immediately follows from
Proposition \ref{quotient-observations} that
$\DF(\Simp(\M/e))$ is a subcomplex of $\link_{\DF(\M)}(e)$.
We can now recall and prove Theorem \ref{contraction-link}
from the introduction.
\vskip .1in
\noindent
{\bf Theorem \ref{contraction-link}}.
{\it
$\link_{\DF(\M)}(e)$ is a collapse (and hence a strong deformation retract)
of $\DF(\Simp(\M/e))$ .
}
\begin{proof} Call a subset $A$ in
$\link_{\DF(\M)}(e)- \DF(\Simp(\M/e))$ {\em unwanted}.
Our strategy will be to collapse away the unwanted faces from $\link_{\DF(\M)}(e)$
in stages.
To be more precise, let $\Delta_0:=\link_{\DF(\M)}(e)$. Having
defined $\Delta_{i-1}$, let $A_i$ be an unwanted face in $\Delta_{i-1}$
with ${\bar A_i}:=\conv_{\Simp(\M/e)}(A_i)$ of maximum cardinality.
Then let $F_i:=\ex_{\Simp(\M/e)}(A_i)$, and define $\Delta_i:=\del_{\Delta_{i-1}}(F_i)$.
We claim that $F_i$ is an unwanted face of $\Delta_i$. If not, then
$F_i$ is an element of $\DF(\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) = {\bar A_i} \supset A_i,
$$
contradicting the fact that $A_i$ is unwanted.
We claim further that $F_i$ is always an exposed face in $\Delta_{i-1}$,
which would complete the proof via Lemma~\ref{l:exp}.
To prove this claim, we must show that $\link_{\Delta_{i-1}}(F_i)$
is collapsible . Let $\M'$ denote the restriction $\M|_{{\bar A_i}+e}$
of the matroid $\M$ to the subset ${\bar A_i}+e$.
Collapsibility of $\link_{\Delta_{i-1}}(F_i)$ follows from
Corollary ~\ref{c:extreme} and the following
three subclaims:
\vskip .2in
\noindent
{\sf Subclaim 1:}
$\link_{\Delta_{i-1}}(F_i) = \link_{\DF(\M')}(F_i+e)$.
\noindent
{\sf Subclaim 2:}
$\M'$ is acyclically oriented (so that it gives rise to a convex geometry).
\noindent
{\sf Subclaim 3:}
$F+e \subset \ex_{\M'}({\bar A_i}+e) \ (= \ex(\M'))$.
\vskip .2in
Subclaims 2 and 3 are easy. To see Subclaim 2,
note that ${\bar A_i}$ is convex in $\Simp(\M/e)$ by definition,
implying ${\bar A_i}+e$ is convex in $\M$ by
Proposition~\ref{quotient-observations} part (b). Hence
${\bar A_i}+e$ is acyclic in $\M$.
To see Subclaim 3, note that the extreme elements of ${\bar A_i}+e$
in $\M'$ are the same as its extreme elements in $\M$, since
we've already seen that ${\bar A_i}+e$ is convex in $\M$.
Then $F_i+e \subset \ex_{\M}({\bar A_i}+e)$ by
Proposition~\ref{quotient-observations} 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 \cap ( F_i+e) = \emptyset$
and $F \cup F_i + e$ is free in $\M'=\M|_{{\bar A_i}+e}$.
Since ${\bar A_i}+e$ is convex, this implies
$F \cup 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 \cap F_i = \emptyset$ and $F \cup F_i \in \Delta_{i-1}$.
Note that $F \cup F_i$ is unwanted since $F_i$ is. Then
$$
{\bar A_i} = \conv_{\Simp(\M/e)}(A_i)
= \conv_{\Simp(\M/e)}(F_i) \subset \conv_{\Simp(\M/e)}(F \cup F_i)
$$
implies that the last inclusion must actually be an equality, otherwise
we would contradict the maximality of ${\bar A_i}$. Thus
$F \cup F_i \subset {\bar A_i}$. To show that $F$ lies in the
right-hand side, we must show $F \cup F_i + e$ is free in
$\M'=\M|_{{\bar A_i}+e}$. We know that $F \cup F_i + e$ is free in $\M$ since
$$
F \in \link_{\Delta_{i-1}}(F_i)
\subset \link_{\Delta_{0}}(F_i)
= \link_{\DF(\M)}(F_i+e).
$$
Therefore $F \cup F_i + e$ is also free in $\M'$.
\end{proof}
\section{Application: counting interior elements}
\label{application-section}
The goal of this section is Theorem~\ref{application} below.
As mentioned earlier, in the case of
a realizable acyclically oriented matroid, this result was conjectured in \cite{AGM},
and proven in \cite{ER} and \cite{Kl}. Aside from the fact that
Theorem~\ref{application} generalizes the main result of \cite{ER},
the proof below simplifies conceptually the topological proof given there.
Say that an element $e \in E$ is {\it 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,
{\it every} element $e$ in $E$ is interior.
The definition of interior elements together with Theorems~\ref{main}
and \ref{contraction-link} immediately imply
\begin{corollary}
\label{interior-significance}
For any $e$ in $E$, we have that $\link_{\DF(\M)}(e)$ is homotopy equivalent to a
$$
\begin{cases}
\text{ sphere }\sphere^{r(\M)-2} &\text{ if }e\text{ is interior}\\
\text{ point } &\text{ otherwise.}
\end{cases}
$$
\end{corollary}
Define the $\beta$ invariant of $\M$ by
$$
\beta(L_{\conv}(\M)):=\sum_{A \in L_{\conv}(\M)}
\mu(\hat{0},A) \,\, \rank_{L_{\conv}(\M)}(A)
$$
where $\mu(-,-)$ denotes the M\"obius function in $L_{\conv}(\M)$.
\begin{theorem}
\label{application}
For any oriented matroid $\M$,
$$
\beta(L_{\conv}(\M))=(-1)^{r(\M)-1} \#\{\text{interior elements }e\text{ in }E\}.
$$
\end{theorem}
\begin{proof}
For a convex set $A$, the interval $[\hat{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
$$
\begin{aligned}
\beta(L_{\conv}(\M))
&:=\sum_{A \in L_{\conv}(\M)} \mu(\hat{0},A) \,\, \rank_{L_{\conv}(\M)}(A)\\
& = \sum_{\text{ free }A \subseteq E} (-1)^{|A|} |A| \\
& = \sum_{e \in E} \sum_{\substack{A \text{ free }\\ e \in A}} (-1)^{|A|} \\
& = \sum_{e \in E} -\tilde{\chi}( \link_{\Delta_{\free}(\M)}(e) )
\end{aligned}
$$
where here $\tilde{\chi}$ denotes reduced Euler characteristic.
The result then follows from Corollary~\ref{interior-significance},
since $\tilde{\chi}$ is a homotopy invariant that vanishes for a point, and
satisfies $\tilde{\chi}(\sphere^r) = (-1)^r.$
\end{proof}
%\section{Appendix: complements of cells in the
%Folkman-Lawrence sphere}
%
%The goal of this appendix is to supply the missing fact from
%the proof of Theorem~\ref{main}, namely that removing the closure
%of a cell from a shellable regular CW-sphere $\sphere^{r}$
%leaves a contractible set.
%
%To this end, we begin with
%a well-known fact about removing such cells that is immediate from
%\cite[Lemma 4.7.27]{OMbook}
%\begin{lemma}
%If $L$ is the face poset of a regular cell complex $X$,
%and $y$ is an element of $L$ corresponding to a closed cell $\sigma$, then
%$\Delta(L - L_{\leq y})$ is a strong deformation retract of $X-\sigma$.\qed
%\end{lemma}
%
%We next recall a few facts from \cite[Chapter 4]{OMbook} about the Folkman-Lawrence
%cell decomposition. It is a shellable regular cell decomposition
%\cite[Theorem 4.3.3]{OMbook} whose face poset is a lattice, the {\em big face lattice},
%$\mathcal F_{big}(\M)$. Moreover, every principal
%ideal in this poset is isomorphic to the face lattice of a shellable regular
%cell decomposition of a sphere, the {\em Edmonds-Mandel lattice}
%$\mathcal F_{em}(\M)$ \cite[Theorem 4.3.5]{OMbook}. Because these cell decompositions are both shellable, the face lattices admit a recursive
%coatom ordering \cite[Lemma 4.7.18]{OMbook}.
%
%\begin{lemma}\label{shellfact} Let $L$ be either $\mathcal F_{big}(\M)$ or $\mathcal F_{em}(\M)$
%and $y \in L$. Then there is recursive coatom ordering of $L$ that
%has those coatoms whose meet with $y$ is bigger than $\hat 0$ appearing
%last.
%\end{lemma}
%\begin{proof} Let us suppose that $L=\mathcal F_{big}(\M)$. By appropriate
%reorientation of $\M$ we may assume that there is a tope $B$ with only positive
%entries and that the face $y$ corresponds to a non-negative covector. The coatoms of $\mathcal F_{big}(\M)$ which have a meet
%greater than $\hat 0$ with $y$ correspond to topes (maximal covectors)
%that have at least one
%$+$ entry in the same coordinate as the covector $y$. This set of
%topes forms an order ideal in the tope poset $\mathcal T(\M,B)$ and hence
%forms an initial segment of a shelling \cite[Prop. 4.3.2]{OMbook}.
%Since the reverse of a shelling order of a sphere is also a shelling order,
%this part of the theorem follows. Applying the construction of \cite[Prop. 4.3.1]{OMbook} to the case of $L=\mathcal F_{em}(\M)$
%gives the result in this case.
%\end{proof}
%
%In what follows, $\overline{L}$ denotes the proper part $L-\{\hat{1},\hat{0}\}$
%of a lattice $L$.
%
%\begin{lemma}\label{spherefact} Let $\sphere$ be a regular $CW$-sphere with
%face poset $L$ which is a lattice. Suppose that for every pair of elements
%$\hat 0 < y < x \leq \hat 1$ in $L$ there exists a CL-shelling of $L_{\leq x}$ having the coatoms
%whose meet with $y$ is greater than $\hat 0$ appear last in the shelling order.
%
%Then $\Delta(\bar L -L_{\leq y})$ is contractible for all $y \in \bar L$.
%\end{lemma}
%
%\begin{proof} Induct on the rank of $L$.
%The lemma clearly is true if $L$ has rank $2$. Suppose that the
%rank of $L$ is $n$. If $y$ has corank $1$, i.e., if $y$ is itself a coatom,
%we can apply \cite[Lemma 4.7.28]{OMbook} to show that $\bar L - L_{\leq y}$
%is contractible.
%
% Suppose that $y$ has rank $k$, $k \leq n-2$ and let $x$ be a coatom of $L$.
%Let
%\[
%L'= \left( \bar L - L_{\leq y} \right) \cap L_{\leq x}
%= \bar L_{\leq x} - L_{ \leq x \wedge y}.
%\]
%By induction $L'$ is
%contractible, and hence $\bar L - L_{\leq y} -\{x\}$ has
%the same homotopy type as $\bar L - L_{\leq y}$ by the Fiber Lemma \ref{quillen}.
% We can continue in this manner, removing elements $x$
%such that $x \wedge y > \hat 0$ in reverse order of their rank until we have shown that $\bar L - L_{\leq y}$ has the same homotopy type as
%\[
%\bar L - \{ z\ |\ z \wedge y \geq \hat 0\}=\{z \in \bar L\,|\, z \leq x',\ x' \wedge y= \hat 0\}.
%\]
%
%Since the set of coatoms $\{ x\,|\, x\wedge y > \hat 0\}$ appear last in
%shelling order, the set $\{z \in \bar L\,|\, z \leq x',\ x' \wedge y= \hat 0\}$
%is the set of faces that appear in an initial, but incomplete, shelling
%order. This is homeomorphic to a ball by \cite[Prop. 4.7.26 (ii)]{OMbook},
%which finishes the induction.
%\end{proof}
%
%Combining these three lemmas completes the proof of Theorem~\ref{main}.
%
%
%
%%{\bf Should we include a remark about how Lemma~\ref{spherefact} corresponds
%%to a dual Edelman-Walker result?}
%
%
\section{Acknowledgement}
The authors thank Lou Billera for asking a question that
led to this work, and Xun Dong for suggesting
the use of Lemma \ref{xdong} 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.
\newcommand{\journalname}[1]{\textit{#1}}
\newcommand{\booktitle}[1]{\textit{#1}}
\begin{thebibliography}{20}
\bibitem{AGM}
C. Ahrens, G. Gordon and E. McMahon,
Convexity and the beta invariant,
\journalname{Discrete Comput. Geom.} \textbf{22} (1999), 411--424.
\bibitem{Bj}
A. Bj\"orner,
Topological methods, in
\booktitle{Handbook of Combinatorics} (R. Graham, M.
Gr\"otschel, and L. Lov\'asz, eds.),
North Holland, Amsterdam, 1995, pp. 1819--1872.
\bibitem{BW}
A. Bj\"orner and V. Welker,
Complexes of directed graphs,
\journalname{SIAM J. Discrete Math.} 12 (1999), 413--424 (electronic).
\bibitem{OMbook}
A.~Bj\"orner, M.~Las Vergnas, B.~Sturmfels, N.~White and G.M.~Ziegler,
\booktitle{Oriented matroids},
Encyclopedia of Mathematics \textbf{46},
Cambridge University Press, Cambridge, 1993.
\bibitem{BO}
T. Brylawski and J. Oxley,
The Tutte polynomial and its applications,
in \booktitle{Matroid applications}, Encyclopedia Math. Appl. \textbf{40},
pp. 123--225, Cambridge University Press, Cambridge, 1992.
\bibitem{xdong}
X. Dong,
Alexander duality for projections of polytopes,
preprint, 2000 (available at {\tt www.math.umn.edu/$\tilde{~}$xdong}).
\bibitem{Ed1}
P. H. Edelman,
The lattice of convex sets of an oriented matroid,
\journalname{J. Combin. Theory Ser. B} \textbf{33} (1982), 239--244.
\bibitem{Ed2}
P. H. Edelman,
The acyclic sets of an oriented matroid,
\journalname{J. Combin. Theory Ser. B} \textbf{36} (1984), 26--31.
\bibitem{EJ}
P.H. Edelman and R. Jamison,
The theory of convex geometries,
\journalname{Geom. Dedicata} \textbf{19} (1985), 247--270.
\bibitem{ER}
P.H. Edelman and V. Reiner,
Counting the interior points of a point configuration,
\journalname{Discrete and Comput. Geom.} \textbf{23} (2000), 1--13.
\bibitem{Et}
G. Etienne,
On the M\"obius algebra of geometric lattices,
\journalname{Europ. J. Combin.} \textbf{19} (1998), 921--933.
\bibitem{Gla}
L.C. Glaser,
\booktitle{Combinatorial Geometry Theory I},
van Nostrand, New York, 1970.
\bibitem{Heckenbach}
F. Heckenbach, Doctoral Thesis, Universit\"at Erlangen, in preparation.
\bibitem{Humphreys}
J. E. Humphreys,
\booktitle{Reflection groups and Coxeter groups},
Cambridge Studies in Advanced Mathematics \textbf{29},
Cambridge University Press, Cambridge, 1990.
\bibitem{KSS}
J. Kahn, M. Saks and D. Sturtevant,
A topological approach to evasiveness,
\journalname{Combinatorica} \textbf{4} (1984), 297--306.
\bibitem{Kl}
D. Klain,
An Euler relation for valuations on polytopes,
\journalname{Adv. Math.} \textbf{147} (1999), 1--34.
\bibitem{KRS}
W. Kook, V. Reiner, D. Stanton,
A convolution formula for the Tutte polynomial,
\journalname{J. Combin. Theory Ser. B} \textbf{76} (1999), 297-299.
\bibitem{LV}
M. Las Vergnas,
Convexity in oriented matroids,
\journalname{J. Combin. Theory Ser. B} \textbf{29} (1980), 231--243.
\bibitem{Re1}
V. Reiner,
Quotients of Coxeter complexes and P-partitions,
Ph.D. thesis, MIT, 1990.
\bibitem{Re2}
V. Reiner,
Signed posets,
\journalname{J. Combin. Theory Ser. A}
\textbf{62} (1993), 324--360.
\bibitem{WW}
M. Wachs and J.W. Walker,
On geometric semilattices,
\journalname{Order} \textbf{2} (1986), 367--385.
\end{thebibliography}
\end{document}