f-Vectors of Polyhedra

Min Yan^{∗}

Department of Mathematics Hong Kong University of Science and Technology Clear Water Bay, Hong Kong mamyan@math.ust.hk

March 10, 1997

Abstract

The f-vector of a triangulation of a polyhedron X is the numbers of simplices at various dimensions. We prove that the affine span of f-vectors of X has dimension \frac{n+s+1}{2}, where n is the dimension of X, and s is the dimension of the part of X that is singular with respect to the local Euler characteristic.

Mathematics Subject Classification: Primary 52B05; Secondary 57P99, 57Q99 Key Words: polyhedron, f-vector, affine span, Euler characteristic, link

∗Research is supported by HKUST 632/94P.

1 Statement of Results

Let X be a polyhedron of dimension n. Given a triangulation Δ of X, let f_{i}(X; Δ) be the number of simplices of dimension i in the triangulation. The f-vector of the triangulation is

f(X; Δ) = (f_{0}, f_{1}, ⋯, f_{n}).

Kruskal and Katona [Ka, Kr] obtained necessary and sufficient conditions for a vector to be the f-vector of some simplicial complex. Jungerman and Ringel [JR, R] gave a complete characterization of the f-vectors of triangulations of compact surfaces. The f-vectors of simplicial polytopes have been extensively studied [BaL, Br, G1, G2, MS]. McMullen [M] conjectured the necessary and sufficient conditions for a vector to be the f-vector of some simplicial polytope. Billera and Lee [BiL] proved the sufficiency part of the conjecture, and Stanley [St] proved the necessity part.

Among the necessary conditions for f-vectors are the Euler characteristic equation and certain linear conditions called the Dehn-Sommerville equations. Such equations were first established for simplicial polytopes [So] and were proved to be the only linear conditions on the f-vectors [Br, G1]. Klee [Kl] generalized the Dehn-Sommerville equations to Euler manifolds (simplicial complexes with same local Euler characteristic property as combinatorial manifolds without boundary). Chen and the author [CY1,CY2] further generalized the equations to Euler manifolds with boundary and obtained all the linear conditions for f-vectors of triangulations of such spaces.

The main result of this paper is the characterization of all (rational) linear conditions on f-vectors of all triangulations of a (fixed) compact polyhedron. In particular, we obtain the dimension of the affine space spanned by these f-vectors.

To state the result, we need the following definition.

Definition 1 Let X be an n-dimensional polyhedron. A point x ∈ X is called an (Eulerian) regular point if χ(lk(x, X)) = χ(S^{n−1}) = 1 − (−1)^{n}. A point that is not Eulerian regular is called an (Eulerian) singular point.

lk(x, X) is the link of the point x in X. It depends only on the local PL-structure of X at x. It is compact and unique up to PL-homeomorphisms. More details on links of points (and links of simplices introduced later on) may be found in Rourke and Sanderson’s book on PL-topology [RS].

We will show (Lemma 3) that for any given triangulation of X, the Eulerian singular part is the union of the interiors of some simplices. The dimension s of the Eulerian singular part is then defined as the biggest dimension of these simplices. We will further show (Lemma 4) that n and s have different parity. The dimension of the affine span of the f-vectors is then given by the following theorem.

Theorem 1 Let X be a polyhedron of dimension n. Let s be the dimension of the Eulerian singular part. Then the dimension of the affine span of the f-vectors of all triangulations of X is \frac{n+s+1}{2}.

If X has no singular parts, then we should take s = −1 in case n is even, and s = 0 in case n is odd. The conclusion of the theorem is then consistent with the classical result on f-vectors for simplicial polytopes [Br, G1] and the extension to f-vectors for manifolds without boundary [CY1,CY2].

If X is a manifold with nonempty boundary ∂X, then ∂X is exactly the Eulerian singular part of X. Therefore s = n − 1, and the conclusion of the theorem is consistent with the result of Chen and the author in this case [CY1].

The theorem is the consequence of the following explicit characterization of the affine span.

