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