<<

. 13
( 14 .)



>>

Euler™s formula has to do with counting the number of faces of dimensions
0, 1 and 2. Namely, let fi be the number of i-dimensional faces.

Euler™s Formula. For any 3-polytope:
f0 ’ f1 + f2 = 2.



Let us verify this relation for the cube and the permutohedron, see Figures
18 and 19.

81
4123 1423


4132 1243
1432
2143


4312 1342 1234



2134
1324

3142
3412

3124
2314
3421


3241 3214



Figure 19: The permutohedron.


f0 f1 f2 f0 ’ f1 + f2

Cube 8 12 6 8 ’ 12 + 6 = 2

Permutohedron 24 36 14 24 ’ 36 + 14 = 2

From a modern mathematical point of view there is no di¬culty in de¬n-
ing higher-dimensional polytopes. Thus, a d-polytope is a full-dimensional
bounded intersection of closed halfspaces in Rd . Such higher-dimensional
polytopes have taken on great practical signi¬cance in the last ¬fty years
because of their importance for linear programming. The term “linear pro-
gramming” refers to techniques for optimizing a linear function subject to
a collection of linear constraints. The linear constraints cut out a feasible
region of space, which is a d-polytope (possibly unbounded in this case).
The combinatorial study of the structure of polytopes has interacted very
fruitfully with this applied area.

It can be shown that the same de¬nition of the faces of a polytope works

82
also in higher dimensions (namely “the possible areas of contact if the poly-
tope is made to touch a plane surface in Rd ”), and that there are only ¬nitely
many faces of each dimension 0, 1, . . . , d ’ 1. Thus we may de¬ne the number
fi of i-dimensional faces for i = 0, 1, . . . , d ’ 1. These numbers for a given
polytope P are collected into a string
f (P ) = (f0 , f1 , . . . , fd’1 ),
called the f -vector of P . For instance, we have seen that f (cube) = (8, 12, 6)
and f (permutohedron) = (24, 36, 14).

Is there an Euler formula for f -vectors in higher dimensions? This ques-
tion was asked early on, and by the mid-1800™s some mathematicians had
discovered the following beautiful fact.

Generalized Euler Formula. For any d-polytope:
f0 ’ f1 + f2 ’ · · · + (’1)d’1 fd’1 = 1 + (’1)d’1 .



However, the early discoverers experienced serious di¬culty with proving
this formula. It is generally considered that the ¬rst complete proof was
given around the year 1900 by Henri Poincar´.e

Having seen this formula it is natural to ask: What other relations, if
any, do the face numbers fi satisfy? This question opens the doors to a huge
and very active research area, pursued by combinatorialists and geometers.
Many equalities and inequalities are known for various classes of polytopes,
such as upper bounds and lower bounds for the numbers fi in terms of the
dimension d and the number f0 of vertices.

The boldest hope one can have for the study of f -vectors of polytopes is
to obtain a complete characterization. By this is meant a reasonably simple
set of conditions by which one can recognize if a given string of numbers is
the f-vector of a d-polytope or not. For instance, one may ask whether
(14, 89, 338, 850, 1484, 1834, 1604, 971, 380, 76) (29)
is the f -vector of a 10-polytope? We ¬nd that
14 ’ 89 + 338 ’ 850 + 1484 ’ 1834 + 1604 ’ 971 + 380 ’ 76 = 0,

83
in accordance with the generalized Euler formula. Had this failed we would
know for sure that we are not dealing with a true f -vector, but agreeing with
the Euler formula is certainly not enough to draw any conclusion. What
other “tests” are there, strong enough to tell for sure whether this is the
f -vector of a 10-polytope?

An answer is known for dimension 3; namely, (f0 , f1 , f2 ) is the f -vector
of a 3-polytope if and only if

(i) f0 ’ f1 + f2 = 2,
(ii) f0 ¤ 2f2 ’ 4,
(iii) f2 ¤ 2f0 ’ 4.

However, already the next case of 4 dimensions presents obstacles that with
present methods are unsurmountable. Thus, no characterization of f -vectors
of general polytopes is known. But if one narrows the class of polytopes to
the so called “simplicial” ones there is a very substantial result that we will
now formulate.

A d-simplex is a d-polytope which is cut out by exactly d + 1 plane cuts.
In other words, it has d + 1 maximal faces, which is actually the minimum
possible for a d-polytope. A 1-simplex is a line segment, a 2-simplex is a
triangle, a 3-simplex is a tetrahedron, and so on; see Figure 20. In general,
a d-simplex is the natural d-dimensional analogue of the tetrahedron.




Figure 20: A d-simplex, d = 1, 2, 3.

A d-polytope is said to be simplicial if all its faces are simplices. It comes
to the same to demand that all maximal faces are (d ’ 1)-simplices. For
instance, a 3-polytope is simplicial if all 2-faces are triangular, as in Figure
21; so the octahedron and icosahedron are examples of simplicial polytopes

84
Figure 21: A simplicial 3-polytope.