Theorem 2 Let X be a polyhedron of dimension n. Let s be the dimension of the Eulerian singular part. Then the (rational) affine span of the f-vectors of all triangulations of X consists of vectors (f_{0}, f_{1}, ⋯, f_{n}) satisfying the last (n − s − 1) Dehn-Sommerville equations

(1 − (−1)^{n−i})f_{i} + ∑_{j>i}(−1)^{n−j−1} \binom{j + 1}{i + 1} f_{j} = 0, s < i < n,

and the Euler characteristic equation

∑_{j=0}^{n}(−1)^{j}f_{j} = χ(X).

It is well-known that the last (n − s − 1) Dehn-Sommerville equations have rank \frac{n−s−1}{2}, and the Euler equation is linearly independent of these Dehn-Sommerville equations. Therefore the dimension of the affine space is (n + 1) − \frac{n−s−1}{2} − 1 = \frac{n+s+1}{2}.

It should be pointed out that the linear relations satisfied by the f-vectors are the only ones with rational coefficients. It is quite possible to have further torsion relations (such as λ(f) = 0 mod p) with integer coefficients. In [CY2], such a possibility is extensively studied for the case that the local Euler characteristic χ(lk(x, X)) takes only two values. It is not very difficult to extend the discussion to the general case and explicitly write down all the torsion relations. The result depends on the stratification structure given by the local Euler characteristic.

The author wishes to thank Dr. B.F. Chen for his comments and help.

2 Dehn-Sommerville Equations for Polyhedra

We classify points of X according to their local Euler characteristics

X_{k} = {x ∈ X : χ(lk(x, X)) = k}.

Thus X_{1−(−1)^{n}} is the Eulerian regular part of X, and ∪_{k≠1−(−1)^{n}}X_{k} is the Eulerian singular part.

If all points are regular, then X is called an Euler manifold without boundary. The notion was first defined in [Kl] for simplicial complexes and was modified in the present form for polyhedra in [CY2]. In fact, the concept was further extended in [CY2] to include manifolds with boundary (and more generally, 2-strata spaces). If there is only one type of singular point, i.e., X_{k} = ∅ for all k except 1 − (−1)^{n} and k_{0}, then X is called an Euler manifold with boundary ∂X = X_{k_{0}}.

Let Δ be a triangulation of X. Then for any simplex σ of Δ, we have the simplicial link of σ in Δ

lk(σ, Δ) = {τ ∈ Δ : τ ∩ σ = ∅, τ and σ span a simplex σ ∗ τ of Δ}.

The PL-homeomorphism type of its geometrical realization lk(σ, X) does not depend on the triangulation and is called the link of σ in X. Denote by σ̇ the interior of σ. Then for x ∈ σ̇, we have the following relation

lk(x, X) = ∂σ ∗ lk(σ, X).  (1)

Lemma 3

X_{k} = ∪{σ̇ : χ(lk(σ, X)) = (−1)^{dim σ}(k − 1 + (−1)^{dim σ})}.

Proof: Suppose that x ∈ σ̇, dim σ = i. Then it follows from (1) that

χ(lk(x, X)) = χ(S^{i−1}) + χ(lk(σ, X)) − χ(S^{i−1})χ(lk(σ, X))
= 1 − (−1)^{i} + (−1)^{i}χ(lk(σ, X)).

This equality is equivalent to

χ(lk(σ, X)) = (−1)^{i}(χ(lk(x, X)) − 1 + (−1)^{i}).

The Lemma is then proved.

To prove that n and s have different parity, we need the following facts from [CY2]:

1. If X is an Euler manifold with boundary ∂X, then lk(σ, X) is an Euler manifold with boundary lk(σ, ∂X). In particular, lk(σ, X) is an Euler manifold without boundary unless σ is the proper face of some simplex in ∂X. Moreover, dim lk(σ, X) and n − dim σ have different parity;

2. If X is an Euler manifold of odd dimension and without boundary, then χ(X) = 0.

Lemma 4 The dimension s of the singular part has different parity from the dimension n of the whole polyhedron.

