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 ( ''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. 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(\Delta)=(f_,f_0,\ldots,f_).$

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

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

: $h_k = \sum_^k (-1)^\binomf_.$

The tuple

: $h(\Delta)=(h_0,h_1,\ldots,h_d)$

is called the ''h''-vector of Δ. In particular, $h_ = 1$, $h_ = f_ - d$, and $h_ = (-1)^ (1 - \chi(\Delta))$, where $\chi(\Delta)$ is the Euler characteristic of $\Delta$. The ''f''-vector and the ''h''-vector uniquely determine each other through the linear relation

: $\sum_^f_(t-1)^= \sum_^h_t^,$

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

:$f_ = \sum_^i \binom h_.$

In particular, $f_ = h_ + h_ + \dotsb + h_$. Let ''R'' = k �be the Stanley–Reisner ring of Δ. Then its Hilbert–Poincaré series can be expressed as

: $P_(t)=\sum_^\frac= \frac.$

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 $\textstyle h$-vector $(h_, h_, \dotsc, h_)$ can be computed from the $\textstyle f$-vector $(f_, f_, \dotsc, f_)$ by using the recurrence relation

:$h^_ = 1, \qquad -1 \le i \le d$
:$h^_ = f_, \qquad -1 \le i \le d-1$
:$h^_ = h^_ - h^_, \qquad 1 \le k \le i \le d$.

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

:$\begin & & & & 1 & & & \\ & & & 1 & & 6 & & \\ & & 1 & & & & 12 & \\ & 1 & & & & & & 8 \\ 1 & & & & & & & & 0 \end$

(We set $f_ = 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 & & & & 1 & & & \\ & & & 1 & & 6 & & \\ & & 1 & & 5 & & 12 & \\ & 1 & & 4 & & 7 & & 8 \\ 1 & & 3 & & 3 & & 1 & & 0 \end$

The entries of the bottom row (apart from the final $0$) are the entries of the $\textstyle h$-vector. Hence, the $\textstyle h$-vector of $\textstyle \Delta$ is $\textstyle (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 ,''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_.$

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_ \operatorname^(X,\mathbb)$

(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 $\left\$, let $\alpha_P(S)$ denote the number of chains in $P$ whose ranks constitute the set $S$. More formally, let

:$rk: P\to\$

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=\.$

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), \quad \beta_P(S) = \sum_ (-1)^ \alpha_P(S)$

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

: $\alpha_P(S) = \sum_\beta_P(T).$

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

:$f_(\Delta(P)) = \sum_ \alpha_P(S), \quad h_(\Delta(P)) = \sum_ \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 , define the corresponding monomial in ''a'' and ''b'',

: $u_S = u_1 \cdots u_n, \quad u_i=a \text i\notin S, u_i=b \text i\in S.$

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

: $\Psi_P(a,b) = \sum_ \beta_P(S) u_.$

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

: $\Psi_P(a,a+b) = \sum_ \alpha_P(S) u_.$

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

: $\Psi_P(a,b) = \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.

References

Further reading

*.
*{{citation
, last = Stanley , first = Richard , author-link = Richard P. Stanley
, isbn = 0-521-55309-1
, publisher = Cambridge University Press
, title = Enumerative Combinatorics
, url = http://www-math.mit.edu/~rstan/ec/
, volume = 1
, year = 1997.

Algebraic combinatorics
Polyhedral combinatorics