but the cube and permutohedron are not. If a polytope is simplicial then its
faces form a simplicial complex in the sense de¬ned in Section 9. The class
of simplicial polytopes is special from some points of view, but nevertheless
very important in polytope theory. For instance, if one seeks to maximize the
number of i-faces of a d-polytope with n vertices, the maximum is obtained
simultaneously for all i by certain simplicial polytopes.

In 1970 Peter McMullen (b. 1942) made a bold conjecture for a characteri-
zation of the f -vectors of simplicial polytopes. A key role in his proposed con-
ditions was played by certain “g-numbers,” so his conjecture became known
as the “g-conjecture.” In 1980 two papers, one by Louis Joseph Billera (b.
1943) and Carl William Lee (b. 1954) and one by Richard Peter Stanley (b.
1944), provided the two major implications that were needed for a proof of
the conjecture. Their combined e¬orts thus produced what is now known as
the “g-theorem.” To state the theorem we need to introduce an auxiliary
concept.

By a multicomplex we mean a nonempty collection M of monomials in
indeterminates x1 , x2 , . . . , xn such that if m ∈ M and m divides m then m ∈
M . Figure 22 shows the multicomplex M = {1, x, y, z, x2 , xy, yz, z 2 , x2 y, z 3 }
ordered by divisibility.

An M -sequence is a sequence (1, a1 , a2 , a3 , . . .) such that each ai is the


85
x 2y z3 2




x2 z2
xy yz 4




x y z 3




1 1



Figure 22: A multicomplex.

number of monomials of degree i in some ¬xed multicomplex. For instance,
the M -sequence coming from the multicomplex M in Figure 22 is (1, 3, 4, 2).
A multicomplex and an M -sequence can very well be in¬nite, but only ¬nite
ones will concern us here. If some zeros are added or removed at the end of
a ¬nite M -sequence it remains an M -sequence.

The “M ” in M -sequence is mnemonic both for “multicomplex” and for
“Macaulay”, in honor of Francis Sowerby Macaulay (1862-1937) who ¬rst
seems to have studied the concept in a paper from 1927. Macaulay™s purpose
was entirely algebraic (to characterize so called Hilbert functions of certain
graded algebras), but the underlying combinatorics of his investigations has
turned out to have far-reaching rami¬cations.

We are now ready to formulate the g-theorem, characterizing the f -
vectors of simplicial d-polytopes. Let δ be the greatest integer less than
or equal to d/2, and let Md = (mi,j ) be the matrix with (δ + 1) rows and d
columns and with entries
d+1’i i
mi,j = ’ , for 0 ¤ i ¤ δ, 0 ¤ j ¤ d ’ 1.
d’j d’j

Here we are using the binomial coe¬cients, de¬ned by

n n!
= ,
k k! · (n ’ k)!

86
where n! = n · (n ’ 1) · (n ’ 2) · · · 2 · 1, and 0! = 1. (The factorial n! was
already used in connection with equation (17), but we repeat the de¬nition
here for the reader™s convenience.)

For example, with d = 10 we get
10 + 1 ’ 2 2 9! 2!
m2,8 = ’ = ’ = 36 ’ 1 = 35,
10 ’ 8 10 ’ 8 2! · 7! 2! · 0!
and the whole matrix is
« 
11 55 165 330 462 462 330 165 55 11
¬ 1 10 45 120 210 252 210 120 45 9 ·
¬ ·
¬0 1 9 36 84 126 126 84 35 7 ·
M10 = ¬ ·
¬0 0 8 28 56 70 55 25 5 ·
1
¬ ·
0 0 7 21 34 31 15 3 
0 1
00 0 0 1 5 10 10 5 1


These matrices Md determine a very surprising link between M -sequences
and f -vectors.

The g-theorem. The matrix equation
f = g · Md
gives a one-to-one correspondence between f -vectors f of simplicial d-polytopes
and M -sequences g = (g0 , g1 , . . . , gδ ).

The equation f = g · Md is to be understood as follows. Multiply each
entry in the ¬rst row of Md by g0 , then multiply each entry in the second row
by g1 , and so on. Finally, after all these multiplications add the numbers in
each column. Then the ¬rst column sum will equal f0 , the second column
sum will equal f1 , and so on.

To exemplify the power of this theorem let us return to a question posed
earlier; namely, is the vector f displayed in equation (29) the f -vector of a
10-polytope? This question can now be answered if sharpened from “10-
polytope” to “simplicial 10-polytope”. Easy computation shows that
f = (1, 3, 4, 2, 0, 0) · Md ,

87
and we know from Figure 22 that (1, 3, 4, 2, 0, 0) is an M -sequence. Hence, f
is indeed the f -vector of some simplicial 10-polytope.

Having seen this, one can wonder if we were just lucky with this relatively
small example. Perhaps for large d it is as hard to determine if a sequence
is an M -sequence as to determine if a sequence is an f -vector coming from a
simplicial polytope. This is not the case. There exists a very easy criterion
in terms of binomial coe¬cients that quickly tests an integer sequence for
being an M -sequence. We will however not state it here.

The proof of the g-theorem is very involved and calls on a lot of math-
ematical machinery. The part proved by Billera and Lee ” that for every

<<

. 13
( 14 .)



>>