Proof: Let σ be a simplex of dimension s such that σ̇ ⊂ X_{k}, k ≠ 1 − (−1)^{n}. Because σ has the highest singular dimension, the interior of any simplex with σ as a proper face consists of regular points. Let U be the union of σ̇ with the interiors of these simplices. Then U is an open neighborhood of σ̇ such that σ̇ is closed in U and U − σ̇ ⊂ X_{1−(−1)^{n}}. In other words, U is an Euler manifold with boundary σ̇. Take any locally finite triangulation T of (U, σ̇) and a simplex τ ⊂ σ̇ of T of dimension s. By the first property of Euler manifolds and the fact that dim τ = dim σ, lk(τ, U) is an Euler manifold without boundary. Moreover, its dimension has different parity from n − s.

Therefore if n − s is even, then lk(τ, U) is an odd dimensional Euler manifold. By the second property about Euler manifolds, we have χ(lk(τ, U)) = 0. Therefore if x ∈ τ̇, then by (1) we have χ(lk(x, X)) = χ(lk(x, U)) = χ(∂τ ∗ lk(τ, U)) = χ(∂τ) = χ(S^{s−1}) = χ(S^{n−1}). This contradicts x ∈ τ̇ ⊂ σ̇ ⊂ X_{k}, k ≠ 1 − (−1)^{n}.

This completes the proof of Lemma 4.

Denote by f_{i}(X_{k}; Δ) the number of simplices σ of Δ such that σ̇ ⊂ X_{k}. Then f_{i}(X; Δ) = ∑_{k} f_{i}(X_{k}; Δ), and we have

∑_{j>i}(−1)^{j−i−1} \binom{j+1}{i+1} f_{j}(X; Δ) = ∑_{dim σ=i} χ(lk(σ, Δ))
= ∑_{k}(−1)^{i}(k − 1 + (−1)^{i})f_{i}(X_{k}; Δ), (2)

where the first equality was essentially due to Klee [Kl] (a reformulation of Klee’s argument may be found in [CY1]), the second equality is due to Lemma 3. Thus we get the following Dehn-Sommerville equation

(1 − (−1)^{n−i})f_{i}(X; Δ) + ∑_{j>i}(−1)^{n−j−1} \binom{j+1}{i+1} f_{j}(X; Δ)
= ∑_{k}(1 − (−1)^{n−i})f_{i}(X_{k}; Δ) + ∑_{k}(−1)^{n}(k − 1 + (−1)^{i})f_{i}(X_{k}; Δ)
= ∑_{k}(1 − (−1)^{n} + (−1)^{n}k)f_{i}(X_{k}; Δ).

The coefficients of f_{∗}(X_{k}; Δ) on the left side form the Dehn-Sommerville matrix D(n) introduced in [CY1]. We observe that the coefficient of f_{i}(X_{k}; Δ) on the right side vanishes if and only if k = 1−(−1)^{n} = χ(S^{n−1}). Therefore we conclude the following.

Lemma 5

D(n)f(X; Δ) = ∑_{k≠1−(−1)^{n}}(1 − (−1)^{n} + (−1)^{n}k)f(X_{k}; Δ).  (3)

3 Proof of Main Result

By Lemma 4, we see that n and s + 1 have the same parity. Then we may conclude from the explicit expression of D(n) that

D(n) = ( \begin{matrix}D(s + 1) & ∗ \\ 0 & E(n, s + 1) \end{matrix} ) .  (4)

The statement of the theorem 2 is then the equality

affine spanf(X) = {v ∈ Q^{n+1} : (0, E(n, s + 1))v = 0, χ(v) = χ(X)}.  (5)

Given any triangulation Δ of X, the right side of the Dehn-Sommerville equation (3) is a combination of f-vectors of spaces of dimension ≤ s. Therefore the last n−s−1 coordinates (0, E(n, s + 1))f(X; Δ) of the n-dimensional vector D(n)f(X; Δ) must vanish. This shows that the left side of (5) is contained in the right side.

To show the two sides to be the same, we only need to find \frac{n+s+1}{2} +1 triangulations of X with affinely independent f-vectors. Here we make use of the existence of triangulations δ_{i}^{p} of D^{p}, 0 ≤ i ≤ [\frac{p+1}{2}], with the following properties 1. ∂δ_{i}^{p} = δ_{i}^{p}|_{S^{p−1}} = ∂Δ^{p}, the boundary of the standard p-simplex;

