h-vector

In algebraic combinatorics, the h-vector of a simplicial polytope is a fundamental invariant of the polytope which encodes the number of faces of different dimensions and allows one to express the Dehn–Sommerville equations in a particularly simple form. A characterization of the set of h-vectors of simplicial polytopes was conjectured by Peter McMullen and proved by Lou Billera and Carl W. Lee and Richard Stanley

Flag h-vector and cd-index

A different generalization of the notions of f-vector and h-vector of a convex polytope has been extensively studied. Let $P$ be a finite graded poset of rank n, so that each maximal chain in $P$ has length n. For any $S$, a subset of $\{0,\dots ,n\}$, let ${\alpha }_P(S)$ denote the number of chains in $P$ whose ranks constitute the set $S$. More formally, let

$rk:P\to \{0,1,\dots ,n\}$

be the rank function of $P$ and let $P_S$ be the $S$-rank selected subposet, which consists of the elements from $P$ whose rank is in $S$:

$P_S=\{x\in P:rk(x)\in S\}.$

Then ${\alpha }_P(S)$ is the number of the maximal chains in $P_S$ and the function

$S\mapsto {\alpha }_P(S)$

is called the flag f-vector of P. The function

$S\mapsto {\beta }_P(S),{\beta }_P(S)=\sum _{T\subseteq S}(-1{)}^{|S|-|T|}{\alpha }_P(S)$

is called the flag h-vector of $P$. By the inclusion–exclusion principle,

${\alpha }_P(S)=\sum _{T\subseteq S}{\beta }_P(T).$

The flag f- and h-vectors of $P$ refine the ordinary f- and h-vectors of its order complex $\mathrm{\Delta }(P)$:

$f_{i-1}(\mathrm{\Delta }(P))=\sum _{|S|=i}{\alpha }_P(S),h_i(\mathrm{\Delta }(P))=\sum _{|S|=i}{\beta }_P(S).$

The flag h-vector of $P$ can be displayed via a polynomial in noncommutative variables a and b. For any subset $S$ of {1,…,n}, define the corresponding monomial in a and b,

$u_S=u_1\cdots u_n,u_i=a\text{ for }i\notin S,u_i=b\text{ for }i\in S.$

Then the noncommutative generating function for the flag h-vector of P is defined by

${\mathrm{\Psi }}_P(a,b)=\sum _S{\beta }_P(S)u_S.$

From the relation between α_P(S) and β_P(S), the noncommutative generating function for the flag f-vector of P is

${\mathrm{\Psi }}_P(a,a+b)=\sum _S{\alpha }_P(S)u_S.$

Margaret Bayer and Louis Billera determined the most general linear relations that hold between the components of the flag h-vector of an Eulerian poset P.

Fine noted an elegant way to state these relations: there exists a noncommutative polynomial Φ_P(c,d), called the cd-index of P, such that

${\mathrm{\Psi }}_P(a,b)={\mathrm{\Phi }}_P(a+b,ab+ba).$

Stanley proved that all coefficients of the cd-index of the boundary complex of a convex polytope are non-negative. He conjectured that this positivity phenomenon persists for a more general class of Eulerian posets that Stanley calls Gorenstein* complexes and which includes simplicial spheres and complete fans. This conjecture was proved by Kalle Karu. The combinatorial meaning of these non-negative coefficients (an answer to the question "what do they count?") remains unclear.

Further reading

• Combinatorics and commutative algebra, Progress in Mathematics, 41 (2nd ed.), Boston, MA: Birkhäuser Boston, Inc., 1996, ISBN 0-8176-3836-9 .
• Enumerative Combinatorics, 1, Cambridge University Press, 1997, ISBN 0-521-55309-1, http://www-math.mit.edu/~rstan/ec/ .