\documentclass{amsart}
\usepackage{amsmath, amssymb, amsthm}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}
\newcommand{\etal}{{\em et. al. }}
\newcommand{\D}{\Delta}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\conv}{\mathrm{conv}}
\newcommand{\inte}{\mathrm{int}}
\newcommand{\relint}{\mathrm{relint}}
\newcommand{\bdy}{\mathrm{bdy}}
\newcommand{\aff}{\mathrm{aff}}
\newcommand{\La}{\mathbf{L}}
\newcommand{\ex}{\mathrm{ex}}
\newcommand{\Free}{\mathrm{Free}}
\newcommand{\lk}{\mathrm{lk}}
\newcommand{\del}{\mathrm{del}}
\newcommand{\st}{\mathrm{st}}
\newcommand{\Po}{\mathbf{P}}
\newcommand{\Li}{\mathcal L}

\begin{document}

\title{Counting the interior points of a point configuration}
\author{Paul H. Edelman}
\address{School of Mathematics\\
University of Minnesota\\
Minneapolis, MN 55455 USA}
\email[P. H. Edelman]{edelman@math.umn.edu}
\author{Victor Reiner}
\email[V. Reiner]{reiner@math.umn.edu}
\thanks{The second author was partially supported by a  Sloan Foundation Fellowship and a University of Minnesota McKnight-Land Grant Fellowship}
\begin{abstract} We prove a formula
conjectured by Ahrens, Gordon, and McMahon for the number of
interior points for a point configuration in $\R^d$.
Our method is to show that the formula can be interpreted as
a sum of Euler characteristics of certain complexes associated with
the point configuration, and then compute the homology of these
complexes.
This method extends to other examples of convex geometries.
We sketch these applications, replicating an earlier result
of Gordon, and proving a new result related to ordered sets.
\end{abstract}
\maketitle

\section{Introduction}\label{S:intro} Let $\A$ be a collection of
points in $\R^d$ whose affine span is all of $\R^d$.  Let
$\inte(\A)$ be the set of points of $\A$ that lie in the interior of
its convex hull, $\conv(\A)$. Call a subset $K$ of $\A$ {\em free} if 
$\conv(K)\cap \A=K$ and the set of vertices of $\conv(K)$ is equal to $K$.
In a recent paper Ahrens, Gordon
and McMahon \cite[Conjecture 4.1]{AGM} conjectured the following
beautiful formula for $|\inte(\A)|$, and proved it for point
configurations $\A$ in $\R^2$:
\begin{theorem}
\label{t:main}
\begin{equation*}
|\inte(\A)|=(-1)^{(d-1)}\sum_{K \mathrm{ free }}(-1)^{|K|}|K|.
\end{equation*}
\end{theorem}
\noindent
We prove this formula in its full generality in Section \ref{s:main}.  D.
Klain \cite[Proposition 6.3]{Kl} has recently proven this formula independently.

  The work of Ahrens, \etal  is part of a larger project of extending matroid invariants to greedoids \cite{GM1,GM2}. Recent work has focused on
generalizing Crapo's $\beta$ invariant, originally defined for matroids
\cite{Cr}, to the more general structure of a greedoid \cite{Go}.
In the special case of greedoids which are convex geometries, the definition of the $\beta$ invariant reduces to essentially the right-hand side of Theorem~\ref{t:main}
\cite{Go}.   Theorem~\ref{t:main} gives a combinatorial interpretation
to the $\beta$ invariant of those convex geometries which are based on Euclidean
point configurations. Given this background, it is not surprising that
Ahrens, \etal use deletion-contraction arguments to establish their
formula for $d=2$.

   Our point of view is more in the tradition of a topological approach to matroid theory \cite{Bj2}, as we now explain.  One can rewrite
