Chain polynomials of distributive lattices are 75 \% unimodal
Anders Bj\"orner
It is shown that the numbers $c_i$ of chains of length $i$ in the proper part $L\setminus\{0,1\}$ of a distributive lattice $L$ of length $\ell +2$ satisfy the inequalities $$c_0<\ldots<c_{\lfloor{\ell /2}\rfloor} \quad\mbox{ and }\quad c_{\lfloor{3 \ell /4}\rfloor}>\ldots>c_{\ell}.$$ This proves 75 \% of the inequalities implied by the Neggers unimodality conjecture.
math0411610.tex
% Nov 26, 2004

\documentclass[12pt]{amsart}
\usepackage{amssymb}
\usepackage{epsf,amsmath}
\usepackage{amssymb,latexsym}

\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{ex}[thm]{Example}
\newtheorem{ddef}[thm]{Definition}
\newtheorem{rem}[thm]{Remark}

\newcommand{\defeq}{\stackrel{\rm def}{=}}
\newcommand{\bd}{\partial}

\def\({\left(}
\def\){\right)}
\def\MM{{\Cal M}}
\def\no={\,{\,|\!\!\!\!\!=\,\,}}
\def\de{\delta}
\def\wt{\widetilde}
\def\vap{\varphi}
\def\bb{\bold{b}}
\def\cc{\bold{c}}
\def\ff{\bold{f}}
\def\bg{\bold{g}}
\def\hh{\bold{h}}
\def\kk{\bold{k}}

\def\rank{\text\rm{rank}}
\def\Aa{{\mathcal{A}}}
\def\BB{{\mathcal{B}}}
\def\CC{{\mathcal{C}}}
\def\FF{{\mathcal{F}}}
\def\LL{{\mathcal{L}}}
\def\NN{{\mathcal{N}}}
\def\la{\lambda}
\def\vap{\varphi}
\def\si{\sigma}
\def\Si{\Sigma}
\def\ep{\varepsilon}
\def\de{\delta}
\def\De{\Delta}
\def\Ga{\Gamma}
\def\circm{\circmega}
\def\C{{\mathbb{C}}}
\def\R{{\mathbb R}}
\def\Z{{\mathbb{Z}}}
\def\N{{\mathbb{N}}}
\def\p{{\mathbb{P}}}
\def\Lv{\left\Vert}
\def\Rv{\right\Vert}
\def\lan{\langle}
\def\ran{\rangle}
\def\wh{\widehat}
\def\no={\,{\,|\!\!\!\!\!=\,\,}}
\def\sbst{\subseteq}
\def\circli{\circverline}
\def\vep{\varepsilon}
\def\lolraw{\longleftrightarrow}
\def\({\left(}
\def\){\right)}
\def\wt{\widetilde}
\def\aff{\text{\rm{aff}}}
\def\conv{\text{\rm{conv}}}
\def\sgn{\circperatorname{sgn}}
\def\lk{\circperatorname{lk}}
\def\DiagD{\mathcal D}
\def\DiagE{\mathcal E}
\def\CatTop{\sf Top}
\def\id{\rm id}
\def\colimit{\circperatorname{\sf colim}}
\def\hocolim{\circperatorname{\sf hocolim}}
\def\susp{\circperatorname{susp}}
\def\sd{\circperatorname{sd}}
\def\rk{\circperatorname{rk}}
\def\seq{\subseteq}
\def\ssm{\smallsetminus}
\def\spst{\supseteq}
\def\beq{\begin{eqnarray}}
\def\eeq{\end{eqnarray}}

\begin{document}
\date{\today}


\title[Chain polynomials of distributive lattices]
{Chain polynomials of distributive lattices are 75 \% unimodal}

