%an AMSLaTeX file (using LaTeX2e) for a 14 page document \documentclass[12pt]{article} \usepackage{amsmath, amsthm} \textwidth6.5truein \textheight8.5truein \topmargin-0.5truein \oddsidemargin+0.2truein \baselineskip0.20truein \newtheorem{thm}{Theorem}[section] \newtheorem{lemma}[thm]{Lemma} \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}} \theoremstyle{remark} \newtheorem*{rmk}{Remark} %------------------------- \newcounter{alphcount} \renewcommand{\thealphcount}{(\alph{alphcount})} \newenvironment{alph-list}{\begin{list}{\thealphcount}{\usecounter{alphcount}}}% {\end{list}} %--macros %general, non-math \newcommand{\ie}{{\em i.e.}} \newcommand{\eg}{{\em e.g.}} \newcommand{\dfn}[1]{{\bf {#1}}} %\newcommand{\idfn}[1]{{\sl {#1}}} \newcommand{\idfn}[1]{#1} \newcommand{\abs}[1]{|#1|} %words \newcommand{\scx}{simplicial complex} \newcommand{\cx}{complex} \hyphenation{Co-hen-Ma-cau-lay Co-hen-Ma-cau-lay-ness} \newcommand{\CM}{Cohen-Macaulay} %\newcommand{\pcm}{pure \CM} \newcommand{\pcm}{\CM} \newcommand{\relcm}{relative \CM} \newcommand{\seqcm}{sequentially \CM} \newcommand{\seqlcmness}{sequential \CM ness} %general, math \newcommand{\disun}{\mathbin{\dot{\cup}}} %from Mark Purtill \newcommand{\numsys}[1]{{\bf #1}} \renewcommand{\colon}{{:}\;} \newcommand{\maps}{\rightarrow} \newcommand{\revimplies}{\impliedby} \newcommand{\lrimplies}{\iff} \newcommand{\rhomi}[1]{\widetilde{H}_{#1}} \newcommand{\homi}[1]{H_{#1}} \newcommand{\nd}{\;} %''and'' in series of conditions \newcommand{\sh}[1]{\Delta(#1)} \newcommand{\skel}[2]{^{(#1, #2)}} \newcommand{\dm}[1]{^{(#1)}} \newcommand{\dg}[1]{^{<#1>}} %\newcommand{\dd}[1]{\skel{#1}{#1}} \newcommand{\dd}[1]{^{[#1]}} \newcommand{\two}[3]{(#1\dd{#2})\dm{#3}} \newcommand{\less}{\backslash} \newcommand{\hh}{\boldsymbol h} \newcommand{\ff}{\boldsymbol f} %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{\wedgesubseq}[4]{#1_{#2_#3} \wedge \dots \wedge #1_{#2_#4}} %alg shifting stuff \newcommand{\kk}{\boldsymbol k} \newcommand{\dimk}{\dim_{\kk}} \newcommand{\kV}{\kk V} \newcommand{\imt}[1]{\tilde{#1}}%''IMage-Tilde'' \newcommand{\imf}[1]{\tilde{f}_{#1}}%''IMage-Tilde'' -- f-variation \newcommand{\collC}{{\mbox{$\cal C$}}} %\rm in math \DeclareMathOperator{\link}{lk} \newcommand{\lk}[2]{\link_{#1}#2} \newcommand{\degk}[2]{\deg_{#1} #2} \DeclareMathOperator{\spn}{span} \DeclareMathOperator{\initial}{init} \newcommand{\init}[1]{\initial(#1)} \begin{document} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 3 (1996), \#R21\hfill} \thispagestyle{empty} \title{ Algebraic Shifting and Sequentially Cohen-Macaulay Simplicial Complexes} \author{Art M. Duval\\ University of Texas at El Paso\\ Department of Mathematical Sciences\\ El Paso, TX 79968-0514\\ {\tt artduval@math.utep.edu}} \date{Submitted: February 2, 1996;\\ Accepted: July 23, 1996.} \maketitle \begin{abstract} Bj\"orner and Wachs generalized the definition of shellability by dropping the assumption of purity; they also introduced the {\sl $h$-triangle}, a doubly-indexed generalization of the $h$-vector which is combinatorially significant for nonpure shellable complexes. Stanley subsequently defined a nonpure simplicial complex to be {\sl sequentially Cohen-Macaulay} if it satisfies algebraic conditions that generalize the Cohen-Macaulay conditions for pure complexes, so that a nonpure shellable complex is sequentially Cohen-Macaulay. We show that algebraic shifting preserves the $h$-triangle of a simplicial complex $K$ if and only if $K$ is sequentially Cohen-Macaulay. This generalizes a result of Kalai's for the pure case. Immediate consequences include that nonpure shellable complexes and sequentially Cohen-Macaulay complexes have the same set of possible $h$-triangles. {\bf 1991 Mathematics Subject Classification:} Primary 06A08; Secondary 52B05. \end{abstract} \section{Introduction}\label{se:intro} A \scx\ is \idfn{pure} if all of its facets (maximal faces, ordered by inclusion) have the same dimension. \CM ness, algebraic shifting, shellability, and the $h$-vector are significantly interrelated for pure \scx es. We will be concerned with extending some of these relations to nonpure \cx es, but first, we briefly review the pure case. More detailed definitions are in later sections. A \scx\ is \idfn{\CM} if its face-ring is a \CM\ ring (an algebraic property), or, equivalently, if the \cx\ satisfies certain topological conditions (see, \eg,~\cite{St:NYAS,St:CCA2}). In particular, the complex must be pure. A pure \scx\ is \idfn{shellable} if it can be constructed one facet at a time, subject to certain conditions (see, \eg,~\cite{Bj:pure.shell,BjW:pure.shell}). A shellable \cx\ is \CM, and the \idfn{$h$-vector} of a \CM\ or shellable \cx\ has natural combinatorial interpretations. \idfn{Algebraic shifting} is a procedure that defines, for every \scx\ $K$, a new \cx\ $\sh{K}$ with the same $h$-vector as $K$ and a nice combinatorial structure ($\sh{K}$ is \idfn{shifted}). Additionally, algebraic shifting preserves many algebraic and topological properties of the original complex, including \CM ness; a \scx\ is \CM\ if and only if $\sh{K}$ is \CM, which, in turn, holds if and only if $\sh{K}$ is pure. Thus, it is easy to tell whether $K$ is \CM, if $\sh{K}$ is known. (See, \eg,~\cite{BjKal,BjKal:NYAS}.) Now we are ready for the nonpure case. Bj\"orner and Wachs' generalization of shellability to nonpure \scx es, made by simply dropping the assumption of purity~\cite{BjW,BjW:II}, generated a great deal of interest, and sparked the generalization of several other related concepts~\cite{SuWa,SuWe,BjSa,art:ithom}. In particular, Stanley introduced \idfn{\seqlcmness}~\cite[Section~III.2]{St:CCA2}, a nonpure generalization of \CM ness, and designed the (algebraic) definition so that a nonpure shellable \cx\ is \seqcm, much as a shellable \cx\ is \CM. Meanwhile, joint work with L.~Rose~\cite{art:ithom} shows that algebraic shifting preserves the $h$-triangle (a nonpure generalization of the $h$-vector) of nonpure shellable \cx es. These developments prompted A.~Bj\"orner (private communication) to ask, ``Does algebraic shifting preserve \seqlcmness?''\ and ``Does algebraic shifting preserve the $h$-triangle of \seqcm\ \scx es?'' Shifted \cx es are nonpure shellable and hence \seqcm, so $\sh{K}$ is always \seqcm. Thus, the ``obvious'' generalization, ``$K$ is \seqcm\ if and only if $\sh{K}$ is \seqcm,'' is trivially false. Bj\"orner's first question may be restated as, ``Can one use $\sh{K}$ to tell if a \scx\ $K$ is \seqcm?'' Our main result is to answer both of Bj\"orner's questions simultaneously, by showing that algebraic shifting preserves the $h$-triangle of a \scx\ if and only if the \cx\ is \seqcm\ (Theorem~\ref{th:big}). In Section~\ref{se:degree}, we introduce basic definitions, including the $f$-triangle and the $h$-triangle. \CM ness and \seqlcmness\ are discussed in Section~\ref{se:cm}, and algebraic shifting in Section~\ref{se:alg.shift}. In Section~\ref{se:proof}, we prove our main result. Finally, Section~\ref{se:h-tri} contains two corollaries concerning nonpure shellability and iterated Betti numbers (a nonpure generalization of homology Betti numbers), and a conjecture on partitions of \seqcm\ \cx es. \section{Degree and dimension}\label{se:degree} We start with some basic definitions that are used throughout. A \dfn{\scx} $K$ is a collection of finite sets (called faces) such that $F \in K$ and $G \subseteq F$ together imply that $G \in K$. We allow $K$ to be the empty \scx\ $\emptyset$ consisting of no faces, or the \scx\ $\{\emptyset\}$ consisting of just the empty face, but we do distinguish between these two cases. A \dfn{subcomplex} of $K$ is a subset of faces $L \subseteq K$ such that $F \in L$ and $G \subseteq F$ imply $G \in L$. A subcomplex is a \scx\ in its own right. An \dfn{order filter} of $K$ is a subset of faces $J \subseteq K$ such that $F \in J$ and $F \subseteq G \in K$ imply $G \in J$. The \dfn{dimension} of a face $F \in K$ is $\dim F = \abs{F} - 1$, and the \dfn{dimension} of $K$ is $\dim K = \max\{\dim F\colon F \in K\}$. The maximal faces of $K$ (under the set inclusion partial order) are called \dfn{facets}, and $K$ is \dfn{pure} if all of its facets have the same dimension. Following~\cite{BjW}, we define the \dfn{degree} of a face $F \in K$ to be $\degk{K}{F} = \max\{\abs{G} \colon F \subseteq G \in K\}$. We further define the \dfn{degree} of $K$ to be $\deg K = \min\{\degk{K}{F}\colon F \in K\}$. Note that $K$ is pure if and only if all of its faces have the same degree. \begin{defncite}{Bj\"orner-Wachs} Let $K$ be a \scx, and let $-1 \leq r, s \leq \dim K$. Then~\cite[Definition~2.8]{BjW} $$K\skel{r}{s}=\{F \in K\colon \dim F \leq s,\ \degk{K}{F} \geq r+1\}.$$ We may extend this by defining $K\skel{r}{s}$ to be the empty \scx\ when $r > \dim K$. \end{defncite} Clearly, $K\skel{r}{s}$ is a subcomplex of $K$. We will frequently make use of the following special cases, the latter two first considered (though not named) in~\cite{BjW}: $K\dm{s}=K\skel{-1}{s}$, the \dfn{$s$-skeleton} of $K$; $K\dg{r}=K\skel{r}{\dim K}$, the \dfn{$r$th sequential layer}, the subcomplex of all faces of $K$ whose degree is at least $r+1$ (equivalently, the subcomplex generated by all facets whose dimension is at least $r$); and $K\dd{i}=K\skel{i}{i}$, the \dfn{pure $i$-skeleton}, the pure subcomplex generated by all $i$-dimensional faces. The notation $K\dd{i}$ is due to Wachs~\cite{Wa}. Other interpretations of $K\skel{r}{s}$, then, are that $K\skel{r}{s}=(K\dg{r})\dm{s}$ and, if $r \geq s$, that $K\skel{r}{s}=\two{K}{r}{s}$. \begin{lemma}\label{th:deg.subcx} Let $L \subseteq K$ be a pair of \scx es. \begin{alph-list} \item\label{it:deg.subcx.a} If $\deg L \geq i+1$, then $L \subseteq K\dg{i}$. \item\label{it:deg.subcx.b} $L\dg{i} \subseteq K\dg{i}$. \end{alph-list} \end{lemma} \begin{proof} \ref{it:deg.subcx.a}: Let $F \in L$. Because $\degk{L}{F} \geq i+1$, there is a face $G \in L$ of dimension at least $i$ containing $F$. But $G \in K$, too, so $\degk{K}{F} \geq i+1$. Therefore, every face $F \in L$ has degree at least $i+1$ in $K$ as well. \ref{it:deg.subcx.b}: Clearly, $L\dg{i} \subseteq L \subseteq K$ and $\deg L\dg{i} \geq i+1$, so by~\ref{it:deg.subcx.a}, $L\dg{i} \subseteq K\dg{i}$. \end{proof} Let $K_j$ denote the set of $j$-dimensional faces of $K$. The \dfn{$f$-vector} of $K$ is the sequence $f(K)=(f_{-1},\dots,f_{d-1})$, where $f_j = f_j(K) = \#K_j$ and $d-1 = \dim K$. The \dfn{$h$-vector} of $K$ is the sequence $h(K)=(h_0, \dots, h_d)$ where \begin{equation}\label{eq:f.h-vec} h_j = h_j(K) = \sum_{s=0}^j (-1)^{j-s}\binom{d-s}{j-s} f_{s-1}(K). \end{equation} Inverting equation~\eqref{eq:f.h-vec} gives $$f_j(K) = \sum_{s=0}^d \binom{d-s}{j+1-s} h_s(K),$$ so knowing the $h$-vector of a \scx\ is equivalent to knowing its $f$-vector. \begin{defncite}{Bj\"orner-Wachs} Let $K$ be a $(d-1)$-dimensional \scx. Define $$f_{i,j}=f_{i,j}(K)= \#\{F \in K\colon \degk{K}{F} = i,\ \dim F = j-1\}.$$ The triangular integer array $\ff(K)=(f_{i,j})_{0 \leq j \leq i \leq d}$ is the \dfn{$f$-triangle} of $K$. Further define \begin{equation}\label{eq:f.h-tri} h_{i,j}=h_{i,j}(K)=\sum_{s=0}^j(-1)^{j-s}\binom{i-s}{j-s} f_{i,s}(K). \end{equation} The triangular array $\hh(K)=(h_{i,j})_{0 \leq j \leq i \leq d}$ is the \dfn{$h$-triangle} of $K$~\cite[Definition~3.1]{BjW}. \end{defncite} Inverting equation~\eqref{eq:f.h-tri} gives \begin{equation}\label{eq:h.f-tri} f_{i,j}(K) = \sum_{s=0}^i \binom{i-s}{j+1-s} h_{i,s}(K), \end{equation} so knowing the $h$-triangle of a \scx\ is equivalent to knowing its $f$-triangle. If $K$ is a pure $(d-1)$-dimensional \scx, then every face has degree $d$, so $$f_{i,j}(K) = \begin{cases} f_{j-1}(K), & \text{if $i = d$,}\\ 0, & \text{if $i \neq d$} \end{cases} ,$$ and similarly for the $h$'s. Thus, when $K$ is pure, the $f$-triangle and $h$-triangle essentially reduce to the $f$-vector and $h$-vector, respectively. Clearly, \begin{equation}\label{eq:fijK.prime} f_{j-1}(K\dg{i-1})=\sum_{p=i}^{d}f_{p,j}(K) \end{equation} for all $0 \leq j, i \leq d$. Inverting equation~\eqref{eq:fijK.prime}, we get \begin{equation}\label{eq:fijK} f_{i,j}(K)=f_{j-1}(K\dg{i-1})-f_{j-1}(K\dg{i}) \end{equation} for all $0 \leq j \leq i \leq d$; this is essentially the same idea as~\cite[equation~(3.2)]{BjW}. In the case $i=d$, equation~\eqref{eq:fijK} relies upon the tail condition $f_{j-1}(K\dg{d})=f_{j-1}(\emptyset)=0$. \section{\CM ness}\label{se:cm} \CM ness is an important algebraic concept, but we will use the equivalent algebraic topological characterizations as our definitions. For all undefined topological terms, see~\cite{Mu:alg.top}; for further details on \CM ness, see~\cite{St:CCA2}. The \dfn{pair} $(K,L)$ will denote a pair of \scx es $L \subseteq K$. Let $\kk$ denote a field, fixed throughout the rest of the paper. Recall that $\rhomi{p}(K)$ refers to \dfn{reduced homology} of $K$ (over $\kk$), and $\rhomi{p}(K,L)$ denotes \dfn{reduced relative homology} of the pair $(K,L)$ (over $\kk$). For $K$ a \scx, $\rhomi{p}(K,\emptyset)=\rhomi{p}(K)$; for a pair $(K,L)$ with $L$ non-empty, $\rhomi{p}(K,L)=\homi{p}(K,L)$. The \dfn{link} of a face $F$ in a \scx\ $K$ is defined to be the subcomplex $$\lk{K}{F}=\{G \in K\colon F \cup G \in K,\ F \cap G = \emptyset\}.$$ For $L \subseteq K$ a pair of subcomplexes and $F \in K$, define the \dfn{relative link} of $F$ in $L$ to be $$\lk{L}{F}=\{G \in L\colon F \cup G \in L,\ F \cap G = \emptyset\}$$ (see Stanley~\cite[Section~5]{St:TV}). If $F \in L$, this matches the usual definition of $\lk{L}{F}$, but we now allow the possibility that $F \not\in L$, in which case $\lk{L}{F} = \emptyset$. Reisner~\cite{Reis:face.ring} showed that a \scx\ $K$ is \dfn{\pcm} (over $\kk$) if, for every $F \in K$ (including $F=\emptyset$), $\rhomi{p}(\lk{K}{F})=0$ for all $p < \dim \lk{K}{F}$; it follows that $K$ is pure. Stanley~\cite[Theorem~5.3]{St:TV} showed that a pair of \scx es $(K,L)$ is \dfn{\relcm} (over $\kk$) if and only if, for every $F \in K$ (including $F=\emptyset$), $\rhomi{p}(\lk{K}{F},\ \lk{L}{F})=0$ for all $p < \dim \lk{K}{F}$. We will take these conditions as our definitions of \CM ness and relative \CM ness, respectively. It is a well-known consequence of Reisner's condition that every skeleton of a \pcm\ \scx\ is again \pcm. \begin{lemma}\label{th:pre-L.1} Let $F$ be a face of a \scx\ $K$, and let $L$ be either the empty \scx\ or a \pcm\ subcomplex of the same dimension as $K$. Then $$\rhomi{p}(\lk{K}{F}) \cong \rhomi{p}(\lk{K}{F},\ \lk{L}{F})$$ for $p < \dim \lk{K}{F}$. \end{lemma} \begin{proof} If $\lk{L}{F}=\emptyset$ (which is always the case if $L=\emptyset$), then $\rhomi{p}(\lk{K}{F}) = \rhomi{p}(\lk{K}{F},\ \emptyset) = \rhomi{p}(\lk{K}{F},\ \lk{L}{F})$ for all $p$. We may as well assume, then, that $\lk{L}{F} \neq \emptyset$; let $G \in \lk{L}{F}$, so $F \disun G \in L$ (where $\disun$ denotes disjoint union). Because $L$ has the same dimension as $K$ and is pure, $F \disun G$ is contained in some facet of $L$ of dimension $\dim K$, say $F \disun H$. Then $H \in \lk{L}{F}$ and $\dim H = \dim \lk{K}{F}$, so $\dim \lk{L}{F} \geq \dim \lk{K}{F}$. But $\lk{L}{F} \subseteq \lk{K}{F}$, and thus $\dim \lk{L}{F} = \dim \lk{K}{F}$. Now let $p < \dim \lk{K}{F} = \dim \lk{L}{F}$. Because $L$ is \pcm, $\rhomi{p}(\lk{L}{F})$ and $\rhomi{p-1}(\lk{L}{F})$ are trivial, so the relative homology long exact sequence of %the pair $(\lk{K}{F},\ \lk{L}{F})$, $$%\begin{equation}%\label{eq:les} \cdots \maps \rhomi{p}(\lk{L}{F}) \maps \rhomi{p}(\lk{K}{F}) \maps \rhomi{p}(\lk{K}{F},\ \lk{L}{F}) \maps \rhomi{p-1}(\lk{L}{F}) \maps \cdots $$%\end{equation} (as in~\cite[Theorem~23.3]{Mu:alg.top}, for example), becomes $$\cdots \maps 0 \maps \rhomi{p}(\lk{K}{F}) \maps \rhomi{p}(\lk{K}{F},\ \lk{L}{F}) \maps 0 \maps \cdots.$$ Therefore $\rhomi{p}(\lk{K}{F}) \cong \rhomi{p}(\lk{K}{F},\ \lk{L}{F})$. \end{proof} \begin{cor}\label{th:L.1} Let $K$ be a \scx, and let $L$ be either the empty \scx\ or a \pcm\ subcomplex of the same dimension as $K$. Then $K$ is \pcm\ if and only if $(K,L)$ is \relcm. \end{cor} \begin{proof} Let $F \in K$. By Lemma~\ref{th:pre-L.1}, all lower-dimensional ($p < \dim \lk{K}{F}$) homology vanishes from all the links of $K$ if and only if all lower-dimensional relative homology vanishes from all the relative links of $(K,L)$, so $K$ is \pcm\ if and only if $(K,L)$ is \relcm. \end{proof} \begin{defncite}{Stanley} Let $K$ be a $(d-1)$-dimensional \scx. Then $K$ is \dfn{\seqcm} if the pairs $$\Omega_i(K) = (K\dd{i},\ \two{K}{i+1}{i})$$ are \relcm\ for $-1 \leq i \leq d-1$~\cite[III.2.9]{St:CCA2}. In particular, when $i=d-1$, we require $\Omega_{d-1}(K) = (K\dd{d-1},\ \emptyset)$ to be \relcm, which is equivalent to $K\dg{d-1}=K\dd{d-1}$ being \pcm, by Corollary~\ref{th:L.1}. \end{defncite} \begin{rmk} This definition is stated slightly differently from the one given by Stanley~\cite{St:CCA2}, but it is entirely equivalent. In~\cite{St:CCA2}, $\Omega^*_i(K)=(K^*_i,\ K^*_i \cap K\dg{i+1})$ is the pair that is required to be \relcm, where $K^*_i$ denotes the subcomplex generated by the $i$-dimensional facets of $K$. But by remarks following~\cite[Theorem~5.3]{St:TV}, \relcm ness of the pair $(K,L)$ depends only on the difference $K \less L$. Both $K\dd{i} \less \two{K}{i+1}{i}$ and $K^*_i \less K^*_i \cap K\dg{i+1}$ describe the set of faces in $K$ whose degree in $K$ is exactly $i+1$, so $\Omega_i(K)$ is \relcm\ precisely when $\Omega^*_i(K)$ is \relcm. \end{rmk} \begin{thm}\label{th:L.3} Let $K$ be a $(d-1)$-dimensional \scx. Then $K$ is \seqcm\ if and only if its pure $i$-skeleton $K\dd{i}$ is \pcm\ for all $-1 \leq i \leq d-1$. \end{thm} \begin{proof} ($\implies$): By induction on $(d-1)-i$. $i=d-1$. By definition of \seqlcmness, $\Omega_{d-1}(K)=(K\dd{d-1},\emptyset)$ is \relcm. By Corollary~\ref{th:L.1}, then, $K\dd{d-1}$ is \pcm. {\em induction step.} Now assume, by way of induction, that $K\dd{i+1}$ is \pcm. Then $\two{K}{i+1}{i}$ is the skeleton of a \pcm\ \cx, and hence \pcm. Since $K$ is \seqcm, $\Omega_i(K)=(K\dd{i},\two{K}{i+1}{i})$ is \relcm, so by Corollary~\ref{th:L.1}, $K\dd{i}$ is \pcm. ($\revimplies$): To prove that $K$ is \seqcm, we need to show that every $\Omega_i(K)$ is \relcm. There are two cases. If $i=d-1$, then $\Omega_{i}(K)=(K\dd{d-1},\emptyset)$ is \relcm\ by Corollary~\ref{th:L.1}, since $K\dd{d-1}$ is \pcm. If $i