the right-hand side in Theorem~\ref{t:main} as follows:
$$
\begin{aligned}
(-1)^{(d-1)}\sum_{K \mathrm{ free }}(-1)^{|K|}|K| 
& = (-1)^{(d-1)}\sum_{K \mathrm{ free }} \sum_{a \in K} (-1)^{|K|} \\
%& = (-1)^{(d-1)}\sum_{a \in \A} \sum_{K \mathrm{ free }}  (-1)^{|K|} \\%
& = (-1)^{(d-1)}\sum_{a \in \A} \widetilde{\chi}_a\
\end{aligned}
$$
where
$$
\widetilde{\chi}_a = \sum_{K\  \mathrm{ free }, \, a \in K}  (-1)^{|K|}.
$$
We will prove Theorem \ref{t:main} by showing 
(see Lemmata~\ref{l:boundary},\ref{l:interior})
that
$$
\widetilde{\chi}_a =
\left\{
\begin{matrix}
(-1)^{d-1} & \text{ if } a \in \inte(\A) \\
0 & \text{ otherwise. }
\end{matrix}
\right.
$$
The latter computation is achieved by interpreting $\widetilde{\chi}_a$
as the reduced Euler characteristic of a certain simplicial complex
(the {\it link} of $a$ in the simplicial complex of free
sets of $\A$), and then analyzing the topology of these complexes. In
contrast, Klain
\cite{Kl}
computes these Euler characteristics directly using valuation theory
for polytopes.
 

  The paper is organized as follows.  In the next section we establish
some general facts from combinatorial topology and polytope theory
necessary for the proof.  In Section~\ref{s:main} we 
prove Theorem \ref{t:main}.
Section~\ref{s:convexgeometry} uses similar techniques to evaluate
the generalized $\beta$ invariant for other convex geometries.
Section~\ref{s:open} discusses some open problems. 

   

  

     
\section{Preliminaries}\label{S:prelim}  In this section we
establish some background results from topological combinatorics 
that will be used throughout the paper.  For much of this material
an excellent reference is \cite{Bj}.

  Let $\D$ be an abstract simplicial complex on the finite ground set $X$.
That is, $\D$ is a collection of  subsets of $X$, called {\em simplices},
with the property that  
\[
 \sigma \subseteq \tau \in \D
\]
implies that $\sigma \in \D$.  For $-1 \leq i \leq |X|-1$ let
$f_i$ be the number of {\em $i$-dimensional faces of } $\D$, i.e.,
\[
f_i =|\{\sigma \in \D\,:\, |\sigma|=i+1\}|.
\]
 For any $x \in X$, we define three associated
subcomplexes, the {\em link of $x$ in $\D$},  the {\em star of $x$ in $\D$},
and the {\em deletion of $x$ in $\D$} by
\[
\begin{aligned}
\lk_\D(x) &=\{\sigma-x\,|\, x \in \sigma \in \D\,\} \\
\st_\D(x) &= \{\sigma \in \D\,|\,\{x\} \cup \sigma \in \D\,\} \\
\del_\D(x) &=\{\sigma\in \D\,|\,x \not\in \sigma\,\}. 
\end{aligned}
\]
It is clear from the definitions that 
\begin{equation}
 \st_\D(x) \cup \del_\D(x) = \D\label{union}
\end{equation}
and
\begin{equation} 
\del_\D(x) \cap  \st_\D(x) = \mathrm{\lk}_\D(x).\label{inter}
\end{equation}

  For a given simplicial complex $\D$, let $\widetilde{H}_i(\D)=\widetilde{H}_i(\D, \mathbb Z)$ be
the reduced homology groups of $\D$ with coefficients in $\mathbb Z$,
for $i \geq 0$.  By the universal coefficient theorem 
\cite[Section 55]{Mu}, $\widetilde{H}_\cdot(\D)$ determines the homology
of $\D$ with any other constant coefficients.  The {\em reduced Euler characteristic}
$\widetilde{\chi}(\D)$ is defined by 
\[
\widetilde{\chi}(\D)= \sum_{i \geq -1}(-1)^i\,f_i=\sum_{i \geq 0}(-1)^i\,\mathrm{dim}_{\mathbb Q}\,\widetilde{H}_i(\D, \mathbb Q).
\]
where we note that $f_{-1}=1$.

 The following lemma
will be necessary in what follows

\begin{lemma}\label{l:linkdel}Let $\D$ be a contractible simplicial complex on 
the ground set $X$ and $x \in X$. For all  $i \geq 0$  
\[
\widetilde{H}_i(\lk_\D(x))\cong\widetilde{H}_i(\del_\D(x)).
\]
Consequently 
\begin{align*}
\widetilde{\chi}(\lk_\D(x))&= \widetilde{\chi}(\del_\D(x))\\
&=\sum_{x \in \sigma \in \D}(-1)^{|\sigma|}.
\end{align*}
\end{lemma}

\begin{proof} Associated to (\ref{union}) and (\ref{inter})
is a Mayer-Vietoris exact sequence \cite[Theorem 25.1]{Mu} 
\[
\cdots \to \widetilde{H}_{i+1}(\D) \to \widetilde{H}_i(\lk_\D(x)) \to \widetilde{H}_i(\del_\D(x)) \oplus \widetilde{H}_i(\st_\D(x)) \to \widetilde{H}_i(\D) \to \cdots
\]
Note that both $\D$ and $\st_\D(x)$ are contractible, the former by
hypothesis and the latter since $\st_\D(x)$ is a cone.  Therefore
the above sequence reduces to 
\[
\cdots \to 0 \to 
\widetilde{H}_i(\lk_\D(x)) \to \widetilde{H}_i(\del_\D(x)) 
\to 0 \to \cdots
\]
which proves the first assertion.  The next equation follows immediately
and the last equation is immediate from the definition of the reduced Euler characteristic. 
\end{proof}



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

\begin{lemma}\label{l:Quillen}  Suppose $Q$ and $P$ are posets and 
$f: Q \to P$ is an order-preserving map.
If for all $x \in P$ the fibers $f^{-1}(P_{\leq x})$ are contractible then $f$ induces a homotopy equivalence between $Q$ and $P$.
\end{lemma}

\begin{lemma}\label{l:closure} Let $f: P \to P$ be an order-preserving map such that
$f(x) \geq x$ for all $x \in P$.  Then $f$ induces a homotopy equivalence
between $P$ and $f(P)$.
\end{lemma}

\begin{remark}\label{r:warning}\rm  In our applications  of Lemma~\ref{l:Quillen}, we will often let $Q$ be a simplicial
complex $\D$ viewed as a partially ordered set, where the partial order on the
simplices is by containment.  The conclusions drawn will technically be
about the order complex of  this poset, which is the 
{\it barycentric subdivision} $\mathrm{sd}(\D)$ of $\D$.
However, it is well-known \cite[Section 15]{Mu} that $\mathrm{sd}(\D)$ is 
homeomorphic to $\D$, so the same conclusions can be drawn about $\D$.
\end{remark}

  The last general facts that we will employ concern {\em Gale transforms}
of point configurations.  Let $\A=\{a_1,\dots,a_n\} \subseteq \mathbb R^d$ be
a collection of points whose affine span is all of $\mathbb R^d$  and let $\conv(\A)$ denote the
polytope which is the convex hull of $\A$.  
List $a_1,\dots,a_n$ as columns of a matrix
and append a row of ones to obtain the $(d+1) \times n$ matrix $M_\A$.
The null space of $M_\A$ is the set of all affine dependencies among the
points in $\A$, i.e., vectors $(\lambda_1,\dots,\lambda_n)$ such that
$\sum_{i=1}^n \lambda_i\,a_i=0$ and $\sum_{i=1}^n \lambda_i=0$.  Let
$A^*$ be an $(n-d-1) \times n$ matrix whose rows form a basis for this
space and denote its columns by ${v_1}^*,\dots,{v_n}^*$. This
collection ${\A}^*$ of points in $\mathbb R^{n-d-1}$ is a {\em Gale transform}
of $\A$.  The correspondence between $v_i$ and ${v_i}^*$ extends naturally
to subsets of $\A$ and ${\A}^*$.  For any subset $B \subseteq \A$,
denote by $\aff(B)$ the affine span of $B$.  The principal property of Gale
transforms is

\begin{lemma}\label{l:Gale}\cite[Section 5.5]{Gr}
Let $F$ be a proper subset of $\A$.  Then
$$
\aff(F) \cap \conv(\A-F)=\varnothing
$$
if and only if
$$
0 \in \relint( \conv{(\A - F)}^* ).
$$
That is, $F$ is exactly the set of
points of $\A$ that lie on a face of $\conv(\A)$  if and only if
${(\A-F)}^*$ has $0$ in its relative interior. 
\end{lemma}

     One should observe that any set of $n$ points
in $\mathbb R^{n-d-1}$ that has $0$ in its relative interior is the Gale
transform of some set of $n$ points in $\mathbb R^d$.  For an interesting 
survey of the uses of Gale transforms, see \cite{BL}.

\begin{lemma}\label{l:nonface} Let $\A$ be a point configuration in $\R^d$, 
$\Po=\conv(\A)$, and $\A^*$ its Gale transform.  Let
$N$ be the poset of proper subsets $A$ of  $\A^*$, ordered by containment,
such that
\[
0 \not\in \relint(\conv(A)).
\]
Then $N$ has the same integral homology as the $(n-d-2)$-sphere,
and hence
$$
\widetilde{\chi}(N)=(-1)^{n-d-2}.
$$
\end{lemma}

\begin{proof}  Let $2^{\A^*}$ be the collection of all subsets of $\A^*$.
Considering its proper part $\overline{2^{\A^*}}$ as partially ordered by inclusion,
its order complex is the barycentric subdivision of the boundary of an
$(n-1)$-simplex, and hence is homeomorphic to an $(n-2)$-sphere.
Lemma~\ref{l:Gale} implies that $2^{\A^*}-N$ is isomorphic as
a poset to the opposite of the face lattice of $\Po$.  Thus the
order complex of $\overline{2^{\A^*}-N}$ is the barycentric
subdivision of the boundary complex of $\Po$, and hence is
homeomorphic to a $(d-1)$-sphere.
It follows from \cite[Lemma 4.7.27]{BLSWZ}
that $N$ is a deformation retract of the space $\overline{2^{\A^*}-N}$, which
is to say the complement of a $(d-1)$-sphere in an $(n-2)$-sphere.  It then
follows from Alexander duality \cite[Theorem 71.1]{Mu} that $N$ has the
homology of an $(n-d-2)$-sphere.
\end{proof}

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


\section{Proof of Theorem \ref{t:main}}\label{s:main}
In this section we
prove the conjecture of Ahrens, {\em et. al.}.  Our discussion in this
section will
be only in terms of the geometric structure of point configurations
in $\R^d$, although there are natural generalizations to the more
abstract situation of convex geometries.  We take up those more 
general questions in the next section.

  Let $\A= \{a_1,\dots,a_n\}$ be a point configuration in $\R^d$.
Given a subset $A$ of $\A$ we define the {\em closure of A}, $A^c$, to
be
\[
A^c= \conv(A) \cap \A.
\]
It is clear that this is a true closure operator on the subsets of $\A$,
that is, it is idempotent, inclusion-preserving, and $A \subseteq A^c$.
The closed sets under this operator will be called {\em the convex sets of}
$\A$.  Let $\La=\La(\A)$ be the lattice of convex sets of $\A$ ordered by
inclusion and $\overline{\La}$ its {\em proper part}, that is,
$\overline{\La}=\La-\{ \varnothing, \A\}$.


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

\begin{lemma}\label{l:lattice} Let $\A$ be a point configuration and $\La(\A)$ be its
lattice of convex sets.  Then $\overline{\La}$ triangulates an 
$$
\left\{ 
\begin{matrix}
(|\A|-2)-\text{ ball } & \text{ if }\A \neq \ex(\A) \\
(|\A|-2)-\text{ sphere } & \text{ if }\A = \ex(\A) 
\end{matrix}
\right.
$$
\end{lemma}
\begin{proof} This follows from \cite[Theorem 4.10]{EJ}, but for the sake of 
completeness we sketch the proof here.  In the case where $\A = \ex(\A)$, note
that   $\La$ is a Boolean algebra on the set $\A$ whose proper part has order
complex equal to the barycentric subdivision of an $(|\A|-1)$-simplex, i.e., it
 triangulates an $(|\A|-2)-\text{ sphere }$.

   If $\A \neq \ex(\A)$  the meet of the coatoms of $\La$  is
the convex set $\A-\ex(\A)$ which lies in $\overline{\La}$.  It follows
from \cite[Crosscut Theorem (10.8)]{Bj} that $\overline{\La}$ is contractible.   

\end{proof}

\begin{lemma}\label{l:free} Let $\A$ be a point configuration 
and $\Free$ its simplicial complex of free sets.  Then $\Free$ is
contractible.
\end{lemma}

\begin{proof}  If $\ex(\A)=\A$, then $\Free$ is just a simplex and
hence is contractible.  Thus, we may assume that $\ex(\A) \neq \A$,
so that the inclusion map $\iota$ is a map from $\Free$ to $\overline{\La}$.
We wish to apply Lemma~\ref{l:Quillen} treating the
simplicial complex $\Free$ as its poset of faces as discussed in Remark~\ref{r:warning}.  We then need to analyze the structure of the fibers
$\iota^{-1}(\La_{\leq C})$ for each $C \in \overline\La$.
It is easy to check that $\iota^{-1}(L_{\leq C})=\Free(C)$ (where here $C$ is
considered as a point configuration), and hence is contractible by induction
on the number of points.
Hence, by Lemma~\ref{l:Quillen}, $\Free$ has the same homotopy type as $\overline{\La}$. By Lemma~\ref{l:lattice}, $\overline{\La}$ is contractible
if $\A \neq \ex(\A)$, and so the lemma is proven.

\end{proof}

 Let
\[
\beta(\A)=\sum_{K \in \Free}(-1)^{|K|}|K|.
\]
Our definition of $\beta(\A)$ differs from that of Ahrens, {\em et. al.} by
a minus sign \cite[Definition 2.2]{AGM}. For our purposes this is
the more convenient convention.

\begin{lemma}\label{l:sumlink} If $\A$ is a point configuration then
\[
\beta(\A)= \sum_{a \in \A} \widetilde{\chi}(\del_{\Free}(a)).
\]
\end{lemma}

\begin{proof}  As noted in Lemma~\ref{l:linkdel}
\[
\widetilde{\chi}(\del_{\Free}(a))= \sum_{a \in K \in \Free}(-1)^{|K|}
\]
since $\Free$ is contractible by Lemma~\ref{l:free}.
Thus 
\begin{align*}
\sum_{a \in \A} \,\, \widetilde{\chi}(\del_{\Free}(a))&=\sum_{a \in \A}\sum_{a \in K \in \Free}(-1)^{|K|}\\
     &=\sum_{K \in \Free}(-1)^{|K|}|K|\\
    &=\beta(\A).
\end{align*}
\end{proof}

  From Lemma~\ref{l:sumlink}, we see that it is sufficient to understand
the topology of each deletion $\del_{\Free}(a)$ in order to evaluate
$\beta(\A)$. That is what we endeavor to do in the rest of this section.  
  Let $\mathbf{P}= \conv(\A)$.  We will assume that $\mathrm{dim}(\Po)=d$ and thus the interior of $\Po$ is the same as its
relative interior.  Let $\bdy(\Po)$ denote the points of $\A$ lying in
the boundary of $\conv(\A)$, that is,  $\bdy(\Po):=\A - \inte(\A)$. 

\begin{lemma}\label{l:boundary} Let $x \in \A$ and suppose that
$x \in \bdy(\Po)$.  Then $\del_{\Free}(x)$ is contractible. As a consequence
$\widetilde{\chi}(\del_{\Free}(x))=0$.
\end{lemma}

\begin{proof} If $x$ is on the boundary of $\Po$ then it is contained
in the relative interior of a unique face $\mathbf F$ of $\Po$.  Let 
$F=\mathbf F \cap \A$. Define a new
point configuration $\mathcal B$ by
\[
\mathcal B = F \cup \{t\}
\]
where $t$ is a new point in $\R^d$ that is affinely independent of the points
in $F$.  The map $f$ from $\A$ to $\B$ defined by
\[
f(a)=
\begin{cases}
		a \quad &\mathrm{ if }\ a \in F\\
		t\quad &\mathrm{ otherwise }.
\end{cases}  
\]
induces a map $\hat f$ from subsets of $\A$ to subsets of
$\B$ by $\hat f(A)=\{f(a)\,|\,a \in A\}$.
It is easy to check that $\hat f$ restricts to a map from $\del_{\Free(\A)}(x)$
to $\del_{\Free(\B)}(x)$.  In order to apply Lemma~\ref{l:Quillen} we will
view both of these simplicial complexes as their posets of faces as discussed
in Remark~\ref{r:warning}.


We now analyze the fibers of this restricted map $\hat{f}$. For notational convenience,
let 
$$
\begin{aligned}
\Gamma &= \del_{\Free(\A)}(x) \\
\Gamma'&=\del_{\Free(\B)}(x).
\end{aligned}
$$
Suppose that $K \in \Gamma'$. We consider two cases in analyzing
the fiber $\hat{f}^{-1}(\Gamma_{\leq K}')$.  

If $t \not\in K$, then
\[
\hat{f}^{-1}(\Gamma_{\leq K}')=\left\{C \subseteq K\,|\,C \in \Gamma\right\},
\]
which has $K$ as a maximum element, since $K \in \Gamma'$ and
$t \not\in K$ implies that $K \in \Gamma.$ 
Hence this fiber is contractible.

If $ t \in K$, then
\begin{align*}
\hat{f}^{-1}(\Gamma_{\leq K}')&=\left\{C \in \Gamma\,|\, C \cap F \subseteq K\right\}\\
&=\Free((K-\{t\}) \cup (\A-F)), 
\end{align*}
(here $(K-\{t\}) \cup (\A-F)$ is considered as a point configuration
on its own).  This fiber is then contractible by Lemma~\ref{l:free}.

  Thus the fibers $\hat{f}^{-1}(\Gamma_{\leq K}')$ are always contractible,
and so by Lemma~\ref{l:Quillen}, we know that
$\del_{\Free(\A)}(x)$ has the same homotopy type
as $\del_{\Free(\B)}(x)$.  Since the point $t$ was affinely independent
of all of the other points in $\B$, we see that $\del_{\Free(\B)}(x)$ has
$t$ as a cone point, and hence is contractible. 
Thus $\del_{\Free(\A)}(x)$ is contractible and the
lemma is proven.
\end{proof}


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

\begin{lemma}\label{l:interior}Let $x \in \A$ and suppose that
$x \in \inte(\Po)$.  Then $\del_{\Free}(x)$ has the integral
homology of a $(d-1)$-sphere. As a consequence,  $\widetilde{\chi}(\del_{\Free}(x)=(-1)^{d-1}$.
\end{lemma}

\begin{proof}  Suppose that $x \in \inte(\Po)$.  Define the
poset $CN(x)$ by
\[
CN(x)=\left\{K \in \La\,| x \not\in \relint(\conv(K))\,\right\}.
\]
Note that $\del_{\Free}(x) \subseteq CN(x)$  and so we can consider the
inclusion map 
$$
\iota : \del_{\Free}(x) \to CN(x).
$$
Again we will view $\del_{\Free}(x)$ as its poset of faces in order to
apply Lemma~\ref{l:Quillen} as discussed in Remark~\ref{r:warning}.

\begin{claim} The fibers $\iota^{-1}(CN(x)_{\leq K})$ are contractible
for every $K \in CN(x)$.
\end{claim}
\begin{proof}[Proof of claim]  There are two cases to consider.  First,
suppose that $x \not\in K$. Then we see that
\[
\iota^{-1}(CN(x)_{\leq K})=\Free(K).
\]
This follows since $K \in \La$ implies that any free subset of $K$ is also
a free subset of $\A$, and $x \not\in K$ implies that it is not in any subset
of $K$.  By Lemma~\ref{l:free}, $\Free(K)$ is contractible and so we are done.

  The second case is that $x \in K$.  Then by the definition of $CN(x)$,
we have $x \in \bdy(\conv(K))$.  From this we conclude that
\begin{align*}
\iota^{-1}(CN(x)_{\leq K})&=\left\{ C \in \Free(K)\,|\, x \not\in C\right\}\\
			  &=\del_{\Free(K)}(x).
\end{align*}
which is contractible by Lemma~\ref{l:boundary}.
\end{proof}

Continuing the proof of Lemma~\ref{l:interior}, since the fibers of $\iota$ are all contractible, Lemma~\ref{l:Quillen} implies that
$\del_{\Free}(x)$ has the same homotopy type as $CN(x)$.  Consider another
poset $N(x)$ defined by
\[
N(x)=\left\{ B \subseteq \A\,|\, x \not\in \relint(\conv(B))\right\}.
\]
The difference between $N(x)$ and $CN(x)$ is that the subsets in $N(x)$
need not be convex.  The closure operator $f(B) = B^c$ gives
a map $f$ from $N(x)$ to itself, since  
$$
x \not\in \relint(\conv(B)) \quad \Rightarrow\quad
x \not\in \relint(\conv(B^c)).
$$
The image of $N(x)$ under the 
map $f$ is exactly $CN(x)$.  Thus by Lemma~\ref{l:closure} we have that
$N(x)$ has the same homotopy type as $CN(x)$, and thus the same homotopy type
as $\del_{\Free}(x)$.  It only remains to analyze the homology of
$N(x)$.

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

\end{proof}


\noindent
{\bf Theorem 1.1} [see  \cite[Conjecture 4.1]{AGM}]
{\em
If $\A$ is a point configuration in $\R^d$ then
\[
\beta(\A)=\sum_{K \in\Free}(-1)^{|K|}|K|=(-1)^{d-1}|\inte(\A)|,
\]
 i.e., $ (-1)^{d-1}\beta(\A)$ equals the number of points in
$\A$ which are in the interior of the convex hull of $\A$.
}

\begin{proof} The proof is immediate from Lemmata~\ref{l:sumlink},   ~\ref{l:boundary} and ~\ref{l:interior} 
\end{proof}

\section{Convex geometries}\label{s:convexgeometry}  In this section we
discuss generalizations of Theorem \ref{t:main} to more general convex geometries.  Most of the framework discussed in Section~\ref{s:main}
goes through for general convex geometries, but we lack at the moment
completely general versions of Lemma~\ref{l:boundary} or
Lemma~\ref{l:interior}.  We can, however, prove
analogues of these lemmata for other specific examples of convex geometries.

  We begin with a brief description of the theory of convex geometries.  
For a more detailed introduction see \cite{EJ}, whose notation we
follow.  Let $X$ be a finite set, and $\Li$ a collection of subsets of $X$ 
that contains $\varnothing$ and $X$ and is closed under intersection.
We can alternatively think of $\Li$ as a closure operator on $X$ defined by
\[
\Li(A)=\bigcap_{\{C \in \Li\,|\,C \supseteq A\}} C.
\]
The subsets in $\Li$ or, equivalently, those subsets  $A$ of $X$ such that
$\Li(A)=A$ will be called {\em convex sets}.  We will say that $\Li$ is
{\em anti-exchange} if given any convex set $C$, and two unequal points
$p$ and $q$ in $X$, neither in $C$, one has that
\[
q \in \Li(K \cup \{p\})\quad \Rightarrow \quad p \not\in \Li(C \cup \{q\}).
\]
A collection $\Li$ of convex sets that is anti-exchange will be called a
{\em convex geometry}. Let $\La(\Li)$ be the lattice of convex sets of
$\Li$ ordered by containment.   Some examples of convex geometries are  
\begin{description}
\item[Point configurations]  The collection of {\it convex subsets}
of a point set $\A$ in $\R^d$ (as described in the previous section)
is a convex geometry, with $X = \A$.

\item[Order convex sets]  Let $Q$ be a poset, and for any
subset $A \subseteq Q$ define
\[
\mathcal{C}_Q(A)=\left\{ q \in Q\,|\, \exists\  a,a' \in A,\ a \leq q \leq a'\right\}.
\]
The closure $\mathcal{C}_Q$ is anti-exchange, and we call the associated convex geometry
with $X=Q$ the {\em order convex sets of $Q$}, denoted $\mathcal{C}_Q$.

\item[Chordal graphs]  Let $G$ be a chordal graph on a vertex set $V$.
That is, $G$ is a graph such that every cycle of length longer than
$4$ has a chord.  A subset $C$ of $V$ will be called {\em m-convex} if it
contains every vertex on every  chordless path between vertices in $C$.
The collection $\Li(G)$ of m-convex sets of a chordal graph is a
convex geometry, with $X=V$ \cite{FJ}.
\end{description}

   If  $C$ is a convex set in a convex geometry $\Li$, a point $x \in C$ is
called {\em an extreme point of $C$} if $x \not\in \Li(C-x)$.  We denote
the set of extreme points of $C$ by $ex(C)$.  We will call a convex set
{\em free} if $ex(C)=C$.  The set of free sets of a convex geometry 
form a simplicial complex which we denote $\Free(\Li)$.  The following lemmata
are direct generalizations of Lemma~\ref{l:lattice} and Lemma~\ref{l:free}.

\begin{lemma} Let $\Li$ be a convex geometry on a ground set $X$ and $\La=\La(\Li)$ be its lattice
of convex sets.   Then $\overline{\La}$ triangulates an
\[
\left\{ 
\begin{matrix}
(|X|-2)-\text{ball} & \text{ if }X \neq \ex(X) \\
(|X|-2)-\text{sphere} & \text{ if }X = \ex(X)
\end{matrix}
\right.
\] 
\end{lemma}
\begin{proof} See \cite[Theorem 4.10]{EJ}.
\end{proof}

\begin{lemma}\label{l:convexfree}Let $\Li$ be a convex geometry 
and $\Free$ its simplicial complex of free sets.  Then $\Free$ is
contractible.
\end{lemma}
\begin{proof}  The proof follows exactly the argument for Lemma~\ref{l:free}. 
\end{proof}

  As before we define 
\[
 \beta(\Li)=\sum_{K \in \Free(\Li)}(-1)^{|K|}|K|.
\]
and note that because of Lemma~\ref{l:convexfree}, Lemma~\ref{l:sumlink} still holds, i.e.,
\begin{equation}
\beta(\Li)= \sum_{x \in X} \widetilde{\chi}(\del_{\Free(\Li)}(x)).\label{e:betaconvex}
\end{equation}
Although we do not have a uniform way of computing $\beta(\Li)$ for 
all convex geometries, we can use the framework we have established
to evaluate it for the examples of convex geometries we described above.
We sketch those arguments here.

\subsection{Order convex sets}  Let $Q$ be a poset and $\mathcal{C}_Q$ be
the collection of order convex sets of $Q$.  We call an element $q \in Q$ a
{\em bottleneck} if $q$ is comparable to every element of $Q$,
but $q$ is neither a maximum nor a minimum element.

\begin{lemma}\label{l:ordertop} Let $\Free=\Free(\mathcal{C}_Q)$ be the free sets of the
convex geometry of order convex sets of $Q$. Then $\del_{\Free}(q)$ has the
homotopy type of the $0$-sphere if $q$ is a bottleneck, and is contractible
otherwise.
\end{lemma}
\begin{proof}[Sketch of Proof] If $q$ is a bottleneck define
$Q_{>q}$ ( resp. $Q_{<q})$ to be the points in $Q$ strictly bigger than (resp. less than)
 $q$. It is easy
to check that $\lk_{\Free}(q)$ is the disjoint union of the two
(non-empty) complexes $\Free(\mathcal{C}_{Q_{>q}})$ and $\Free(\mathcal{C}_{Q_{<q}})$,
each of which is contractible by Lemma \ref{l:free}.
Hence $\del_{\Free}(q)$ has the homotopy type of the $0$-sphere.

  If $q$ is not a bottleneck, then there are two possibilities.
On the one hand, $q$ might be a maximum or minimum element,
in which case it is easy to see that $\del_{\Free}(q)$ is the
same as $\Free(\mathcal{C}_{Q-\{q\}})$, and hence is contractible
by Lemma~\ref{l:free}.

If $q$ is not a bottleneck and is also neither a maximum nor a minimum
element of $Q$, then there exist elements of $Q$ which are bigger than
$q$, smaller than $q$, and incomparable to $q$.  Define a new four-element
poset $Q'=\{b,s,i,q'\}$ 
(here $b,s,i$ are mnemonic for ``bigger",``smaller", ``incomparable" to $q$)
in which $b \geq q' \geq s$ and $i$ is incomparable to any of the other 
three. One can easily check that $\del_{\Free(\mathcal C_{Q'})}(q')$
is contractible since it is a cone with cone point $i$.  The
 map $f: Q \to Q'$ given by
\[
f(x)=
\begin{cases}
     b \quad &\textrm{if } x > q\\
     q' \quad &\textrm{if } x = q\\
     s \quad &\textrm{if } x < q\\
     i \quad &\textrm{if } x \textrm{ is incomparable to } q.
\end{cases}
\]
induces a map from $\del_{\Free(\mathcal{C}_Q)}(q)$ to $\del_{\Free(\mathcal{C}_{Q'})}(q')$.  One can check the relevant fibers
 $f^{-1}(Q'_{\leq y})$ to see that they are all contractible, and thus $\del_{\Free(\mathcal{C}_Q)}(q)$ has the homotopy type of $\del_{\Free(\mathcal C_{Q'})}(q')$, and hence is contractible.
\end{proof}

\begin{corollary} Let $Q$ be a poset and $\mathcal{C}_Q$ be
the collection of order convex sets of $Q$.  Then $\beta(\mathcal{C}_Q)$ is
equal to the number of bottlenecks in $Q$.
\end{corollary}
\begin{proof} From the previous lemma we see that
\[
\widetilde{\chi}(\del_{\Free}(q))=
\begin{cases}
      1 \quad &\textrm{ if $q$ is a bottleneck}\\
      0 \quad &\textrm{ otherwise}.
\end{cases}
\]
Apply this formula to (\ref{e:betaconvex}).
\end{proof}

\subsection{Chordal graphs}\label{ss:graph} 
Gordon has previously interpreted  $\beta(\Li(G))$ for
a chordal graph $G$ in \cite{Go}.  He did this by means of a deletion-contraction argument.  Our topological
approach gives a more detailed result.

\begin{lemma} Let $G$ be a connected chordal graph.  A subset $K$ of $V$ is free in $\Li(G)$ if and only if it induces a clique in $G$.
\end{lemma}
\begin{proof}  See \cite[Lemma 5.1]{Go}.
\end{proof}

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

\begin{lemma}\label{l:graphtop}   Let $G$ be a connected chordal graph and $\Free=\Free(\Li(G))$.
For each vertex $v$ in $G$, the complex  $\del_{\Free}(v)$ has the homotopy type of $c(v)$ disjoint points.
\end{lemma}

\begin{proof}[Sketch of Proof]  It is easy to show that $\del_{\Free}(v)$
is just the disjoint union of $\Free(\Li(G'))$  for each connected component
$G'$ of $G-v$.  By Lemma~\ref{l:convexfree} these are all contractible so
the lemma follows.
\end{proof}

  Recall that a {\em block} of a graph is a maximal subgraph which
contains no cut-vertex. We denote by $b(G)$ the number of blocks  in the
graph $G$.

\begin{corollary} \cite[Theorem 5.1]{Go}
Let $G$ be a connected chordal graph.  Then
$$
\beta(\Li(G))=b(G)-1.
$$
\end{corollary}
\begin{proof} From the previous lemma we see that
\[
\widetilde{\chi}(\del_{\Free}(v))=c(v)-1,
\]
and so 
\[
\beta(\Li(G))=\sum_{v \in G} (c(v)-1).
\]
It is then an elementary graph-theoretic  fact \cite[Problem 4.1.28]{We} that 
\[
\sum_{v \in G} (c(v)-1)=b(G)-1.
\]
\end{proof}

\section{Open problems}\label{s:open}  In this section we  discuss some open problems
aimed toward generalizing  Theorem~\ref{t:main} to all convex geometries.
  As a first step in this direction we formulate a conjecture that generalizes Lemma~\ref{l:boundary} for all convex geometries.  Let $\Li$ be
a convex geometry on the ground set $X$.  A subset $A$ of $X$ will be called
{\em independent} if $a \not\in \Li(A-a)$ for all $a \in A$.  We will say
that {\em $x$ depends on $y$} if there exists an independent set $A$ such that
$y \in A$, $ x \in \Li(A)$ but $x \not\in \Li(A-y)$. Let $Dep(x)$ be the
set of all points $y$ such that $x$ depends on $y$.  The situation in 
which $Dep(x)=X$ includes the following as special cases
\begin{itemize}
\item  $x \in \inte(\A)$ for a point configuration,
\item $x$ is a bottleneck of a poset,
\item $x$ is a vertex for which $c(v)=1$ in a chordal graph.
\end{itemize}

\begin{conjecture}[cf. Lemmata~\ref{l:boundary}, \ref{l:ordertop},
and \ref{l:graphtop}] For a convex geometry $\Li$ on the ground set $X$, the complex $\del_{\Free(\Li)}(x)$ is contractible unless $Dep(x) = X$.
\end{conjecture}

  The question of what happens if $Dep(x)=X$ is much less clear, as the
diversity of outcomes in 
Lemmata~\ref{l:interior}, \ref{l:ordertop}, and \ref{l:graphtop} indicate. 
In this direction, we pose the following question.

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



\begin{thebibliography}{20}
\bibitem{AGM}
C. Ahrens, G. Gordon and E. McMahon,\emph{Convexity and the beta invariant},
preprint, 1998.

\bibitem{BL}
M. Bayer and C. Lee, \emph{Combinatorial aspects of convex polytopes}, in
Handbook on Convex Geometry (P. Gruber and J. Wills, eds.), North-Holland,
Amsterdam, 1993, pp. 485--534.

\bibitem{Bj}
 A. Bj\"orner, \emph{Topological methods}, Handbook of Combinatorics (R. Graham, M. Gr\"otschel, and L. Lov\'asz, eds.), North Holland, Amsterdam, 1995, pp. 1819-1872.

\bibitem{Bj2}
A. Bj\"orner, \emph{Homology and shellability of matroids and geometric lattices},
in Matroid Applications (N. White, ed.), Encyclopedia of Mathematics and
its Applications, Vol. 40,  Cambridge Univ. Press, Cambridge, 1992, pp. 226-283.

\bibitem{BLSWZ}
A. Bj\"orner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler,
Oriented Matroids, Encyclopedia of Mathematics and its Applications, vol. 46,
Cambridge University Press, Cambridge, 1993.

\bibitem{Cr}
H. Crapo, \emph{A higher invariant for matroids}, J. Comb. Th.,\textbf{2}~(1967), 406--417.

\bibitem{Do}
X. Dong, personal communication, 1999.

\bibitem{EJ}
P. H. Edelman and R. Jamison, \emph{The theory of convex geometries}, Geom. Ded.,\textbf{19}~(1985), 247--270.

\bibitem{FJ}
M. Farber and R. Jamison, \emph{On local convexity in graphs}, Discrete Math.,
\textbf{66}~(1987), 231--247.

\bibitem{Go}
G.  Gordon,  \emph{A $\beta$ invariant for greedoids and antimatroids},
Elect. J. Combin.,\textbf{4}~(1997), \#R13.
\bibitem{GM1}
G. Gordon and E. McMahon,\emph{ A greedoid polynomial which distinguishes rooted
arborescences}, Proc. Amer. Math. Soc. \textbf{107}~(1989), 287--298.

\bibitem{GM2}
G. Gordon and E. McMahon, \emph{A greedoid characteristic polynomial}, Contemp. Math.
\textbf{197}~(1996), 343-351.

\bibitem{Gr}

B. Gr\"unbaum, Convex Polytopes, Interscience, London, 1967.

\bibitem{Kl}

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

\bibitem{Mu}
J. Munkres, Elements of Algebraic Topology, Addison-Wesley, Menlo Park, 1984.

\bibitem{Qu}
D. Quillen, \emph{Homotopy properties of the poset of non-trivial $p$-subgroups
of a group}, Adv. in Math.,\textbf{28}~(1978), 101-128.

\bibitem{Re}
V. Reiner, \emph{On some instances of the generalized Baues problem}, preprint, 1998.

\bibitem{We}
D. B.  West, Introduction to  Graph Theory, Prentice-Hall, Upper Saddle River,
1996.


\end{thebibliography}

 


\end{document}