\author[Anders Bj\"orner]{Anders Bj\"orner}
\email{bjorner@math.kth.se}
\address{Department of Mathematics\\
         Royal Institute of Technology\\
         S-100~44 Stockholm, Sweden}

\author[Jonathan David Farley]{Jonathan David Farley}

\address{Department of Applied Mathematics\\
        Massachusetts Institute of Technology\\
	Cambridge, Massachusetts 02139\\
        United States of America}


\begin{abstract}
It is shown that the numbers $c_i$ of chains of length $i$
in the proper part $L\setminus\{0,1\}$ of a distributive 
lattice $L$ of length $\ell +2$ satisfy the inequalities
$$c_0<\ldots<c_{\lfloor{\ell /2}\rfloor} \quad\mbox{ and }\quad
c_{\lfloor{3 \ell /4}\rfloor}>\ldots>c_{\ell}.$$
This proves 75 \% of the inequalities implied by the 
Neggers unimodality conjecture.
\end{abstract}

\maketitle

\section{Introduction}

The {\em chain polynomial} of a finite poset $P$ is defined as
$$C(P,t)=\sum_i c_i t^i,
$$
where $c_i$ is the number of chains (totally ordered subsets) in $P$
of length $i$ (i.e., cardinality $i+1$). One of the equivalent forms
of a well-known poset  conjecture due to Neggers \cite{Ne} implies that
the chain polynomial of 
the proper part $L\setminus\{0,1\}$ of a distributive 
lattice $L$ of length $d+1$ is {\em unimodal},
meaning that for some $k$ the coefficients of
$C(L\setminus\{0,1\}  ,t)$ satisfy the inequalities
$$c_0 \le \ldots\le c_k
\ge\ldots\ge c_{d-1}.$$
See \cite{Bre} and \cite{St4} for background, references  and more details
concerning this unimodality conjecture.
Recent progress in a special case (when the poset of join-irreducibles
is graded) appears in  \cite{Bran}, \cite{Far} and \cite{ReWe}.

The purpose of this note is to show that the unimodality
conjecture is 75\% correct, in the sense that violations of
unimodality can occur only for indices (roughly) between $d/2$ and
$3d/4$. More precisely,
we prove the following.

\begin{thm}
The numbers $c_i$ of chains of length $i$
in the proper part of a distributive 
lattice $L$ of length $d+1$ satisfy the inequalities
$$c_0<\ldots<c_{\lfloor{(d-1)/2}\rfloor} \;\mbox{ and }\;
c_{\lfloor{3(d-1)/4}\rfloor}>\ldots>c_{d-1}.$$
\end{thm}

The proof consists in observing that the order complex of
$L\setminus\{0,1\}$ is a nicely behaved ball, and then gathering and 
combining some known facts from $f$-vector theory. The pieces of the
argument are stated as Propositions 2, 3, 4 and 5. Of these, only
Proposition 3 seems to be new.


\section{Some $f$-vector inequalities}

For standard notions concerning simplicial
complexes we refer to the literature, see e.g. the books \cite{Br, Z}.

Let $\De$ be a $(d-1)$-dimensional simplicial complex, and let $f_i$ be the
number of $i$-dimensional faces of $\De$. The sequence $(f_0,\dots,f_{d-1})$
is called the {\em $f$-vector} of $\De$. We put $f_{-1}=1$.
The {\em $h$-vector} $(h_0,\dots,h_d)$ of $\De$ is defined by the equation
\begin{equation}\label{fh-rel}
\sum_{i=0}^{d} f_{i-1} x^{d-i} = \sum_{i=0}^{d} h_i (x+1)^{d-i}. 
\end{equation}
\bigskip

In the following two results we 
assume that  $\(f_0,f_1,\ldots,f_{d-1}\)$ is the
$f$-vector of a $(d-1)$-dimensional simplicial complex $\De$,
and that $f_0 >d$.
From now on, let $d\ge 3$ and $\de\defeq \lfloor\frac{d}2\rfloor$,
$\ep\defeq \lfloor\frac{d-1}2\rfloor$.

\begin{prop} Suppose that 
$h_i \ge 0,$ for all $0\le i \le d$.
Then
$$ f_i < f_j, \mbox{   for all $i<j$ such that $i+j\le d-2.$}$$
In particular, $f_0<f_1<\ldots<f_{\ep}$.
\end{prop}

\begin{proof}
This implication is well known. See e.g. \cite[Proposition 7.2.5 (i)]{Bj1}.
\end{proof}

\begin{prop} Suppose that $h_i \ge h_{d-i} \ge 0, \quad \mbox{for all $0\le i \le \de$.}$
Then
$$f_{\lfloor{3(d-1)/4}\rfloor}>
\ldots>f_{d-2}>f_{d-1}.$$
\end{prop}

\medskip

\begin{proof}
By (\ref{fh-rel}),
the $f$-vector $\ff=\(f_0,f_1,\ldots,f_{d-1}\)$ 
and the $h$-vector $\hh=\(h_0,h_1,\ldots,h_d\)$ satisfy
\begin{equation}\label{fh2}
f_k=\sum^d_{i=0}h_i\binom{d-i}{d-1-k}\qquad , \qquad k=-1,\ldots,d-1.
\end{equation}
Define integer vectors $\bb^i$ as follows:
$$
\bb^i=\(b^i_0,b^i_1,\ldots,b^i_{d-1}\) \qquad, \qquad\text{where }
b^i_k=\binom{i}{d-1-k}.
$$
Then, by  (\ref{fh2}), 
$\ff=\sum^d_{i=0}h_i\bb^{d-i}$,
which we rewrite
\begin{equation}\label{fh3}
\ff=\sum^{\ep}_{i=0}(h_i -h_{d-i})\bb^{d-i} +  \sum^{\de}_{i=0}h_{d-i}{\tilde{\bb}}^i,
\end{equation}
where
$$
{\tilde{\bb}}^i\defeq\left\{
\begin{array}{ll}
\bb^i+\bb^{d-i}&\qquad,\qquad\text{if } 2i\no=d\\
\bb^{d/2}&\qquad,\qquad\text{if } 2i=d. 
\end{array}\right.
$$

Let us say that a unimodal sequence
$$
a_0\le a_1\le\ldots\le a_k\ge a_{k-1}\ge\ldots\ge a_n
$$
{\it peaks\/} at $k$ 
(note that this does not necessarily determine $k$ uniquely).

It is shown in \cite[Proof of Thm. 5, p. 50]{Bj2} that
the vector ${\tilde{\bb}}^i$ is uni\-modal and peaks at
$d-1-\lfloor\frac{(d-i)}2\rfloor$.
The vector $\bb^{d-i}$ is a segment of a row in Pascal's triangle,
so it is easy to see that it is uni\-modal and, in fact,  also peaks at
$d-1-\lfloor\frac{(d-i)}2\rfloor$. One easily checks that
$$
d-1-\lfloor\frac{(d-i)}2\rfloor =
\left\{
\begin{array}{ll}
\lfloor\frac{d}2\rfloor+\lfloor{\frac{i}2}\rfloor-1&\qquad,\qquad\text{if
$d$ and $i$ are even}\\
\lfloor{\frac{d}2}\rfloor+\lfloor{\frac{i}2}\rfloor&\qquad,\qquad
\text{otherwise.}
\end{array}\right.
$$
Hence, both the vectors $\bb^{d-i}$ ($0 \le i\le \ep$) and the vectors
 $\tilde{\bb}^i$ ($0 \le i\le \de$) are unimodal and peak between $\de$
and $\de+\lfloor\de/2\rfloor$. 

By equation (\ref{fh3}), $\ff$ is a nonnegative linear
combination of the vectors $\bb^{d-i}$ and $\tilde{\bb}^i$.
It follows from the previous paragraph that
the inequalities hold for each of these vectors separately, 
strictly for $\bb^{d}$, and 
non-strictly otherwise. For the computation of the index
$\lfloor{3(d-1)/4}\rfloor$, see again
 \cite[pp. 50--51]{Bj2}.
 Hence, if $h_d=0$ the result follows. 
The case when $h_d=1$ requires a small extra argument to see that the
inequalities are in fact strict. For this case one can proceed as
in \cite[Proof of Thm. 5]{Bj2}.
\end{proof}


\section{On the $h$-vectors of balls}

We say that a simplicial complex is a {\em polytopal $(d-1)$-sphere} if it
is combinatorially isomorphic to the boundary complex of some convex $d$-polytope.
See Ziegler \cite{Z} for notions relating to 
polytopes and convex geometry.

\smallskip

We now review some definitions and results from the general theory of face 
numbers. For more about this topic, see e.g.   
\cite{Z} or the survey \cite{BB}.

It follows from (\ref{fh-rel}) that $h_0=1$, $h_1=f_0 -d$, and $h_d=(-1)^{d-1} \tilde{\chi}(\De)$, where
$\tilde{\chi}(\De)$ is the reduced Euler characteristic of $\De$. In
particular,
$$h_d=\left\{ \begin{array}{ll}
1, & \mbox{if $\De$ is a sphere,} \\
0, & \mbox{if $\De$ is a ball,}
\end{array}
\right.
$$
where the conditions are shorthand for saying that $\De$'s geometric
realization is homeomorphic to a sphere, resp. a ball.

The following are the {\em Dehn-Sommerville relations}:
\begin{equation}\label{DS}
\mbox{{\em If $\De$ is a sphere then \;
$h_i = h_{d-i}$, \; for all $0\le i \le d$.}}
\end{equation}
Hence, for spheres all $f$-vector information is encoded in the
shorter {\em $g$-vector}
$g=(g_0,\dots,g_{\lfloor \frac{d}{2} \rfloor})$, defined by
$g_i =h_i - h_{i-1}$. 
The relevance of the $g$-vector for this paper
is the following result, due to Stanley \cite{St1}:
\begin{equation}\label{g-thm}
\mbox{{\em If $\De$ is a polytopal sphere, then \:
$g_i\geq 0$ for all $i\geq 0$.}}
\end{equation}

If $\De$ is a $(d-1)$-ball, its boundary complex $\bd\De$ is a $(d-2)$-sphere.
Furthermore, $\bd\De$'s  $f$-vector is determined by that of $\De$, as shown by the
following consequence of the Dehn-Sommerville relations, due to
McMullen and Walkup \cite{MW}, see also \cite[Coroll. 3.9]{BL2}:
\begin{equation}\label{ball-thm}
\mbox{{\em If $\De$ is a ball with boundary $\bd \De$, then \;
$h^{\De}_{i} - h^{\De}_{d-i} = g^{\bd\De}_{i}$.}}
\end{equation}

Say that a $(d-1)$-ball $\De$ admits a {\em polytopal embedding} if
$\De$ is isomorphic to a subcomplex of the boundary complex
of some simplicial $d$-polytope. The following was shown by Kalai \cite[\S 8]{Kal}
and Stanley \cite[Coroll. 2.4]{St3}.
\begin{equation}\label{g-thm2}
\mbox{{\em If $\De$ admits a polytopal embedding, then \:
$g^{\bd\De}_i\geq 0$ for all $i\geq 0$.}}
\end{equation}

Combining (\ref{g-thm}), (\ref{ball-thm}) and (\ref{g-thm2}), we deduce 
 the following result.

\begin{prop}
If $\De$ is a $(d-1)$-ball, such that either the 
boundary sphere $\bd\De$ is polytopal
or $\De$ admits a polytopal embedding,
then $$h_i \ge h_{d-i} \ge 0, \; \mbox {for all} \; 0\le i \le \de.$$
\hfill$\Box$
\end{prop}


\section{Proof of Theorem 1}

We refer to \cite[Ch. 3]{St2} for basic facts and notation concerning
distributive lattices.

Let $L$ be a distributive lattice of length $d+1$, and let 
$\De_L =\De(L\setminus \{0,1\})$
be the order complex of its proper part. Thus, $\De_L$ is a 
pure simplicial complex of dimension $d-1$.

\newpage

\begin{prop} 
Suppose that $L$ is 
%a distributive lattice of length $d+1$, which is 
not Boolean. Then
the complex $\De_L$ is a $(d-1)$-ball satisfying
\begin{enumerate}
\item[(i)] $\De_L$ admits a polytopal embedding,
\item[(ii)] $\bd\De_L$ is polytopal.
\end{enumerate}
\end{prop}

\begin{proof}
By Birkhoff's representation theorem (see \cite[Ch. 3]{St2}) we have
that $L=J(P)$, where $J(P)$ is the family of order ideals of some poset $P$
ordered by inclusion.
Let $B$ denote the Boolean lattice of {\em all} subsets of $P$. Then
$\De_B =\De(B\setminus \{0,1\})$
is a polytope boundary (the barycentric subdivision of
the boundary of a $d$-simplex). Furthermore, $\De_L$ is embedded
in $\De_B$ as a full-dimensional subcomplex. Finally,
$\De_L$ is a shellable ball \cite{Bj3, Pro}. Thus,
part (i) is proved.

Part (ii) requires a small convexity argument. Alternatively, it follows
from Provan's result \cite{Pro} that $\De_L$ can be obtained from a simplex
via repeated stellar subdivisions. Since this part is not needed for
the main result of this paper, details of the proof are left out.
\end{proof}

We now have all the pieces needed to prove Theorem 1.
We may assume that $L$ is not Boolean, 
since in that case $\De_L$ is a sphere and Theorem 1 
is a special case of \cite[Thm. 5]{Bj2}. Then, 
by Propositions 4 and 5 we have that
$$h_i \ge h_{d-i} \ge 0, \; \mbox {for all} \; 0\le i \le \de.$$
Furthermore, by Propositions 2 and 3 it follows that
the $f$-vector of $\De_L$ satisfies
$$f_0<\ldots<f_{\lfloor{(d-1)/2}\rfloor} \;\mbox{ and }\;
f_{\lfloor{3(d-1)/4}\rfloor}>\ldots>f_{d-1}.$$
Since $f_i=c_i$ for all $i$, the proof of Theorem 1 
is complete.

\vspace{1cm}

\begin{thebibliography}{xxxx}

\bibitem{BB} 
L.~J. Billera and A. Bj\"orner, {\em Face numbers of polytopes and complexes,}
in ``Handbook of Discrete and Computational Geometry, 2nd Ed.'' 
(ed. J. E. Goodman and
J. O'Rourke), CRC Press, Boca Raton, FL, 2004, pp. 407--430.

\bibitem{BL2} 
L.~J. Billera and C.~W. Lee, {\em The numbers of faces of polytope 
pairs and unbounded
polyhedra}, European J. of Combinatorics {\bf 2} (1981), 307 -- 322.

\bibitem{Bj3} A. Bj\"orner, {\em Shellable and Cohen-Macaulay
partially ordered sets}, Trans. Amer. Math. Soc.
{\bf 260} (1980), 159--183.

\bibitem{Bj2} A. Bj\"orner, {\em Partial unimodality for $f$-vectors of simplicial
polytopes and spheres},  in ``Jerusalem Combinatorics ~'93''
(eds. H. Barcelo and G. Kalai), Contemporary Math. Series, Vol. 178,
Amer. Math. Soc., 1994, pp. 45--54.

\bibitem{Bj1} A. Bj\"orner, {\it The homology and shellability of matroids and
geometric lattices}, in \lq\lq Matroid Applications''(ed. N. White), Cambridge
Univ. Press, 1992, pp. 226--283.

\bibitem{Br} G.E. Bredon, {\it Topology and Geometry}, Graduate Texts in 
Mathematics, {\bf 139}, 
Springer-Verlag, New York-Heidelberg-Berlin, 1993.

\bibitem{Bre} F. Brenti, {\em Unimodal, Log-Concave and Polya Frequency 
Sequences in Combinatorics}, Memoirs Amer. Math. Soc. {\bf 413},
Amer. Math. Soc., 1989. 

\bibitem{Bran} P. Br\"and\'en, {\em Sign-graded posets. unimodality of $W$-
polynomials and the Charney-Davis conjecture},
Electronic Journal of Combinatorics {\bf 11 (2)} (2004), \# R9.

\bibitem{Far} J. D. Farley, {\em Linear extensions of ranked posets,
enumerated by descents. A problem of Stanley from the 1981 Banff Conference
on Ordered Sets}, Advances in Appl. Math. (to appear), preprint, 2003.

\bibitem{Kal}
G. Kalai, {\em The diameter of graphs of convex polytopes and $f$-vector theory},
in `` Applied geometry and discrete mathematics, The Victor Klee Festschrift'',
DIMACS Series in Discrete Math. and Theor. Computer Sci.,
Vol. 4, Amer. Math. Soc., Providence, R.I., 1991, pp. 387--411.

\bibitem{MW} 
P. McMullen and D.~W. Walkup,  {\em A generalized lower bound conjecture for simplicial
polytopes}, Mathematika {\bf 18} (1971), 264 -- 273.

\bibitem{Ne} J. Neggers, {\em Representations of finite partially ordered
sets}, J. Comb. Inf. Syst. Sci. {\bf 3} (1978), 113--133.

\bibitem{Pro} 
J. S. Provan ,  {\em Decompositions, shellings, and diameters of
simplicial complexes and convex polyhedra},
Ph.D. Thesis, Cornell Univ., 1977. 

\bibitem{ReWe} V. Reiner and V. Welker, {\em On the Charney-Davis and the
Neggers-Stanley conjectures}, J. Combinat. Theory, Series A, to appear.

\bibitem{St1} 
R.~P. Stanley, {\em The number of faces of simplicial
convex polytopes}, Advances in Math. {\bf 35} (1980), 236 -- 238.

\bibitem{St2} 
R.~P. Stanley, {\em Enumerative Combinatorics, Vol 1},
Cambridge Univ. Press, 1997.

\bibitem{St3} 
R.~P. Stanley, {\em A monotonicity property of $h$-vectors and
$h^*$-vectors}, Europ. J. Combinatorics {\bf 14} (1993), 251 -- 258.

\bibitem{St4} 
R.~P. Stanley, {\em Positivity problems and conjectures in algebraic
combinatorics}, in ``Mathematics: frontiers and perspectives'', Amer.
Math. Soc., Providence, R.I., 2000.

\bibitem{Z} 
G.~M. Ziegler, {\em Lectures on Polytopes}, GTM-series, Springer-Verlag, 
Berlin, 1995.

\end{thebibliography}

\end{document}





math0411610.extracted_bib
\begin{thebibliography}{xxxx}

\bibitem{BB} 
L.~J. Billera and A. Bj\"orner, {\em Face numbers of polytopes and complexes,}
in ``Handbook of Discrete and Computational Geometry, 2nd Ed.'' 
(ed. J. E. Goodman and
J. O'Rourke), CRC Press, Boca Raton, FL, 2004, pp. 407--430.

\bibitem{BL2} 
L.~J. Billera and C.~W. Lee, {\em The numbers of faces of polytope 
pairs and unbounded
polyhedra}, European J. of Combinatorics {\bf 2} (1981), 307 -- 322.

\bibitem{Bj3} A. Bj\"orner, {\em Shellable and Cohen-Macaulay
partially ordered sets}, Trans. Amer. Math. Soc.
{\bf 260} (1980), 159--183.

\bibitem{Bj2} A. Bj\"orner, {\em Partial unimodality for $f$-vectors of simplicial
polytopes and spheres},  in ``Jerusalem Combinatorics ~'93''
(eds. H. Barcelo and G. Kalai), Contemporary Math. Series, Vol. 178,
Amer. Math. Soc., 1994, pp. 45--54.

