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 [math]\displaystyle{ P }[/math] be a finite graded poset of rank n, so that each maximal chain in [math]\displaystyle{ P }[/math] has length n. For any [math]\displaystyle{ S }[/math], a subset of [math]\displaystyle{ \left\{0, \ldots, n\right\} }[/math], let [math]\displaystyle{ \alpha_P(S) }[/math] denote the number of chains in [math]\displaystyle{ P }[/math] whose ranks constitute the set [math]\displaystyle{ S }[/math]. More formally, let

[math]\displaystyle{ rk: P\to\{0,1,\ldots,n\} }[/math]

be the rank function of [math]\displaystyle{ P }[/math] and let [math]\displaystyle{ P_S }[/math] be the [math]\displaystyle{ S }[/math]-rank selected subposet, which consists of the elements from [math]\displaystyle{ P }[/math] whose rank is in [math]\displaystyle{ S }[/math]:

[math]\displaystyle{ P_S=\{x\in P: rk(x)\in S\}. }[/math]

Then [math]\displaystyle{ \alpha_P(S) }[/math] is the number of the maximal chains in [math]\displaystyle{ P_S }[/math] and the function

[math]\displaystyle{ S \mapsto \alpha_P(S) }[/math]

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

[math]\displaystyle{ S \mapsto \beta_P(S), \quad \beta_P(S) = \sum_{T \subseteq S} (-1)^{|S|-|T|} \alpha_P(S) }[/math]

is called the flag h-vector of [math]\displaystyle{ P }[/math]. By the inclusion–exclusion principle,

[math]\displaystyle{ \alpha_P(S) = \sum_{T\subseteq S}\beta_P(T). }[/math]

The flag f- and h-vectors of [math]\displaystyle{ P }[/math] refine the ordinary f- and h-vectors of its order complex [math]\displaystyle{ \Delta(P) }[/math]:

[math]\displaystyle{ f_{i-1}(\Delta(P)) = \sum_{|S|=i} \alpha_P(S), \quad h_{i}(\Delta(P)) = \sum_{|S|=i} \beta_P(S). }[/math]

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

[math]\displaystyle{ u_S = u_1 \cdots u_n, \quad u_i=a \text{ for } i\notin S, u_i=b \text{ for } i\in S. }[/math]

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

[math]\displaystyle{ \Psi_P(a,b) = \sum_{S} \beta_P(S) u_{S}. }[/math]

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

[math]\displaystyle{ \Psi_P(a,a+b) = \sum_{S} \alpha_P(S) u_{S}. }[/math]

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

[math]\displaystyle{ \Psi_P(a,b) = \Phi_P(a+b, ab+ba). }[/math]

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/ .