How the g-Conjecture Came About

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

1) Euler’s theorem

euler1

Euler

Euler’s famous formula V-E+F=2 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 d-dimensional polytopes P is

f_0(P)-f_1(P)+f_2(P)+\dots+(-1)^{d-1}f_{d-1}(P)=1-(-1)^d.

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 f_0-f_1+f_2 = 2. 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 F is the set of all faces containing F. (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 v as the simplicial complex obtained by removing v from all faces in the star of v. 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: 2f_1=3f_2. (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 (d-1)-dimensional spheres there are [(d+1)/2] 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 h-vector described in Eran’s post.

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

h_0=1,

h_1 = f_0-d,

h_2=f_1-(d-1)f_0+{{d} \choose {2}},

h_3=f_2-(d-2)f_1+{{d-1} \choose {2}}f_0-{{d} \choose {3}},

and so on. Lets see also the highest h-numbers

h_{d-1}=f_{d-2} - 2 f_{d-3} + 3 f_{d-4} - ... + (-1)^{(d-1)}(d-2)

and

h_d = f_{d-1}- f_{d-2} + f_{d-3} - \dots +(-1)^d.

The Dehn-Sommerville relations read simply h_i = h_{d-i}. (Note that h_0=h_d 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 d-polytopes extend to triangulations of (d-1)-dimensional spheres, and even to (d-1)-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 (d-1) so that all the links of faces satisfy the Euler relation.)

Victor_Klee_MFO

Vic Klee

3) The Lower Bound Conjecture

Simplicial 3-polytopes satisfy

f_1 = 3f_0-6.

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

f_1 \ge 4f_0 - 10

and simplicial 5-polytopes satisfy

f_1 \ge 5f_0-15

and so on: Simplicial d-polytopes satisfy

f_1 \ge df_0- {{d+1} \choose {2}}.

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

In terms of the h-numbers the lower bound theorem amounts to the inequality h_1 \le h_2.

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 d-polytopes with n 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 h-vectors and noting that the upper bound theorem has a simple description in terms of the h-numbers.

For every simplicial d-polytope h_k \le {{n-d+k-1} \choose {k}}.

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 h_1 \le h_2. The fact that 1=h_0 \le h_1 simply asserts that every d-polytope has at least d+1 vertices. We also know that h_i = h_{d-i}.

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

h_0\le h_1\le h_2\le\dots \le h_m, where m=[d/2].

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 g-conjecture relied on one more piece of machinery. This is Macaulay’s 1927 theorem which gives a complete description of f-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 f-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) (h_0,h_1,\dots, h_{d-1}) is the h-vector of a simplicial d-polytope

2) (h_0,h_1,\dots, h_{d-1}) is the h-vector of a triangulation of a (d-1)-dimensional sphere.

3) The following  conditions are satisfied:

a) h_k=h_{d-k}, for every k.

b) Write g_i: = h_i-h_{i-1} for i=1,2,\dots,[d/2]. Then the vector (g_0,g_1,\dots, g_{[d/2]}) 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.

About these ads
This entry was posted in Combinatorics, Convex polytopes, Open problems and tagged , , , , . Bookmark the permalink.

5 Responses to How the g-Conjecture Came About

  1. D. Eppstein says:

    Re your claim that the first complete proof of Euler’s formula is by Poincaré: supposedly there’s a proof in Legendre’s 1794 Élements de géométrie, the one involving sums of spherical angles.

  2. Gil Kalai says:

    Dear David, I meant that the first proof in high dimensions was by Poincare. I suppose Euler had a proof of his formula, didn’t he?

  3. D. Eppstein says:

    Euler’s attempt at a proof is in E231. The basic idea is to remove one vertex at a time and consider a polyhedron with one fewer vertex. It is possible to do so, but it requires more care than Euler takes: he needs some assumption such as convexity in order to perform this removal (the Schönhardt polyhedron cannot have any vertex removed in this way) but it is clear from his Corollary 4 describing two different ways of removing a degree-four vertex that he does not intend to assume convexity. So I can’t accept this as being a correct proof.

  4. Pingback: Satoshi Murai and Eran Nevo proved the Generalized Lower Bound Conjecture. | Combinatorics and more

  5. Pingback: Richard Stanley: How the Proof of the Upper Bound Theorem (for spheres) was Found | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s