2. The f-vectors f(D^{p}; δ_{i}^{p}) are affinely independent.

Such triangulations may be obtained by deleting one p-dimensional simplex from some triangulations of S^{p} (the boundaries of (p+1)-dimensional cyclic polytopes [Br, G1], for example).

We start by fixing an arbitrary triangulation Δ of X. Let σ̇ ⊂ X_{k}, k ≠ 1 − (−1)^{n}, be the interior of an s-dimensional simplex in the singular part of X. Then we replace the subcomplex σ ∗ lk(σ, Δ) of Δ by the complex δ_{i}^{s} ∗ lk(σ, Δ). Since σ ∗ lk(σ, Δ) is glued to the rest of Δ along ∂σ ∗ lk(σ, Δ) = ∂δ_{i}^{s} ∗ lk(σ, Δ) (the equality is by the first property of δ_{i}^{s}), the replacement is still a triangulation of X. We denote the triangulation by Δ_{i}.

For any simplex τ ∈ lk(σ, Δ), the simplex σ ∗ τ is replaced by δ_{i}^{s} ∗ τ. Since σ has the highest singular dimension, the interior of σ ∗ τ consists of regular points. It then follows from ∂δ_{i}^{s} = ∂σ that the subdivision does not affect the singular part of X except the interior of σ. Consequently,

f(X_{l}; Δ_{i}) = f(X_{l}; Δ), l ≠ k, 1 − (−1)^{n}  (6)

and

f(X_{k}; Δ_{i}) = f(X_{k}; Δ) + f(D^{s}; δ_{i}^{s}) − f(S^{s−1}; ∂Δ^{s}), l = k.  (7)

By Dehn-Sommerville equation (3), we see that (6) and (7) imply

\begin{aligned}& D(n)f(X; Δ_{i}) − D(n)f(X; Δ_{0}) \\ = & (1 − (−1)^{n} + (−1)^{n}k)[f(D^{s}; δ_{i}^{s}) − f(D^{s}; δ_{0}^{s})], \end{aligned} 1 ≤ i ≤ [\frac{s+1}{2}]  (8)

These are linearly independent by the second property of δ_{i}^{s}.

The similar replacement may be carried out in the regular part of X. Let θ̇ ⊂ X_{1−(−1)^{n}} be the interior of an n-dimensional simplex of Δ_{0}, the zeroth of [\frac{s+3}{2}] triangulations we just constructed. Then we may replace θ with the complex δ_{j}^{n} to obtain Δ_{δ_{0,j}}, 0 ≤ j ≤ [\frac{n+1}{2}]. Since ∂δ_{j}^{n} = ∂θ, nothing is changed on simplices other than the interior θ̇. Therefore, we have

f(X_{l}; Δ_{0,j}) = f(X_{l}; Δ_{0}), l ≠ 1 − (−1)^{n},  (9)

and

f(X; Δ_{0,j}) = f(X; Δ_{0}) + f(D^{n}; δ_{j}^{n}) − f(S^{n−1}; ∂Δ^{n}).  (10)

By the second property of δ_{j}^{n}, (10) implies that the vectors

f(X; Δ_{0,j}) − f(X; Δ_{0,0}) = f(D^{n}; δ_{j}^{n}) − f(D^{n}; δ_{0}^{n}), 1 ≤ j ≤ [\frac{n+1}{2}]  (11)

are linearly independent.

Now we claim that the f-vectors of the triangulations

Δ_{1}, Δ_{2}, ⋯, Δ[_{\frac{s+1}{2}}]; Δ_{0,0}, Δ_{0,1}, ⋯ Δ_{0,[\frac{n+1}{2}]}  (12)

are affinely independent. Consider the linear relation

\begin{aligned}[ & \frac{s+1}{2} & ] \\ & ∑ \\ & i=1 \end{aligned} a_{i}(f(X; Δ_{i}) − f(X; Δ_{0,0})) + \begin{aligned}[ & \frac{n+1}{2} & ] \\ & ∑ \\ & j=1 \end{aligned} b_{j}(f(X; Δ_{0,j}) − f(X; Δ_{0,0})) = 0.  (13)

