%asrh/msri.tex
\documentclass[12pt]{amsart}
\usepackage{amsmath, amsthm}
\headheight=8pt     \topmargin=0pt
\textheight=624pt   \textwidth=432pt
\oddsidemargin=18pt \evensidemargin=18pt

%\textwidth6.5truein 
%\textheight8.5truein
%%\topmargin-0truein 
%\topmargin-0.5truein 
%\oddsidemargin+0.2truein
%\baselineskip0.20truein 
%%%----Rough draftversion----- 
%\pagestyle{myheadings} 
%\markright{ \today }
%%\renewcommand{\baselinestretch}{1.3}
%%%---------------------------- 

%---more final version----
\newtheorem{thm}{Theorem}[section]
\newtheorem{lemma}[thm]{Lemma} 
%\newtheorem{rmk}[thm]{Remark}%only if you want to number remarks
\newtheorem{cor}[thm]{Corollary} 
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{prop}[thm]{Proposition}

\theoremstyle{definition}
\newtheorem*{defn}{Definition}
\newenvironment{defncite}[1]{\begin{defn}[#1]}{\end{defn}}
%\newtheorem*{ex}{Example}
\newtheorem{ex}[thm]{Example}

\theoremstyle{remark}
\newtheorem*{rmk}{Remark}
%-------------------------
\newcounter{alphcount}
\renewcommand{\thealphcount}{(\alph{alphcount})}
\newenvironment{alph-list}{\begin{list}{\thealphcount}{\usecounter{alphcount}}}%
                        {\end{list}} 

%--macros
%%for anything missing, try ithom/ober.tex first.

%general, non-math
\newcommand{\ie}{{\em i.e.}} 
\newcommand{\eg}{{\em e.g.}} 
\newcommand{\dfn}[1]{{\bf {#1}}} 
\newcommand{\idfn}[1]{#1} 
\newcommand{\abs}[1]{|#1|}

%general, math
\newcommand{\disun}{\mathbin{\dot{\cup}}}       %from Mark Purtill
\newcommand{\condns}[2]{\substack{#1 \\ #2}}
\newcommand{\numsys}[1]{{\bf #1}}
\renewcommand{\colon}{{:}\;}
\newcommand{\maps}{\rightarrow} 
\newcommand{\revimplies}{\impliedby}
\newcommand{\lrimplies}{\iff}
\newcommand{\rhom}{\widetilde{H}}
\newcommand{\rhomi}[1]{\widetilde{H}_{#1}}
\newcommand{\rcohomi}[1]{\widetilde{H}^{#1}} 
\newcommand{\homi}[1]{H_{#1}}
\newcommand{\nd}{\;}    %''and'' in series of conditions
\newcommand{\sh}[1]{\Delta(#1)}

%sequences etc.
\newcommand{\seq}[3]{{#1}_{#2},\dots,{#1}_{#3}}
\newcommand{\ltseq}[3]{{#1}_{#2} < \dots < {#1}_{#3}}
\newcommand{\ltsubseq}[4]{#1_{#2_#3} < \dots < #1_{#2_#4}}
\newcommand{\gtseq}[3]{{#1}_{#2} > \dots > {#1}_{#3}}
\newcommand{\set}[3]{\{\seq{#1}{#2}{#3}\}}
\newcommand{\setseq}[3]{\{\ltseq{#1}{#2}{#3}\}}
\newcommand{\setsubseq}[4]{\{\ltsubseq{#1}{#2}{#3}{#4}\}}
\newcommand{\sumseq}[3]{{#1}_{#2}+\cdots+{#1}_{#3}}
\newcommand{\wedgeseq}[3]{{#1}_{#2} \wedge \cdots \wedge {#1}_{#3}}
\newcommand{\wedgesubseq}[4]{#1_{#2_#3} \wedge \dots \wedge #1_{#2_#4}} 

%alg shifting stuff
%\newcommand{\kk}{{\mbox{\bf k}}}%these two...
\newcommand{\kk}{\boldsymbol k}
%\newcommand{\dimk}{\dim_{\bf k}}%...go together
\newcommand{\dimk}{\dim_{\kk}}
\newcommand{\kV}{\kk V}
\newcommand{\imt}[1]{\widetilde{#1}}%''IMage-Tilde''
\newcommand{\imf}[1]{\widetilde{f}_{#1}}%''IMage-Tilde'' -- f-variation
\newcommand{\img}[1]{\widetilde{\gamma}_{#1}}%...gamma variation
\newcommand{\ime}[1]{\widetilde{e}_{#1}}%...e variation
\newcommand{\collC}{\mathcal C}

%\rm in math 
\DeclareMathOperator{\link}{lk}
\newcommand{\lk}[2]{\link_{#1}#2}
\newcommand{\degk}[2]{\deg_{#1} #2}
\DeclareMathOperator{\spn}{span}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\Gin}{Gin}

%old betas
\newcommand{\betat}{\beta}
\newcommand{\rbeti}[1]{\beta_{#1}}

\begin{document} 

\title{Algebraic Shifting Increases Relative Homology}

\author{Art M. Duval}
\address{\hskip-\parindent
        University of Texas at El Paso\\
        Department of Mathematical Sciences\\   
        El Paso, TX 79968-0514}
\email{artduval@math.utep.edu}

\thanks{Research performed while a General Member
of the Mathematical Sciences Research Institute, Berkeley.  Research
at MSRI is supported in part by NSF grant DMS-9701755}

\begin{abstract}

We show that algebraically shifting a pair of simplicial complexes
weakly increases their relative homology Betti numbers in every
dimension.  

More precisely, let $\Delta(K)$ denote the algebraically shifted
complex of simplicial complex $K$, and let $\rbeti{j}(K,L)=\dimk
\rhomi{j}(K,L;\kk)$ be the dimension of the $j$th reduced relative
homology group over a field $\kk$ of a pair of simplicial complexes $L
\subseteq K$.  Then
$\rbeti{j}(K,L) \leq \rbeti{j}(\Delta(K),\Delta(L))$ for all $j$.

The theorem is motivated by somewhat similar results about Gr\"obner
bases and generic initial ideals.  Parts of the proof use Gr\"obner
basis techniques.
\end{abstract}

\maketitle

\section{Introduction}\label{se:intro}
Algebraic shifting is a remarkable procedure that finds, for any
simplicial complex $K$, a shifted (and hence combinatorially simpler)
simplicial complex $\Delta(K)$ with many of the same properties as
$K$.  For instance, the $f$-vector and homology Betti numbers are
preserved; Bj\"orner and Kalai~\cite{BjKal:1} used this fact to
characterize the $f$-vectors and Betti numbers of simplicial
complexes.

However, the situation for pairs of complexes and relative homology is
different.  In a simple example on three vertices
(Example~\ref{ex:pardue}), algebraically shifting a pair of complexes
increases their relative homology in dimensions $0$ and $1$.  Upon
seeing this one example, Keith Pardue (private communication)
conjectured that algebraic shifting always weakly increases relative
homology in every dimension.  Our main result (Theorem~\ref{th:main})
is that this conjecture is true.

Pardue's conjecture was grounded in more than just this one simple
example.  Algebraic shifting, which takes place in exterior
(anti-commutative) algebra, is similar to using Gr\"obner bases and
generic initial ideals in commutative algebra (see
Section~\ref{se:alg.shift}).  Quantities such as free resolution Betti
numbers weakly increase upon taking generic initial ideals (see,
\eg,~\cite{Hulett:thesis, Hulett, Bigatti}, and
Section~\ref{se:alg.shift}).  Pardue's insight was that these results
would carry over to algebraic shifting.

It would be ideal, then, to prove his conjecture by translating the
algebraic shifting problem to a generic initial ideal problem, and
then invoking the existing results.  However, this approach has been
unsuccessful, so far.  The proof here, while motivated at points by
Gr\"obner basis ideas (see Lemma~\ref{th:gamma.exist}), instead
directly refines Bj\"orner and Kalai's correspondence between the
homology of the original complexes and the combinatorics of the
algebraically shifted complexes.  The hope is that this result will
serve as further evidence of the deeper
connection between algebraic shifting and generic initial ideals.

Background and notation on simplicial complexes, including homology,
shifted complexes, and near-cones is in Section~\ref{se:scx}.
Algebraic shifting is reviewed and compared to generic initial ideals
in Section~\ref{se:alg.shift}.  In Section~\ref{se:rel.hom}, we use
Gr\"obner basis ideas to define a nice basis of a space associated
with a pair of complexes $(K,L)$, and then use this basis to compare
key components of the homology groups of $(K,L)$ and
$(\Delta(K),\Delta(L))$.  We prove our main result
(Theorem~\ref{th:main}) in Section~\ref{se:proof}.

\section{Simplicial complexes}\label{se:scx}
For basic definitions of simplicial complexes and their homology and
relative homology, see, \eg,~\cite[Chapter~1]{Mu}
or~\cite[Section~0.3]{St:CCA}.  We allow the empty simplicial complex
$\emptyset$ consisting of no faces; all other complexes must contain
the empty set as a $(-1)$-dimensional face.  We also allow the complex
$\{\emptyset\}$ consisting of only the empty face, but we do
distinguish between the two complexes $\emptyset$ and $\{\emptyset\}$.
Let $K_j$ denote the set of $j$-dimensional faces of a simplicial
complex $K$.  The \dfn{$f$-vector} of $K$ is the sequence
$(f_0,\ldots,f_{d-1})$, where $f_j = f_j(K) = \abs{K_j}$ and $d-1 =
\dim K$.  The same notion of $f$-vector will apply in this paper to
every finite collection of sets.

Let $\kk$ be a field, fixed throughout the paper.  The $j$th
\dfn{Betti number} of a simplicial complex $K$ is
$\rbeti{j}=\rbeti{j}(K)=\dimk\rhomi{j}(K)$, where $\rhomi{j}(K)$ is
the $j$th reduced homology group of $K$ (with respect to $\kk$).
Similarly, the $j$th \dfn{relative Betti number} of a pair of
simplicial complexes $L
\subseteq K$ is $\rbeti{j}=\rbeti{j}(K,L)=\dimk\rhomi{j}(K,L)$, where
$\rhomi{j}(K,L)$ is the $j$th reduced \dfn{relative homology group} of
the pair $(K,L)$ (with respect to $\kk$).

``Reduced'' homology means precisely to treat the empty set as a face
of any non-empty complex, so $\rbeti{0}$ is one less than the number
of connected components of $\Delta$, and hence one less than the
``unreduced'' $\rbeti{0}$.  Furthermore, $\rbeti{-1}=0$, unless
$\Delta=\{\emptyset\}$, in which case $\rbeti{-1}=1$.
%
Reduced relative homology, which also treats the empty set as a face
of any non-empty complex, is the same as unreduced
relative homology, except that $\rbeti{-1}(\{\emptyset\},\emptyset)=1$;
for any other pair of complexes,
$\rbeti{-1}=0$.

%Recall that over a field $\kk$, $\dimk \rcohomi{j}(K;\kk) = 
%\dimk \rhomi{j}(K;\kk)$, so that Betti numbers measure reduced homology
%as well as reduced cohomology.

\begin{defn}
If $S=\setseq{s}{1}{j}$ and $T=\setseq{t}{1}{j}$ are $j$-subsets
of integers,
then:
\begin{itemize}
\item $S \leq_P T$ under the standard \dfn{partial order} if $s_p
  \leq t_p$ for all $p$; and
\item $S <_L T$ under the \dfn{lexicographic order} if there is a
  $q$ such that $s_q < t_q$ and $s_p = t_p$ for $p < q$ .
\end{itemize}
\end{defn}

Lexicographic order is a total order which  refines the 
partial order.

\begin{defn}
A collection $\collC$ of $k$-subsets is \dfn{shifted} if $S \leq_P T$
and $T \in \collC$ together imply that $S \in \collC$.  A simplicial
complex 
$\Delta$ is \dfn{shifted} if the set of $j$-dimensional faces of
$\Delta$ is shifted for every $j$.
\end{defn}

Bj\"orner and Kalai showed in~\cite{BjKal:1} that
shifted complexes are near-cones, which we now define.

\begin{defn}
A \dfn{near-cone} with \dfn{apex} $v_0$ is a simplicial complex
$\Delta$ satisfying the following property:
For all $F \in \Delta$, if $v_0 \not\in F$ and $w \in F$, then 
$$(F - \{w\}) \cup \{v_0\} \in \Delta.$$  
For $\Delta$ a near-cone with apex $v_0$, let
$B(\Delta) = 
	\{F \in \Delta\colon F \cup \{v_0\} \not\in \Delta\}$
and 
$\Delta' 
  = \{F \in \Delta\colon v_0 \not\in F, F \cup \{v_0\} \in \Delta\}$;
then 
$$\Delta = (v_0 \ast \Delta') \disun B(\Delta),$$
where $\ast$ denotes topological join (so
$v_0 \ast \Delta' = 
  \Delta' \disun \{\{v_0\} \disun F\colon F \in \Delta'\}$).
Both $\Delta'$ and $\Delta' \disun B(\Delta)$ are subcomplexes of $\Delta$.
If $B(\Delta) = \emptyset$, then $\Delta$ is simply a \dfn{cone}.
\end{defn}

Note, in particular, that $\emptyset$ and $\{\emptyset\}$ are
near-cones (the condition in the definition is vacuous in this case)
and that $\emptyset = v_0 \ast \emptyset$ and 
$\{\emptyset\} = (v_0 \ast \emptyset) \disun \{\emptyset\}$.  
If $\Delta$ is a near-cone with apex $v_0$, then $v_0$ is one of the
vertices of $\Delta$, unless $\Delta=\emptyset\ {\rm or}\ \{\emptyset\}$.

It is not hard to see that shifted simplicial complexes are near-cones
with apex $1$.

Every $F \in B(\Delta)$ is maximal in $\Delta$, so the collection of
faces in $B(\Delta)$ forms an antichain.  Further, $f(B(\Delta)) =
\betat(\Delta)$, which follows by contracting $v_0 \ast \Delta'$ to
$v_0$, leaving a sphere for every face in
$B(\Delta)$~\cite[Theorem~4.3]{BjKal:1}.
In other words, 
if $\Delta$ is a near-cone with apex $v_0$, then
\begin{equation}\label{eq:beta.shift}
\rbeti{j}(\Delta)= \abs{\{F\in \Delta_j\colon 
	v_0 \not\in F, \nd v_0 \disun F \not\in \Delta\}}.
\end{equation}
This observation is generalized by~\cite[Lemma~8]{art:relative}:
If $\Gamma \subseteq \Delta$ is a pair of near-cones with common apex
$v_0$, then
\begin{multline}\label{eq:pair.near-cones}
\rbeti{j}(\Delta,\Gamma)=
  \abs{\{F\in (\Delta - \Gamma)_j\colon 
	v_0 \not\in F, \nd v_0 \disun F \not\in \Delta\}}\\  +
  \abs{\{G\in (\Delta - \Gamma)_j\colon 
	v_0 \in G, \nd G - \{v_0\} \in \Gamma\}}.
\end{multline}

In light of the formulation of the homology of near-cones that
equation~\eqref{eq:beta.shift} gives,
equation~\eqref{eq:pair.near-cones} is approximately the near-cone
equivalent of using the long exact sequence
(e.g.,~\cite[Theorem~23.3]{Mu})
\begin{equation}\label{eq:les}
\dots \rightarrow \rhomi{j}(L) \xrightarrow{i_*} \rhomi{j}(K) 
      \xrightarrow{\pi_*} \rhomi{j}(K,L) 
      \xrightarrow{\partial_*} \rhomi{j-1}(L) \rightarrow \cdots
\end{equation}
to compute
$$\rbeti{j}(K,L) = \dim(\im (\pi_*)_j) + \dim(\im (\partial_*)_j)$$
for an arbitrary pair $(K,L)$.


\section{Algebraic shifting}\label{se:alg.shift}

Algebraic shifting transforms a simplicial complex into a shifted
simplicial complex with the same $f$-vector and Betti numbers.  
It also preserves many
algebraic properties of the original complex.  Algebraic shifting was
introduced by Kalai in~\cite{Kal:Eck}; our exposition is summarized
from~\cite{BjKal:1} and included for completeness (see
also~\cite{BjKal:NYAS,Kal:AS}).  We start with the exterior face ring.

\begin{defn} 
Let $K$ be a $(d-1)$-dimensional 
simplicial complex with vertices $V=\set{e}{1}{n}$ 
linearly ordered $\ltseq{e}{1}{n}$.  Let $\Lambda(\kV)$ denote the 
exterior algebra of the vector space $\kV$; it has a $\kk$-vector 
space basis consisting of all the monomials 
$e_S := \wedgesubseq{e}{i}{1}{j}$, 
where $S=\setsubseq{e}{i}{1}{j} \subseteq V$ 
(and $e_{\emptyset}=1$).  
Note that $\Lambda(\kV)=\oplus_{j=0}^n \Lambda^j(\kV)$ is a graded
$\kk$-algebra, and that $\Lambda^j(\kV)$ has basis 
$\{e_S\colon \abs{S}=j\}$.
Let $(I_K)_j$ be the subspace of $\Lambda^{j+1}(\kV)$ generated by the
basis $\{e_S\colon \abs{S}=j+1, \nd  S \not\in K\}$.
Then $I_K:=\oplus_{j=-1}^{d-1} (I_K)_j$ is the homogeneous
graded ideal 
of $\Lambda(\kV)$ generated by $\{e_S\colon S \not\in K\}$.  
Let $\Lambda_j[K] := \Lambda^{j+1}(\kV)/(I_K)_j$.
Then the graded quotient algebra 
$\Lambda[K]:= \oplus_{j=-1}^{d-1} \Lambda_j[K] 
	         = \Lambda(\kV)/I_K$
is called the \dfn{exterior face ring} of $K$ (over $\kk$).  
\end{defn} 

The exterior face ring is the exterior algebra analogue to the
Stanley-Reisner face ring of a simplicial complex~\cite{St:CCA}.  For
$x\in\kV$, let $\imt{x}$ denote the image of $x$ in $\Lambda[K]$.

\begin{defncite}{Kalai}
  Let $\set{f}{1}{n}$ be a ``generic'' basis of $\kV$, \ie,
  $$f_i=\sum^n_{j=1}\alpha_{ij}e_j,$$ where the $\alpha_{ij}$'s are
  $n^2$ transcendentals, algebraically independent over $\kk$.
  Define $f_S:=\wedgesubseq{f}{i}{1}{j}$ for
  $S=\setseq{i}{1}{j}$ (and set $f_\emptyset = 1$).  Let
$$\Delta(K,\kk) :=
        \{S \subseteq [n]\colon \imf{S} \not\in
                \spn \{\imf{R}\colon R <_L S \}\}$$ 
be the \dfn{algebraically shifted complex} obtained from $K$;
we will write $\Delta(K)$ instead of $\Delta(K,\kk)$ when the field is
understood to be $\kk$.  In other words, the $j$-subsets of
$\Delta(K)$ can be chosen by listing all the $j$-subsets of $[n]$ in
lexicographic order and omitting those that are in the span of earlier
subsets on the list, modulo $I_K$ and with respect to the $f$-basis.

The algebraically shifted complex $\Delta(K)$ is (as its name suggests)
shifted, and is independent of the numbering of the vertices of 
$K$~\cite[Theorem~3.1]{BjKal:1}.
\end{defncite} 

It is easy to see that algebraic shifting preserves the $f$-vector,
\ie, $f_j(K)=f_j(\Delta(K))$.  Bj\"orner and Kalai~\cite{BjKal:1} showed that
algebraic shifting also preserves Betti numbers, 
\ie, $\rbeti{j}(K)=\rbeti{j}(\Delta(K))$.  The reason lies in the relation between
algebraic shifting and coboundaries.  Define the \dfn{weighted coboundary operator}
$\delta\colon \Lambda[K]\maps\Lambda[K]$ by
$\delta(x)=\imf{1} \wedge x$, so
$$\delta(\ime{S})= \imf{1} \wedge \ime{S} =
\sum^n_{j=1}\alpha_{1j} \ime{j} \wedge \ime{S} =
\sum_{\condns{j\not\in S}{S \cup \{j\} \in K}}
        \pm \alpha_{1j} \ime{S \cup \{j\}}$$ 
(hence the name weighted coboundary operator).
Betti numbers may be computed using
this $\delta$, \ie,
$\rbeti{j}(K)=\dimk(\ker \delta)_j/(\im \delta)_j$~\cite[pp.~289--290]{BjKal:1}.  
Furthermore, the action of $\delta$ 
on many members of the $\imt{f}$-basis
is easy to describe: $\delta(\imf{F})$ equals $\imf{1\disun F}$ if $1
\not\in F$ and $1 \disun F \in \Delta(K)$, but is zero if $1\in F$
(the third case, when $1 \not\in F$, but $1 \disun F \not\in
\Delta(K)$, is harder, and we shall not need it).

What about relative homology?  First, we note a result of
Kalai's~\cite[Theorem~2.2]{Kal:AS} 
that if $L \subseteq K$ is a pair of simplicial
complexes, then $\Delta(L) \subseteq \Delta(K)$.  For every pair
$(K,L)$, we may then consider the pair $(\Delta(K),\Delta(L))$.  In
contrast to the single complex case, however, the homology of $(K,L)$
and $(\Delta(K),\Delta(L))$ need not coincide, as the following
example shows.

\begin{ex}\label{ex:pardue} 
Let $K$ be the simplicial complex on vertices $\{1,2,3\}$ whose
maximal faces are $\{1\}$ and $\{2,3\}$, and $L$ be the subcomplex
consisting of just the two vertices $\{1\}$ and $\{2\}$.  The only
shifted complex with three vertices and one edge has maximal faces
$\{1,2\}$ and $\{3\}$, so this must be $\Delta(K)$.  Furthermore, $L$
is the only simplicial complex with two vertices and no edges, so
$\Delta(L)=L$.  (See
Figure~\ref{fg:pardue}.)  
\begin{figure}
\begin{center}
\setlength{\unitlength}{0.012500in}%
%
\begin{picture}(458,36)(71,720)
\thicklines
\put(451,740){\circle{8}}
\put(525,740){\circle*{8}}
\put(364,740){\circle{8}}
\put(368,740){\line( 1, 0){ 79}}
\put(364,747){\makebox(0,0)[b]{$1$}}
\put(451,747){\makebox(0,0)[b]{$2$}}
\put(525,747){\makebox(0,0)[b]{$3$}}
\put(448,720){\makebox(0,0)[b]{$(\Delta(K),\Delta(L))$}}
\put(149,740){\circle{8}}
\put( 75,740){\circle{8}}
\put(236,740){\circle*{8}}
\put(232,740){\line(-1, 0){ 79}}
\put(149,747){\makebox(0,0)[b]{$2$}}
\put( 75,747){\makebox(0,0)[b]{$1$}}
\put(236,747){\makebox(0,0)[b]{$3$}}
\put(148,720){\makebox(0,0)[b]{$(K,L)$}}
\end{picture}
\end{center}
\caption{Example~\ref{ex:pardue}}\label{fg:pardue}
\end{figure}
But then it is easy to see that
$(\Delta(K),\Delta(L))$ has non-trivial relative homology in
dimensions $0$ and $1$, while $(K,L)$ has no non-trivial relative
homology.

Thus, the relative Betti numbers of $(\Delta(K),\Delta(L))$ are all at
least as large as those of $(K,L)$.  Theorem~\ref{th:main} shows that
this is true for any pair $(K,L)$.
\end{ex}

Algebraic shifting is the exterior algebra analogue of generic initial
ideals and Gr\"obner bases in commutative algebra, in the following
way.  If $I_K$ were instead a monomial ideal of a {\em polynomial}\
ring, then the algorithm used to create the list of non-faces of
$\Delta(K)$ would instead create a list of monomials generating the
generic initial ideal of $I_K$, denoted $\Gin(I_K)$.  For further
details of generic initial ideals, see, for
instance~\cite[Section~15.9]{Eisenbud}.  For more about the
relationship between generic initial ideals and algebraic shifting,
see~\cite{HeTe}.  For a more general exterior algebra version of
Gr\"obner bases and generic initial ideals,
see~\cite[Section~1]{AHH:Gotzmann}.

Theorem~\ref{th:main} bears some resemblance to results about generic
initial ideals (Section~\ref{se:alg.shift}).  For instance,
Hulett~\cite[proof of Lemma~1.24]{Hulett:thesis},~\cite[p.~2338]{Hulett} 
and Bigatti~\cite[proof of Theorem~3.7]{Bigatti} have shown that for
any homogeneous ideal $I$ in a polynomial ring, the free resolution
Betti numbers of its generic initial ideal $\Gin(I)$ are at least as
large as those of $I$.

\section{Relative homology}\label{se:rel.hom}

In order to say anything about $(\Delta(K),\Delta(L))$, we must first
consider $(K,L)$.  For $Q=K-L$ (the ``$Q$'' is for ``quotient''), we
define $\Delta(Q)=\Delta(K)-\Delta(L)$.  This is primarily a
combinatorial definition, with the algebra hidden in the computation
of $\Delta(K)$ and $\Delta(L)$.  We now examine how to interpret
$\Delta(Q)$ algebraically.  Let
$$\imt{Q}=\spn\{\ime{F}\colon F \in Q\}.$$
It is not hard to see, then, that we may algebraically shift
the subcomplex $L$ using $\Lambda[K]$ instead of $\Lambda[L]$, by
modding out by $\imt{Q}$ on $\Lambda[K]$ instead of by $I_L$ on
$\Lambda[L]$, since $\imt{Q}=\imt{I_L}$ (see~\cite[Section~3]{art:relative}).

Lemmas~\ref{th:gamma.exist} and~\ref{th:gamma.basis} show 
how $\Delta(Q)$ is related to $\imt{Q}$, namely
that $\Delta(Q)$ indexes a nice basis of $\imt{Q}$;
the construction is motivated by Gr\"obner basis ideas.  Then, guided
by earlier results about $\imt{Q}$ (summarized here as
Lemma~\ref{th:im.ker}), we use this basis of $\imt{Q}$ in
Lemmas~\ref{th:Sigma.top} and~\ref{th:Sigma.bottom} to compare key
subspaces of $\rhom(K,L)$ and $\rhom(\Delta(K),\Delta(L))$.

\begin{lemma}\label{th:gamma.exist}
If $F \in \Delta(Q)$, then there is a unique linear combination
$\sum_{\condns{G <_L F}{G \in \Delta(L)}} a_G \imf{G}$, such that 
$\imf{F}-\sum_{\condns{G <_L F}{G \in \Delta(L)}} a_G \imf{G} \in
\imt{Q}$.
\end{lemma}

\begin{proof}
Since $F \in \Delta(Q)$, and hence $F \not\in \Delta(L)$, we have
\begin{equation}\label{eq:normal.form}
\imf{F}-\sum_{G <_L F} a_G \imf{G} \in I_L = \imt{Q}
\end{equation}
for some $a_G$.  We may iterate this process on the $\imf{G}$'s for
which $G \not\in \Delta(L)$, replacing {\em them} by lexicographically
earlier linear combinations that are equal modulo $I_L=\imt{Q}$
until every $G$ in equation~\eqref{eq:normal.form} is in 
$\Delta(L)$.  
This eventually terminates, since lexicographic order is a total order.
(In Gr\"obner basis theory, this procedure is known as finding the
normal form~\cite[Definition~2.1.3]{AdLou}.)

To show these $a_G$ are unique, assume that also
\begin{equation}\label{eq:gamma.unique.2}
\imf{F}-\sum_{\condns{G <_L F}{G \in \Delta(L)}} b_G \imf{G} \in
\imt{Q}.
\end{equation}
Then by subtracting equation~\eqref{eq:gamma.unique.2} from
equation~\eqref{eq:normal.form}, we get
\begin{equation}\label{eq:gamma.unique.3}
\sum_{\condns{G <_L F}{G \in \Delta(L)}} (b_G - a_G) \imf{G} \in
\imt{Q}.
\end{equation}

If any $b_G - a_G$ in equation~\eqref{eq:gamma.unique.3} is non-zero,
let $G_0$ index the lexicographically last of these; then 
$$(a_{G_0}-b_{G_0})\imf{G_0}
 -\sum_{\condns{G <_L G_0}{G \in \Delta(L)}} (b_G-a_G) \imf{G} \in
\imt{Q},$$ and $$\imf{G_0} -\sum_{\condns{G <_L G_0}{G \in
\Delta(L)}} \left(\frac{b_G-a_G}{a_{G_0}-b_{G_0}}\right) \imf{G} \in
\imt{Q},$$
which contradicts $G_0 \in \Delta(L)$.
\end{proof}

\begin{defn}
By Lemma~\ref{th:gamma.exist}, we may define, for any $F \in
\Delta(Q)$, $\img{F}$ supported on $\Delta(L)$ such that 
$\imf{F}-\img{F} \in \imt{Q}$.
\end{defn}

\begin{lemma}\label{th:gamma.basis}
$\{\imf{F}-\img{F}\colon F \in \Delta(Q)\}$ is a basis of $\imt{Q}$.
\end{lemma}

\begin{proof}
We first show that $\{\imf{F}-\img{F}\colon F \in \Delta(Q)\}$ is
linearly independent.  Assume otherwise; 
\begin{equation}\label{eq:gamma.ind}
\sum_{F \in \Delta(Q)} b_F(\imf{F}-\img{F})=0,
\end{equation}
where $b_{F_0} \neq 0$ for some $F_0 \in \Delta(Q)$.  When expanding
the sum on the left-hand side of equation~\eqref{eq:gamma.ind} in the
$\{\imf{F}\colon F \in \Delta(K)\}$ basis, the coefficient of
$\imf{F_0}$ will be $b_{F_0} \neq 0$, since the $\img{F}$ are all
supported on $\Delta(L)$, and so cannot cancel $\imf{F_0}$.  So
$\{\imf{F}-\img{F}\colon F \in \Delta(Q)\}$ is a set of $\abs{\Delta(Q)}$
linearly independent vectors in $\imt{Q}$.

On the other hand, $\imt{Q}$ is a
$\abs{K-L}=\abs{\Delta(Q)}$-dimensional vector space, so
$\{\imf{F}-\img{F}\colon F \in \Delta(Q)\}$ must be a basis.
\end{proof}

Now we see how $\imt{Q}$ can help compute homology and relative homology.
We adopt the shorthand $$\delta^{-1}\imt{Q}=
\{\imt{x} \in \Lambda[K]\colon \delta \imt{x} \in \imt{Q}\}.$$

\begin{lemma}\label{th:im.ker}
For any pair of simplicial complexes $L \subseteq K$,
\begin{alph-list}
\item\label{it:Gamma}
$\rbeti{j}(L)=\dim 
((\delta^{-1}\imt{Q})/(\im \delta + \imt{Q}))_j$; and
\item\label{it:Sigma} 
$\rbeti{j}(K,L)=\dim
((\ker \delta \cap \imt{Q})/(\delta \imt{Q}))_j$.
\end{alph-list}
\end{lemma}

\begin{proof}
This is~\cite[Lemmas 2 and 4]{art:relative}, where the notation
$\Lambda[\Sigma]$ was used in place of $\imt{Q}$.
\end{proof}

Lemma~\ref{th:im.ker}\ref{it:Sigma} suggests that in order to compute
$\rbeti{j}(K,L)$, we examine $\ker \delta \cap \imt{Q}$ and
$\delta\imt{Q}$.  However, $\im \delta \cap \imt{Q}$ turns out to be
easier to handle than $\ker \delta \cap \imt{Q}$.  The next two lemmas
compare $\im \delta \cap \imt{Q}$ and $\delta \imt{Q}$ to
subspaces of $\imt{Q}$ indexed by combinatorially defined sets of
$\Delta(Q)$. These two comparisons will combine to prove the key
inequality in the proof of Theorem~\ref{th:main}.

\begin{lemma}\label{th:Sigma.top}
$\im \delta \cap \imt{Q} \subseteq 
	\spn \{\imf{1 \disun F}-\img{1 \disun F}\colon
		1 \not\in F,\nd 1 \disun F \in \Delta(Q)\}$.
\end{lemma}

\begin{proof}
Let $\imt{x} \in \im \delta \cap \imt{Q}$.  By
Lemma~\ref{th:gamma.basis}, we can write
\begin{equation}\label{eq:supp.Sigma}
\imt{x} = \sum_{G \in \Delta(Q)} a_G (\imf{G}-\img{G})
\end{equation}
uniquely, since $\imt{x}\in\imt{Q}$.  Similarly, 
by~\cite[equation~(3.5)]{BjKal:1}, we can also write
\begin{equation}\label{eq:supp.1}
%\imt{x}=\sum_{1 \disun F \in \Delta(K)} b_F \imf{1 \disun F}
\imt{x}=\sum_{\condns{1 \not\in F}{1 \disun F \in \Delta(K)}} 
		b_F \imf{1 \disun F}
\end{equation}
uniquely, since $\imt{x}\in\im \delta$.  Now, by definition, the
support of $\img{G}$ is entirely on $\Delta(L)$.  Of course, the
support of $\imt{x}$ in $\Delta(Q)$ must be the same in
equations~\eqref{eq:supp.Sigma} and~\eqref{eq:supp.1},
so we must be able to write every $G \in \Delta(Q)$ such that $a_G
\neq 0$ as $G=1 \disun F$ for some $F$.  Therefore,
equation~\eqref{eq:supp.Sigma} can be rewritten as
$$\imt{x} = \sum_{\condns{1 \not\in F}{1 \disun F \in \Delta(Q)}} 
		a_{1 \disun F} (\imf{1 \disun F}-\img{1 \disun F}),$$
implying the lemma.
\end{proof}

\begin{lemma}\label{th:Sigma.bottom}
There is a subspace $\imt{Q'}$ of $\imt{Q}$ such that
$$\dim \delta \imt{Q'} = \abs{ \{F \in \Delta(Q)\colon
	1 \not\in F, \nd 1 \disun F \in \Delta(Q)\}}.$$
\end{lemma}

\begin{proof}
Let $\imt{Q'}=\spn \{\imf{F}-\img{F}\colon
		F \in \Delta(Q), \nd 1 \not\in F, \nd
		1 \disun F \in \Delta(Q)\}$.  
First note that by definition of $\img{F}$ (and $F \in \Delta(Q)$),
each $\imf{F}-\img{F} \in \imt{Q}$, so $\imt{Q'}$ is a subspace of
$\imt{Q}$.  Clearly, we only need to show that 
$\{\delta(\imf{F}-\img{F})\colon
		F \in \Delta(Q), \nd 1 \not\in F, \nd
		1 \disun F \in \Delta(Q)\}$
is linearly independent.

By definition of $\img{F}$ and Lemma~\ref{th:gamma.exist}, we may
write each
$$\imf{F}-\img{F}=\imf{F}-
  \sum_{\condns{G<_L F}{G\in\Delta(L)}} b_{F,G}\imf{G}$$
for some $b_{F,G}$'s.
Furthermore, we are assuming $1 \disun F \in \Delta(Q)$ for each $F$,
so $1 \disun F \in \Delta(K)$, and thus $\delta \imf{F}=\imf{1 \disun F}$.
For each $G <_L F$, if $1 \in G$, then $\delta\imf{G}=0$;  otherwise 
$1 \disun G <_L 1 \disun F \in \Delta(K)$, so $1 \disun G \in
\Delta(K)$, and $\delta \imf{G}=\imf{1\disun G}$.  Therefore
$$\delta(\imf{F}-\img{F})=\imf{1 \disun F}-
  \sum_{\condns{G<_L F}{1 \not\in G, \nd G\in\Delta(L)}} 
		b_{F,G}\imf{1 \disun G}.$$

To show that $\{\delta(\imf{F}-\img{F})\colon
		F \in \Delta(Q), \nd 1 \not\in F, \nd
		1 \disun F \in \Delta(Q)\}$
is linearly independent, assume
\begin{equation}\label{eq:Sigma.ind}
0=\sum_{\condns{F \in \Delta(Q)}{1 \not\in F,\nd 1 \disun F \in
\Delta(Q)}} c_F(\imf{1 \disun F} - 
  \sum_{\condns{G <_L F}{1 \not\in G, \nd G \in \Delta(L)}}
    b_{F,G}\imf{1 \disun G}).
\end{equation}
Now, $f_{1 \disun G}$'s appearing in equation~\eqref{eq:Sigma.ind} all
satisfy $G\in \Delta(L)$, while all the $\imf{1 \disun F}$'s satisfy 
$F \in \Delta(Q)$, so there is no cancellation between the 
$\imf{1 \disun G}$'s and the $\imf{1 \disun F}$'s.  But all the 
$\imf{1 \disun F}$'s are distinct members of the 
$\{\imf{H}\colon H \in \Delta(K)\}$ basis, so there is no cancellation
among the $\imf{1 \disun F}$'s.  Therefore all the $c_F$'s must be
zero, and the $\delta(\imf{F}-\img{F})$'s are linearly independent.
\end{proof}

\section{Proof of main theorem}\label{se:proof}
We start with an easy lemma.
\begin{lemma}\label{th:KIJ}
If $I$, $J$, and $K$ are subspaces of a vector space and $I \subseteq
K$, then
$$\dim (K/I) 
= \dim ((K \cap J)/(I \cap J))
+ \dim ((K + J)/(I + J)).$$
\end{lemma}

\begin{proof}
Simply expand the right-hand side as
\begin{multline*}
(\dim (K \cap J)-\dim (I \cap J))
+((\dim K + \dim J - \dim (K \cap J)) \\ - 
  (\dim I + \dim J - \dim (I \cap J)))
\end{multline*}
by the standard vector space argument
$\dim (A + B) = \dim A + \dim B - \dim (A \cap B)$, applied twice.
This expression then easily simplifies to 
$\dim K - \dim I = \dim (K/I)$.
\end{proof}

\begin{thm}\label{th:main}
For any pair of simplicial complexes $L \subseteq K$,
$$\rbeti{j}(K,L) \leq \rbeti{j}(\Delta(K),\Delta(L))$$
for all $j$.
\end{thm}

\begin{proof} 
Because $\Delta(K)$ and $\Delta(L)$ are shifted, and therefore
near-cones with apex $1$, we may use equations~\eqref{eq:beta.shift}
and~\eqref{eq:pair.near-cones} to compute the homology of $\Delta(K)$,
$\Delta(L)$, and  $(\Delta(K),\Delta(L))$.
The sets in these equations overlap in a nice way.  In particular, if
we let
\begin{align*}
C_{KQ} &= \{F \in \Delta(Q)\colon 1 \not\in F,\nd 
		1 \disun F \not\in \Delta(K)\},\\
C'_{LQ} &= \{G \in \Delta(Q)\colon 1 \in G,\nd 
		G-1 \in \Delta(L)\},\\
C_{LQ} &= \{F \in \Delta(L)\colon 1 \not\in F,\nd 
		1 \disun F \in \Delta(Q)\},\ {\rm and}\\
%\intertext{and}
C_{KL} &= \{F \in \Delta(L)\colon 1 \not\in F,\nd 
		1 \disun F \not\in \Delta(K)\},
\end{align*}
then it is not hard to see, from equation~\eqref{eq:beta.shift}, that
\begin{align*}
\rbeti{j}(\Delta(K))&=\abs{(C_{KQ})_j}+\abs{(C_{KL})_j},\\
\rbeti{j}(\Delta(L))&=\abs{(C_{LQ})_j}+\abs{(C_{KL})_j},\\
\intertext{and, from equation~\eqref{eq:pair.near-cones}, that}
\rbeti{j}(\Delta(K),\Delta(L))&=\abs{(C_{KQ})_j}+\abs{(C'_{LQ})_j}.\\
\end{align*}
(We name these sets ``$C$'' because they are combinatorial.)
An easy bijection ($F \leftrightarrow 1 \disun F = G$) shows that
$$\abs{(C_{LQ})_j}=\abs{(C'_{LQ})_{j+1}}.$$
Continuing the analogy begun at the end of Section~\ref{se:scx}
between formulas for homology of near-cones and the long exact
sequence~\eqref{eq:les}, $C_{KQ}$ corresponds to $\im \pi_*$, 
$C_{LQ}$ and $C'_{LQ}$ correspond to $\im \partial_*$, and
$C_{KL}$ corresponds to $\im i_*$.

We can find ``corresponding'' subspaces in $\Lambda[K]$; define
\begin{align*}
A_{KQ}&=(\ker \delta \cap \imt{Q})/(\im \delta \cap \imt{Q}),\\
A'_{LQ}&=(\im \delta \cap \imt{Q})/(\delta \imt{Q}),\\
A_{LQ}&=(\delta^{-1}\imt{Q})/(\ker \delta + \imt{Q}),\ {\rm and}\\
%\intertext{and}
A_{KL}&=(\ker \delta + \imt{Q})/(\im \delta + \imt{Q}).
\end{align*}
(We name these spaces ``$A$'' because they are algebraic.)
Then by Lemma~\ref{th:KIJ}, 
\begin{align*}
\rbeti{j}(K)&=\dim (A_{KQ})_j + \dim (A_{KL})_j;\\
\intertext{by Lemma~\ref{th:im.ker},}
\rbeti{j}(L)&=\dim (A_{LQ})_j + \dim (A_{KL})_j,\ {\rm and}\\
\rbeti{j}(K,L)&=\dim (A_{KQ})_j +\dim (A'_{LQ})_j;
\end{align*}
and, by~\cite[Lemma~5]{art:relative},
$$ (A_{LQ})_j \cong (A'_{LQ})_{j+1}.$$


We will show how the dimension of each $A$ subspace compares with the
cardinality of the corresponding $C$ set with the same subscript.
Because algebraic shifting preserves homology,
\begin{align}
 \dim (A_{LQ})_j +\dim (A_{KL})_j = \rbeti{j}(L) &= \rbeti{j}(\Delta(L))
=\abs{(C_{LQ})_j}+\abs{(C_{KL})_j} \label{eq:new.1}\\
\intertext{and}
 \dim (A_{KQ})_j +\dim (A_{KL})_j = \rbeti{j}(K) &= \rbeti{j}(\Delta(K))
=\abs{(C_{KQ})_j}+\abs{(C_{KL})_j}. \label{eq:new.2}
\end{align}
%
By Lemma~\ref{th:Sigma.top}, 
\begin{align*}
\dim (\im \delta \cap \imt{Q})_{j+1} &\leq
  \abs{\{F \in \Delta(K)_{j}\colon 1 \not\in F, \nd 1 \disun F \in\Delta(Q) \}},\\
\intertext{and by Lemma~\ref{th:Sigma.bottom},}
\dim (\delta \imt{Q})_{j+1} &\geq \dim (\delta \imt{Q'})_{j+1}\\ &=
 \abs{\{F \in \Delta(Q)_{j}\colon 1 \not\in F, \nd 1 \disun F \in\Delta(Q) \}}.
\end{align*}
(The index shift, of $j+1$ to $j$, in the above inequalities arises
because the $(j+1)$-dimensional basis elements for $\im \delta \cap
\imt{Q}$ and $\delta\imt{Q'}$ are the $(j+1)$-dimensional elements
$\imf{1\disun F} - \img{1\disun F}$ and $\delta(\imf{F} - \img{F})$,
respectively, each of which is $(j+1)$-dimensional precisely when $F$
is $j$-dimensional.)
Since $\Delta(L)$ is the complement of $\Delta(Q)$ with respect to
$\Delta(K)$, then,
\begin{align*}%\label{eq:star}
\dim (A'_{LQ})_{j+1} &= \dim ((\im \delta \cap \imt{Q})/(\delta\imt{Q}))_{j+1}
= \dim (\im \delta \cap \imt{Q})_{j+1} - \dim (\delta\imt{Q})_{j+1}
					\notag\\
 &\leq \abs{\{F \in \Delta(L)_{j}\colon 
	1 \not\in F, \nd 1 \disun F \in\Delta(Q)\}} \notag\\
 &= \abs{(C_{LQ})_{j}},
\end{align*}
and so
$$\dim (A_{LQ})_j = \dim (A'_{LQ})_{j+1} \leq
                    \abs{(C_{LQ})_j} = \abs{(C'_{LQ})_{j+1}}$$

%\begin{align*}
%\dim (A_{LQ})_j &\leq \abs{(C_{LQ})_j}. \notag\\
%\intertext{Equation~\eqref{eq:new.1} then implies}
Equation~\eqref{eq:new.1} then implies
\begin{align*}
\dim (A_{KL})_j &\geq \abs{(C_{KL})_j},\\
\intertext{so by equation~\eqref{eq:new.2},}
\dim (A_{KQ})_j &\leq \abs{(C_{KQ})_j},\\
\intertext{and so finally}
\rbeti{j}(K,L)=\dim (A_{KQ})_j +\dim (A'_{LQ})_j &\leq 
               \abs{(C_{KQ})_j}+\abs{(C'_{LQ})_j} 
  = \rbeti{j}(\Delta(K),\Delta(L)).
\end{align*}
\end{proof}

\subsection*{Acknowledgements}
I gratefully acknowledge help from conversations with Keith Pardue,
Frank Sottile, and Eric Babson.

\begin{thebibliography}{AHH}

\bibitem[AL]{AdLou} W.~Adams and P.~Loustaunau,
			{\em An Introduction to Gr\"obner Bases},
			Graduate Studies in Mathematics {\bf 3},
			American Mathematical Society, Providence, RI, 1994.

\bibitem[AHH]{AHH:Gotzmann} A. Aramova, J. Herzog, T. Hibi,
			``Gotzmann theorems for exterior algebras and
				combinatorics,''
			{\em J. Alg.}\ {\bf 191} (1997), 174--211.

\bibitem[Bi]{Bigatti} A.~Bigatti,
			``Upper bounds for the Betti numbers of
				a given Hilbert function,''
			{\em Comm.\ Alg.}\
				{\bf 21} (1993), 2317--2334.

\bibitem[BK1]{BjKal:1} A.~Bj\"{o}rner and G.~Kalai,
			``An extended Euler-Poincar\'{e} theorem,''
			{\em Acta Math.}\ {\bf 161} (1988), 279--303.

\bibitem[BK2]{BjKal:NYAS} A.~Bj\"orner and G.~Kalai,
                        ``On $f$-vectors and homology,'' in
                        {\em Combinatorial Mathematics: Proceedings of
                                the Third International Conference}
%                               New York, 1985},
                        (G.~Bloom, R.~Graham, J.~Malkevitch, eds.);
                        {\em Ann.\ N. Y. Acad.\ Sci.}\
                                {\bf 555} (1989), 63--80.
%
%                       International Conference on Combinatorial Mathematics
%                               (3rd: 1985: New York, NY), ``author''

\bibitem[Du]{art:relative} A.~Duval,
			``On $f$-vectors and relative homology,''
			{\em J. Alg.\ Comb.}, to appear.

\bibitem[Ei]{Eisenbud} D. Eisenbud, 
			{\em Commutative Algebra with a View Towards
				Algebraic Geometry},
			Spinger-Verlag, New York, 1995.

\bibitem[HT]{HeTe} J. Herzog and N. Terai, 
			``Stable properties of algebraic shifting,''
			preprint, 1998.

\bibitem[Hu1]{Hulett:thesis} H.~Hulett, 
			{\em Maximum Betti Numbers for a Given
				Hilbert Function}, 
			Ph.\ D. thesis, University of Illinois at
				Urbana-Champaign, 1993.
\bibitem[Hu2]{Hulett} H.~Hulett,
			``Maximum Betti numbers for a given Hilbert function,''
			{\em Comm.\ Alg.} {\bf 21} (1993), 2335--2350.

\bibitem[Ka1]{Kal:Eck} G.~Kalai,
                        ``Characterization of $f$-vectors of families
                                of convex sets in $\numsys{R}^d$, Part I:
                                Necessity of Eckhoff's conditions,''
                        {\em Israel J. Math.}\ {\bf 48} (1984), 175--195.

\bibitem[Ka2]{Kal:AS} G.~Kalai,
			Algebraic Shifting, 
			unpublished manuscript (July 1993 version).

\bibitem[Mu]{Mu} J.~Munkres,
			{\em Elements of Algebraic Topology},
			Benjamin/Cummings, Menlo Park, CA, 1984.	

\bibitem[St1]{St:TV} R.~Stanley,
			``Generalized $h$-vectors, intersection
				cohomology of toric varieties,
				and related results,'' in 
			{\em Commutative Algebra and Combinatorics}
			(M. Nagata and H. Matsumura, eds.), 
			Advanced Studies in Pure Mathematics {\bf 11},
				Kinokuniya, Tokyo, and North-Holland, 
				Amsterdam/New York, 1987, 
			187--213.

\bibitem[St2]{St:CCA} R.~Stanley,  
			{\em Combinatorics and Commutative Algebra,
				2nd ed.},
			Birkh\"auser, Boston, 1996.

\end{thebibliography}


\end{document}
