How the g-Conjecture Came About

Update: Slides from a great 2014 lecture on the g-conjecture by Lou Billera in the conference celebrating Richard Stanley’s 70th birthday.

This post complements Eran Nevo’s first  post on the -conjecture

1) Euler’s theorem

Euler

Euler’s famous formula for the numbers of vertices, edges and faces of a  polytope in space is the starting point of many mathematical stories. (Descartes came close to this formula a century earlier.) The formula for -dimensional polytopes is

The first complete proof (in high dimensions) was provided by Poincare using algebraic topology. Earlier geometric proofs were based on “shellability” of polytopes which was only proved a century later. But there are elementary geometric proofs that avoid shellability.

2) The Dehn-Sommerville relations

Dehn

Consider a 3-dimensional simplicial polytope, –namely, a polytope all of whose faces are triangles. We have Euler’s relation In addition, we can look at the links of faces of various dimension and apply Euler’s theorem to them.

Let me review what stars and links are:  The star of a vertex is simply the collection of all faces containing it. And the star of a face is the set of all faces containing . (This definition of stars applies to a very general notion of complexes.) Now, for simplicial polytopes, or for general simplicial complexes, we can define the link of a vertex  as the simplicial complex obtained by removing from all faces in the star of . The link of an edge or a higher dimensional face is defined in a similar way.

Now, lets see: The link of every vertex of a simplicial 3-polytope can be regarded as the faces of a simplicial 2-polytope (a polygon). When we apply Euler’s relation and sum over all vertices we obtain the relation: . (The same relation is obtained by summing Euler’s relation over all links of edges.)

The Dehn-Sommerville relations extend this observation to higher dimensions. It turns out that for triangulations of -dimensional spheres there are [] linear relations among the face numbers.

It turns out also that certain linear combinations of face numbers are more appropriate to describe the combinatorics of the face numbers than the face numbers themselves. This leads to the -vector described in Eran’s post.

As explained in Eran’s post, the -numbers of simplicial -polytopes are defined in terms of the face numbers by:

and so on. Lets see also the highest -numbers

and

.

The Dehn-Sommerville relations read simply . (Note that is  Euler’s relation.)

The Dehn-Sommerville relations apply to much more general class of complexes. This was studied in a paper by Victor Klee. The Dehn-Somerville relations for simplicial -polytopes extend to triangulations of -dimensional spheres, and even to -dimensional “homology spheres”. And we can take the term “homology sphere” in the most relaxed sense: we can just require that the entire complex and all links of faces have the same rational homology groups as spheres of the same dimension. In fact, we can go beyond spheres: Odd-dimensional triangulations of closed manifolds are O.K. too. (The ultimate generality described by Klee for the Dehn-Sommerville relations– (without altering the relations themselves which would allow even greater generality –) is for “Eulerian simplicial complexes”, i.e., simplicial complexes of dimension so that all the links of faces satisfy the Euler relation.)

Vic Klee

3) The Lower Bound Conjecture

Simplicial 3-polytopes satisfy

.

The lower bound conjecture asserts that simplicial 4-dimensional polytopes satisfy

and simplicial 5-polytopes satisfy

and so on: Simplicial -polytopes satisfy

.

This conjecture was made by Grunbaum (I think) and was open until proved in 1970 by David Barnette.

In terms of the -numbers the lower bound theorem amounts to the inequality .

Branko Grunbaum

David Barnette

4) The Upper Bound Conjecture

1970 was a good year. A few months after Barnette proved the lower bound conjecture, Peter McMullen proved the upper bound conjecture. Motzkin’s upper bound conjecture asserts that among all -polytopes with  vertices, the cyclic polytope has the maximum number of facets. This conjecture can easily be reduced to the case of simplicial polytopes. One of the important ingredients in McMullen’s proof was the introduction of the -vectors and noting that the upper bound theorem has a simple description in terms of the -numbers.

For every simplicial -polytope .

5) McMullen-Walkup Generalized Lower Bound Theorem

The next step was a natural but far-reaching extension of the lower bound inequality. Recall that the lower bound inequality asserts that . The fact that  simply asserts that every -polytope has at least vertices. We also know that .

McMullem and Walkup’s  “generalized lower bound conjecture” asserts that for every simplicial -polytope,

, where [].

McMullen and Walkup also formulated an important conjecture about the cases of equality.

Update, March 2012: Satoshi Murai and Eran Nevo have just proved the 1971 generalized lower bound conjecture of McMullen and Walkup, in their  paper On the generalized lower bound conjecture for polytopes and spheres .

6) Macaulay’s theorem and the Kruskal-Katona theorem

The -conjecture relied on one more piece of machinery. This is Macaulay’s 1927 theorem which gives a complete description of -vectors of multicomplexes. Such vectors are called M-vectors. Macaulay’s theorem is closely related to the Kruskal-Katona theorem that we already discussed which gives a complete description of -vectors of simplicial complexes. (We will come back to Kruskal-Katona’s theorem and to the precise numerical description of Macaulay’s theorem some other time.)

7) The g-Conjecture

In 1971 McMullen proposed the g-conjecture. He made the conjecture only for simplicial polytopes and also asked if it can be extended to general triangulations of spheres.

Here is the conjecture (also for spheres) again:

The following conditions are equivalent

1) () is the -vector of a simplicial -polytope

2) () is the -vector of a triangulation of a -dimensional sphere.

3) The following  conditions are satisfied:

a) , for every .

b) Write for . Then the vector is an M-vector.

Part b) of 3) consists of the generalized lower bound inequalities of McMullen and Walkup and additional non-linear inequalities from Macaulay’s theorem. Eran’s second post will revisit Macaulay’s theorem.