The Dehn-Sommerville equations (3) and the equation (9) imply that

D(n)f(X; Δ_{0,j}) = D(n)f(X; Δ_{0}).

Therefore applying D(n) to (13) gives rise to

\begin{aligned}[ & \frac{s+1}{2} & ] \\ & ∑ \\ & i=1 \end{aligned} a_{i}(D(n)f(X; Δ_{i}) − D(n)f(X; Δ_{0})) = 0.  (14)

Then the linear independence of (8) implies that a_{i} = 0 in (14). Moreover, (13) becomes

\begin{aligned}[ & \frac{n+1}{2} & ] \\ & ∑ \\ & j=1 \end{aligned} b_{j}(f(X; Δ_{0,j}) − f(X; Δ_{0,0})) = 0.

Because (11) are linearly independent, we also conclude that b_{j} = 0.

The existence of triangulations (12) with affinely independent f-vectors means that the dimension of the left side of (5) is at least [\frac{s+1}{2}] + [\frac{n+1}{2}] = \frac{n+s+1}{2}, which is equal to the dimension of the right side. Consequently both sides of (5) are equal. This completes the proof of Theorem 2.

References

[BaL] Bayer, M., Lee, C.: Combinatorial aspects of convex polytopes. In: Handbook of Convex Geometry, Gruber, P.M., Wills, J.M.(ed), 485-534. Elsevier Science 1993

[BiL] Billera, L. J., Lee, C.: A proof of the sufficiency of McMullen’s conditions for f-vectors of simplicial convex polytopes. Jour. Combinatorial Theory (A) 31, 237-255 (1981)

[Br] Brøndsted, A.: An Introduction to Convex Polytopes. Graduate Texts in Math. vol.90. Berlin-Heidelberg-New York: Springer-Verlag 1983

[CY1] Chen, B.F., Yan, M.: Linear conditions on the number of faces of manifolds with boundary. (to appear in Adv. Math.)

[CY2] Chen, B.F., Yan, M.: Euler manifolds and their combinatorics. (preprint, 1994)

[G1] Grünbaum, B.: Convex Polytopes. Pure and Applied Math. vol.16. New York: Wiley-Interscience 1967 [G2] Grünbaum, B.: Polytopes, graphs, and complexes. Bull. Amer. Math. Soc.

vol.76, 1131-1201 (1970)

[JR] Jungerman, M., Ringel, G.: Minimal triangulations on orientable surfaces. Acta. Math. 145, 121-154 (1980)

[Ka] Katona, G.: A theorem of finite sets. In: Theory of Graphs, Proceeding of Tihany Conference, 1966, Erdös, P., Katona, G.(ed), 187-207. New York: Academic Press/Budapest: Akadémia Kiadó 1968

[Kl] Klee, V.: A combinatorial analogue of Poincaré’s duality theorem. Can. J. Math. 16, 517-531 (1964)

[Kr] Kruskal, J.B.: The number of simplices in a complex. In: Mathematical Optimization Techniques, 251-278. University of California Press 1963

[M] McMullen, P.: On the upper bound conjecture for complex polytopes. Jour. Combinatorial Theory (B) 10, 187-200 (1971)

[MS] McMullen, P., Shephard, G. C.: Convex Polytopes and Upper Bound Conjecture. London Math. Soc. Lecture Note Ser. 3. London: Cambridge University Press 1971

[R] Ringel, G.: Wie man die geschlossenen nichtorientierbaren Flächen in möglichst wenig Dreiecke zerlegen kann. Math. Ann. 130, 317-326 (1955)

[RS] Rourke, C.P., Sanderson, B.J.: Introduction to Piecewise-Linear Topology. Berlin-Heidelberg-New York: Springer-Verlag 1972

[So] Sommerville, D.M.Y.: The relations connecting the angle-sums and volume of a polytope in space of n-dimensions. Proc. Roy. Soc. London Ser. A 115, 103-119 (1927)

[St] Stanley, R. P.: On the number of faces of simplicial convex polytopes. Advances in Math. 35, 236-238 (1980)