H-vector

☆ Save On Wikipedia ↗

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[1] and proved by Lou Billera and Carl W. Lee[2][3] and Richard Stanley[4] (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.[5][6]

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 fi i-dimensional faces and f−1 = 1. These numbers are arranged into the f-vector of Δ,

f ( Δ ) = ( f − 1 , f 0 , … , f d − 1 ) . {\displaystyle f(\Delta )=(f_{-1},f_{0},\ldots ,f_{d-1}).} {\displaystyle f(\Delta )=(f_{-1},f_{0},\ldots ,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 = ∑ i = 0 k ( − 1 ) k − i ( d − i k − i ) f i − 1 . {\displaystyle h_{k}=\sum _{i=0}^{k}(-1)^{k-i}{\binom {d-i}{k-i}}f_{i-1}.} {\displaystyle h_{k}=\sum _{i=0}^{k}(-1)^{k-i}{\binom {d-i}{k-i}}f_{i-1}.}

The tuple

h ( Δ ) = ( h 0 , h 1 , … , h d ) {\displaystyle h(\Delta )=(h_{0},h_{1},\ldots ,h_{d})} {\displaystyle h(\Delta )=(h_{0},h_{1},\ldots ,h_{d})}

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

∑ i = 0 d f i − 1 ( t − 1 ) d − i = ∑ k = 0 d h k t d − k , {\displaystyle \sum _{i=0}^{d}f_{i-1}(t-1)^{d-i}=\sum _{k=0}^{d}h_{k}t^{d-k},} {\displaystyle \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 , … , d {\displaystyle i=0,\dotsc ,d} {\displaystyle i=0,\dotsc ,d},

f i − 1 = ∑ k = 0 i ( d − k i − k ) h k . {\displaystyle f_{i-1}=\sum _{k=0}^{i}{\binom {d-k}{i-k}}h_{k}.} {\displaystyle f_{i-1}=\sum _{k=0}^{i}{\binom {d-k}{i-k}}h_{k}.}

In particular, f d − 1 = h 0 + h 1 + ⋯ + h d {\displaystyle f_{d-1}=h_{0}+h_{1}+\dotsb +h_{d}} {\displaystyle f_{d-1}=h_{0}+h_{1}+\dotsb +h_{d}}. Let R = k[Δ] be the Stanley–Reisner ring of Δ. Then its Hilbert–Poincaré series can be expressed as

P R ( t ) = ∑ i = 0 d f i − 1 t i ( 1 − t ) i = h 0 + h 1 t + ⋯ + h d t d ( 1 − t ) d . {\displaystyle 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}}}.} {\displaystyle 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 {\displaystyle \textstyle h} {\displaystyle \textstyle h}-vector ( h 0 , h 1 , … , h d ) {\displaystyle (h_{0},h_{1},\dotsc ,h_{d})} {\displaystyle (h_{0},h_{1},\dotsc ,h_{d})} can be computed from the f {\displaystyle \textstyle f} {\displaystyle \textstyle f}-vector ( f − 1 , f 0 , … , f d − 1 ) {\displaystyle (f_{-1},f_{0},\dotsc ,f_{d-1})} {\displaystyle (f_{-1},f_{0},\dotsc ,f_{d-1})} by using the recurrence relation

h 0 i = 1 , − 1 ≤ i ≤ d {\displaystyle h_{0}^{i}=1,\qquad -1\leq i\leq d} {\displaystyle h_{0}^{i}=1,\qquad -1\leq i\leq d}
h i + 1 i = f i , − 1 ≤ i ≤ d − 1 {\displaystyle h_{i+1}^{i}=f_{i},\qquad -1\leq i\leq d-1} {\displaystyle h_{i+1}^{i}=f_{i},\qquad -1\leq i\leq d-1}
h k i = h k i − 1 − h k − 1 i − 1 , 1 ≤ k ≤ i ≤ d {\displaystyle h_{k}^{i}=h_{k}^{i-1}-h_{k-1}^{i-1},\qquad 1\leq k\leq i\leq d} {\displaystyle h_{k}^{i}=h_{k}^{i-1}-h_{k-1}^{i-1},\qquad 1\leq k\leq i\leq d}.

and finally setting h k = h k d {\displaystyle \textstyle h_{k}=h_{k}^{d}} {\displaystyle \textstyle h_{k}=h_{k}^{d}} for 0 ≤ k ≤ d {\displaystyle \textstyle 0\leq k\leq d} {\displaystyle \textstyle 0\leq k\leq d}. For small examples, one can use this method to compute h {\displaystyle \textstyle h} {\displaystyle \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 Δ {\displaystyle \textstyle \Delta } {\displaystyle \textstyle \Delta } of an octahedron. The f {\displaystyle \textstyle f} {\displaystyle \textstyle f}-vector of Δ {\displaystyle \textstyle \Delta } {\displaystyle \textstyle \Delta } is ( 1 , 6 , 12 , 8 ) {\displaystyle \textstyle (1,6,12,8)} {\displaystyle \textstyle (1,6,12,8)}. To compute the h {\displaystyle \textstyle h} {\displaystyle \textstyle h}-vector of Δ {\displaystyle \Delta } {\displaystyle \Delta }, construct a triangular array by first writing d + 2 {\displaystyle d+2} {\displaystyle d+2} 1 {\displaystyle \textstyle 1} {\displaystyle \textstyle 1}s down the left edge and the f {\displaystyle \textstyle f} {\displaystyle \textstyle f}-vector down the right edge.

1 1 6 1 12 1 8 1 0 {\displaystyle {\begin{matrix}&&&&1&&&\\&&&1&&6&&\\&&1&&&&12&\\&1&&&&&&8\\1&&&&&&&&0\end{matrix}}} {\displaystyle {\begin{matrix}&&&&1&&&\\&&&1&&6&&\\&&1&&&&12&\\&1&&&&&&8\\1&&&&&&&&0\end{matrix}}}

(We set f d = 0 {\displaystyle f_{d}=0} {\displaystyle 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:

1 1 6 1 5 12 1 4 7 8 1 3 3 1 0 {\displaystyle {\begin{matrix}&&&&1&&&\\&&&1&&6&&\\&&1&&5&&12&\\&1&&4&&7&&8\\1&&3&&3&&1&&0\end{matrix}}} {\displaystyle {\begin{matrix}&&&&1&&&\\&&&1&&6&&\\&&1&&5&&12&\\&1&&4&&7&&8\\1&&3&&3&&1&&0\end{matrix}}}

The entries of the bottom row (apart from the final 0 {\displaystyle 0} {\displaystyle 0}) are the entries of the h {\displaystyle \textstyle h} {\displaystyle \textstyle h}-vector. Hence, the h {\displaystyle \textstyle h} {\displaystyle \textstyle h}-vector of Δ {\displaystyle \textstyle \Delta } {\displaystyle \textstyle \Delta } is ( 1 , 3 , 3 , 1 ) {\displaystyle \textstyle (1,3,3,1)} {\displaystyle \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 [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 fi 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 . {\displaystyle h_{k}=h_{d-k}.} {\displaystyle 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 Q ⁡ IH 2 k ⁡ ( X , Q ) {\displaystyle h_{k}=\dim _{\mathbb {Q} }\operatorname {IH} ^{2k}(X,\mathbb {Q} )} {\displaystyle h_{k}=\dim _{\mathbb {Q} }\operatorname {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.[7]

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

r k : P → { 0 , 1 , … , n } {\displaystyle rk:P\to \{0,1,\ldots ,n\}} {\displaystyle rk:P\to \{0,1,\ldots ,n\}}

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

P S = { x ∈ P : r k ( x ) ∈ S } . {\displaystyle P_{S}=\{x\in P:rk(x)\in S\}.} {\displaystyle P_{S}=\{x\in P:rk(x)\in S\}.}

Then α P ( S ) {\displaystyle \alpha _{P}(S)} {\displaystyle \alpha _{P}(S)} is the number of the maximal chains in P S {\displaystyle P_{S}} {\displaystyle P_{S}} and the function

S ↦ α P ( S ) {\displaystyle S\mapsto \alpha _{P}(S)} {\displaystyle S\mapsto \alpha _{P}(S)}

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

S ↦ β P ( S ) , β P ( S ) = ∑ T ⊆ S ( − 1 ) | S | − | T | α P ( S ) {\displaystyle S\mapsto \beta _{P}(S),\quad \beta _{P}(S)=\sum _{T\subseteq S}(-1)^{|S|-|T|}\alpha _{P}(S)} {\displaystyle S\mapsto \beta _{P}(S),\quad \beta _{P}(S)=\sum _{T\subseteq S}(-1)^{|S|-|T|}\alpha _{P}(S)}

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

α P ( S ) = ∑ T ⊆ S β P ( T ) . {\displaystyle \alpha _{P}(S)=\sum _{T\subseteq S}\beta _{P}(T).} {\displaystyle \alpha _{P}(S)=\sum _{T\subseteq S}\beta _{P}(T).}

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

f i − 1 ( Δ ( P ) ) = ∑ | S | = i α P ( S ) , h i ( Δ ( P ) ) = ∑ | S | = i β P ( S ) . {\displaystyle f_{i-1}(\Delta (P))=\sum _{|S|=i}\alpha _{P}(S),\quad h_{i}(\Delta (P))=\sum _{|S|=i}\beta _{P}(S).} {\displaystyle f_{i-1}(\Delta (P))=\sum _{|S|=i}\alpha _{P}(S),\quad h_{i}(\Delta (P))=\sum _{|S|=i}\beta _{P}(S).}

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

u S = u 1 ⋯ u n , u i = a  for  i ∉ S , u i = b  for  i ∈ S . {\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.} {\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.}

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

Ψ P ( a , b ) = ∑ S β P ( S ) u S . {\displaystyle \Psi _{P}(a,b)=\sum _{S}\beta _{P}(S)u_{S}.} {\displaystyle \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

Ψ P ( a , a + b ) = ∑ S α P ( S ) u S . {\displaystyle \Psi _{P}(a,a+b)=\sum _{S}\alpha _{P}(S)u_{S}.} {\displaystyle \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.[9]

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

Ψ P ( a , b ) = Φ P ( a + b , a b + b a ) . {\displaystyle \Psi _{P}(a,b)=\Phi _{P}(a+b,ab+ba).} {\displaystyle \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.[10] The combinatorial meaning of these non-negative coefficients (an answer to the question "what do they count?") remains unclear.

References

  1. McMullen, Peter (1971), "The numbers of faces of simplicial polytopes", Israel Journal of Mathematics, 9 (4): 559–570, doi:10.1007/BF02771471, MR 0278183, S2CID 92984501.
  2. Billera, Louis; Lee, Carl (1980), "Sufficiency of McMullen's conditions for f-vectors of simplicial polytopes", Bulletin of the American Mathematical Society, 2 (1): 181–185, doi:10.1090/s0273-0979-1980-14712-6, MR 0551759.
  3. Billera, Louis; Lee, Carl (1981), "A proof of the sufficiency of McMullen's conditions for f-vectors of simplicial convex polytopes", Journal of Combinatorial Theory, Series A, 31 (3): 237–255, doi:10.1016/0097-3165(81)90058-3.
  4. Stanley, Richard (1980), "The number of faces of a simplicial convex polytope", Advances in Mathematics, 35 (3): 236–238, doi:10.1016/0001-8708(80)90050-X, MR 0563925.
  5. Kalai, Gil (2018-12-25). "Amazing: Karim Adiprasito proved the g-conjecture for spheres!". Combinatorics and more. Retrieved 2019-06-12.
  6. Adiprasito, Karim (2018-12-26). "Combinatorial Lefschetz theorems beyond positivity". arXiv:1812.10454v3 [math.CO].
  7. Karu, Kalle (2004-08-01). "Hard Lefschetz theorem for nonrational polytopes". Inventiones Mathematicae. 157 (2): 419–447. arXiv:math/0112087. Bibcode:2004InMat.157..419K. doi:10.1007/s00222-004-0358-3. ISSN 1432-1297. S2CID 15896309.
  8. Stanley, Richard (1979), "Balanced Cohen-Macaulay Complexes", Transactions of the American Mathematical Society, 249 (1): 139–157, doi:10.2307/1998915, JSTOR 1998915.
  9. Bayer, Margaret M. and Billera, Louis J (1985), "Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets", Inventiones Mathematicae 79: 143-158. doi:10.1007/BF01388660.
  10. Karu, Kalle (2006), "The cd-index of fans and posets", Compositio Mathematica, 142 (3): 701–718, doi:10.1112/S0010437X06001928, MR 2231198.

Further reading