\bibitem{Bj1} A. Bj\"orner, {\it The homology and shellability of matroids and
geometric lattices}, in \lq\lq Matroid Applications''(ed. N. White), Cambridge
Univ. Press, 1992, pp. 226--283.

\bibitem{Br} G.E. Bredon, {\it Topology and Geometry}, Graduate Texts in 
Mathematics, {\bf 139}, 
Springer-Verlag, New York-Heidelberg-Berlin, 1993.

\bibitem{Bre} F. Brenti, {\em Unimodal, Log-Concave and Polya Frequency 
Sequences in Combinatorics}, Memoirs Amer. Math. Soc. {\bf 413},
Amer. Math. Soc., 1989. 

\bibitem{Bran} P. Br\"and\'en, {\em Sign-graded posets. unimodality of $W$-
polynomials and the Charney-Davis conjecture},
Electronic Journal of Combinatorics {\bf 11 (2)} (2004), \# R9.

\bibitem{Far} J. D. Farley, {\em Linear extensions of ranked posets,
enumerated by descents. A problem of Stanley from the 1981 Banff Conference
on Ordered Sets}, Advances in Appl. Math. (to appear), preprint, 2003.

\bibitem{Kal}
G. Kalai, {\em The diameter of graphs of convex polytopes and $f$-vector theory},
in `` Applied geometry and discrete mathematics, The Victor Klee Festschrift'',
DIMACS Series in Discrete Math. and Theor. Computer Sci.,
Vol. 4, Amer. Math. Soc., Providence, R.I., 1991, pp. 387--411.

