H-vector

Template:Lowercase 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 (g-theorem). The definition of h-vector applies to arbitrary abstract simplicial complexes. The g-conjecture stated that for simplicial spheres, all possible h-vectors occur already among the h-vectors of the boundaries of convex simplicial polytopes. It was proven in December 2018 by Karim Adiprasito.

Stanley introduced a generalization of the h-vector, the toric h-vector, which is defined for an arbitrary ranked poset, and proved that for the class of Eulerian posets, the Dehn–Sommerville equations continue to hold.Template:Citation needed A different, more combinatorial, generalization of the h-vector that has been extensively studied is the flag h-vector of a ranked poset. For Eulerian posets, it can be more concisely expressed by means of a noncommutative polynomial in two variables called the cd-index.

Definition

Let Δ be an abstract simplicial complex of dimension d − 1 with f_i i-dimensional faces and f₋₁ = 1. These numbers are arranged into the f-vector of Δ,

$f(\mathrm{\Delta })=(f_{-1},f_0,\dots ,f_{d-1}).$

An important special case occurs when Δ is the boundary of a d-dimensional convex polytope.

For k = 0, 1, …, d, let

$h_k=\sum _{i=0}^k(-1{)}^{k-i}(\genfrac{}{}{0ex}{}{d-i}{k-i})f_{i-1}.$

The tuple

$h(\mathrm{\Delta })=(h_0,h_1,\dots ,h_d)$

is called the h-vector of Δ. In particular, $h_0=1$, $h_1=f_0-d$, and $h_d=(-1{)}^d(1-\chi (\mathrm{\Delta }))$, where $\chi (\mathrm{\Delta })$ is the Euler characteristic of $\mathrm{\Delta }$. The f-vector and the h-vector uniquely determine each other through the linear relation

$\sum _{i=0}^d{f}_{i-1}(t-1{)}^{d-i}=\sum _{k=0}^d{h}_k{t}^{d-k},$

from which it follows that, for $i=0,\dots ,d$,

$f_{i-1}=\sum _{k=0}^i(\genfrac{}{}{0ex}{}{d-k}{i-k})h_k.$

In particular, $f_{d-1}=h_0+h_1+\cdots +h_d$. Let R = k[Δ] be the Stanley–Reisner ring of Δ. Then its Hilbert–Poincaré series can be expressed as

$P_R(t)=\sum _{i=0}^d\frac{f_{i-1}{t}^i}{(1-t{)}^i}=\frac{h_0+h_{1}t+\cdots +h_d{t}^d}{(1-t{)}^d}.$

This motivates the definition of the h-vector of a finitely generated positively graded algebra of Krull dimension d as the numerator of its Hilbert–Poincaré series written with the denominator (1 − t)^d.

The h-vector is closely related to the h^*-vector for a convex lattice polytope, see Ehrhart polynomial.

Recurrence relation

The $h$-vector $(h_0,h_1,\dots ,h_d)$ can be computed from the $f$-vector $(f_{-1},f_0,\dots ,f_{d-1})$ by using the recurrence relation

$h_0^i=1,-1\le i\le d$

$h_{i+1}^i=f_i,-1\le i\le d-1$

$h_k^i=h_k^{i-1}-h_{k-1}^{i-1},1\le k\le i\le d$.

and finally setting $h_k=h_k^d$ for $0\le k\le d$. For small examples, one can use this method to compute $h$-vectors quickly by hand by recursively filling the entries of an array similar to Pascal's triangle. For example, consider the boundary complex $\mathrm{\Delta }$ of an octahedron. The $f$-vector of $\mathrm{\Delta }$ is $(1,6,12,8)$. To compute the $h$-vector of $\mathrm{\Delta }$, construct a triangular array by first writing $d+2$ $1$s down the left edge and the $f$-vector down the right edge.

$\begin{array}{cccccccc}& & & & 1& & & \\ & & & 1& & 6& & \\ & & 1& & & & 12& \\ & 1& & & & & & 8\\ 1& & & & & & & & 0\end{array}$

(We set $f_d=0$ just to make the array triangular.) Then, starting from the top, fill each remaining entry by subtracting its upper-left neighbor from its upper-right neighbor. In this way, we generate the following array:

$\begin{array}{cccccccc}& & & & 1& & & \\ & & & 1& & 6& & \\ & & 1& & 5& & 12& \\ & 1& & 4& & 7& & 8\\ 1& & 3& & 3& & 1& & 0\end{array}$

The entries of the bottom row (apart from the final $0$) are the entries of the $h$-vector. Hence, the $h$-vector of $\mathrm{\Delta }$ is $(1,3,3,1)$.

Toric h-vector

To an arbitrary graded poset P, Stanley associated a pair of polynomials f(P,x) and g(P,x). Their definition is recursive in terms of the polynomials associated to intervals [0,y] for all y ∈ P, y ≠ 1, viewed as ranked posets of lower rank (0 and 1 denote the minimal and the maximal elements of P). The coefficients of f(P,x) form the toric h-vector of P. When P is an Eulerian poset of rank d + 1 such that P − 1 is simplicial, the toric h-vector coincides with the ordinary h-vector constructed using the numbers f_i of elements of P − 1 of given rank i + 1. In this case the toric h-vector of P satisfies the Dehn–Sommerville equations

$h_k=h_{d-k}.$

The reason for the adjective "toric" is a connection of the toric h-vector with the intersection cohomology of a certain projective toric variety X whenever P is the boundary complex of rational convex polytope. Namely, the components are the dimensions of the even intersection cohomology groups of X:

$h_k={\dim }_{\mathbb{Q}}{\mathrm{IH}}^{2k}(X,\mathbb{Q})$

(the odd intersection cohomology groups of X are all zero). The Dehn–Sommerville equations are a manifestation of the Poincaré duality in the intersection cohomology of X. Kalle Karu proved that the toric h-vector of a polytope is unimodal, regardless of whether the polytope is rational or not.

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

• Template:Citation.
• Template:Citation.