- Source: 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 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}).}
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}.}
The tuple
h
(
Δ
)
=
(
h
0
,
h
1
,
…
,
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}
,
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 ))}
, where
χ
(
Δ
)
{\displaystyle \chi (\Delta )}
is the Euler characteristic of
Δ
{\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},}
from which it follows that, for
i
=
0
,
…
,
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}.}
In particular,
f
d
−
1
=
h
0
+
h
1
+
⋯
+
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}}}.}
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}
-vector
(
h
0
,
h
1
,
…
,
h
d
)
{\displaystyle (h_{0},h_{1},\dotsc ,h_{d})}
can be computed from the
f
{\displaystyle \textstyle f}
-vector
(
f
−
1
,
f
0
,
…
,
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}
h
i
+
1
i
=
f
i
,
−
1
≤
i
≤
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}
.
and finally setting
h
k
=
h
k
d
{\displaystyle \textstyle h_{k}=h_{k}^{d}}
for
0
≤
k
≤
d
{\displaystyle \textstyle 0\leq k\leq d}
. For small examples, one can use this method to compute
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 }
of an octahedron. The
f
{\displaystyle \textstyle f}
-vector of
Δ
{\displaystyle \textstyle \Delta }
is
(
1
,
6
,
12
,
8
)
{\displaystyle \textstyle (1,6,12,8)}
. To compute the
h
{\displaystyle \textstyle h}
-vector of
Δ
{\displaystyle \Delta }
, construct a triangular array by first writing
d
+
2
{\displaystyle d+2}
1
{\displaystyle \textstyle 1}
s down the left edge and the
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}}}
(We set
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}}}
The entries of the bottom row (apart from the final
0
{\displaystyle 0}
) are the entries of the
h
{\displaystyle \textstyle h}
-vector. Hence, the
h
{\displaystyle \textstyle h}
-vector of
Δ
{\displaystyle \textstyle \Delta }
is
(
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}.}
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} )}
(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
{\displaystyle P}
be a finite graded poset of rank n, so that each maximal chain in
P
{\displaystyle P}
has length n. For any
S
{\displaystyle S}
, a subset of
{
0
,
…
,
n
}
{\displaystyle \left\{0,\ldots ,n\right\}}
, let
α
P
(
S
)
{\displaystyle \alpha _{P}(S)}
denote the number of chains in
P
{\displaystyle P}
whose ranks constitute the set
S
{\displaystyle S}
. More formally, let
r
k
:
P
→
{
0
,
1
,
…
,
n
}
{\displaystyle rk:P\to \{0,1,\ldots ,n\}}
be the rank function of
P
{\displaystyle P}
and let
P
S
{\displaystyle P_{S}}
be the
S
{\displaystyle S}
-rank selected subposet, which consists of the elements from
P
{\displaystyle P}
whose rank is in
S
{\displaystyle S}
:
P
S
=
{
x
∈
P
:
r
k
(
x
)
∈
S
}
.
{\displaystyle P_{S}=\{x\in P:rk(x)\in S\}.}
Then
α
P
(
S
)
{\displaystyle \alpha _{P}(S)}
is the number of the maximal chains in
P
S
{\displaystyle P_{S}}
and the function
S
↦
α
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)}
is called the flag h-vector of
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).}
The flag f- and h-vectors of
P
{\displaystyle P}
refine the ordinary f- and h-vectors of its order complex
Δ
(
P
)
{\displaystyle \Delta (P)}
:
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).}
The flag h-vector of
P
{\displaystyle P}
can be displayed via a polynomial in noncommutative variables a and b. For any subset
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.}
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}.}
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}.}
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
Ψ
P
(
a
,
b
)
=
Φ
P
(
a
+
b
,
a
b
+
b
a
)
.
{\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. The combinatorial meaning of these non-negative coefficients (an answer to the question "what do they count?") remains unclear.
References
Further reading
Stanley, Richard (1996), Combinatorics and commutative algebra, Progress in Mathematics, vol. 41 (2nd ed.), Boston, MA: Birkhäuser Boston, Inc., ISBN 0-8176-3836-9.
Stanley, Richard (1997), Enumerative Combinatorics, vol. 1, Cambridge University Press, ISBN 0-521-55309-1.
Kata Kunci Pencarian:
- H-I
- H-IIB
- Kecepatan
- Daftar merek mobil
- Juno I
- Proton-K
- Soyuz 2.1a
- Shavit
- Ariane 1
- Lambda 4S
- H-vector
- Vector-H
- Poynting vector
- Unit vector
- Simplicial complex
- Inner product space
- Vector space
- Support vector machine
- Vector calculus
- Vector (mathematics and physics)