\bibitem{MW} 
P. McMullen and D.~W. Walkup,  {\em A generalized lower bound conjecture for simplicial
polytopes}, Mathematika {\bf 18} (1971), 264 -- 273.

\bibitem{Ne} J. Neggers, {\em Representations of finite partially ordered
sets}, J. Comb. Inf. Syst. Sci. {\bf 3} (1978), 113--133.

\bibitem{Pro} 
J. S. Provan ,  {\em Decompositions, shellings, and diameters of
simplicial complexes and convex polyhedra},
Ph.D. Thesis, Cornell Univ., 1977. 

\bibitem{ReWe} V. Reiner and V. Welker, {\em On the Charney-Davis and the
Neggers-Stanley conjectures}, J. Combinat. Theory, Series A, to appear.

\bibitem{St1} 
R.~P. Stanley, {\em The number of faces of simplicial
convex polytopes}, Advances in Math. {\bf 35} (1980), 236 -- 238.

\bibitem{St2} 
R.~P. Stanley, {\em Enumerative Combinatorics, Vol 1},
Cambridge Univ. Press, 1997.

\bibitem{St3} 
R.~P. Stanley, {\em A monotonicity property of $h$-vectors and
$h^*$-vectors}, Europ. J. Combinatorics {\bf 14} (1993), 251 -- 258.

\bibitem{St4} 
R.~P. Stanley, {\em Positivity problems and conjectures in algebraic
combinatorics}, in ``Mathematics: frontiers and perspectives'', Amer.
Math. Soc., Providence, R.I., 2000.

\bibitem{Z} 
G.~M. Ziegler, {\em Lectures on Polytopes}, GTM-series, Springer-Verlag, 
Berlin, 1995.

\end{thebibliography}