(Eran Nevo) The g-Conjecture I

This post is authored by Eran Nevo. (It is the first in a series of five posts.)


Peter McMullen

The g-conjecture

What are the possible face numbers of triangulations of spheres?

There is only one zero-dimensional sphere and it consists of 2 points.

The one-dimensional triangulations of spheres are simple cycles, having n vertices and n edges, where n\geq 3.

The 2-spheres with n vertices have 3n-6 edges and 2n-4 triangles, and n can be any integer \geq 4. This follows from Euler formula.

For higher-dimensional spheres the number of vertices doesn’t determine all the face numbers, and for spheres of dimension \geq 5 a characterization of the possible face numbers is only conjectured! This problem has interesting relations to other mathematical fields, as we shall see.

A good place to read more about it is Stanley’s book `Combinatorics and Commutative algebra‘. First let’s fix some notation.

f \leftrightarrow h vectors

A collection K of subsets of [n]=\{1,2,...,n\} is called a (finite abstract) simplicial complex if it is closed under inclusion, i.e. S\subseteq T\in K implies S\in K. Note that if K is not empty (which we will assume from now on) then \emptyset \in K, and is of dimension -1. The elements of K are called faces. The fvector (face vector) of K is f(K)=(f_{-1},f_0,f_1,...) where f_{i-1}=|\{T\in K: |T|=i\}|. For example, if K is the (d-1)-simplex then f_{i-1}(K)=\binom{d}{i}.

From now on, let’s assume that K is a simplicial (d-1)-sphere, meaning that its geometric realization is homeomorphic to the (d-1)-dimensional sphere. What are the relations among the f_j(K)‘s? We know that the reduced Euler characteristic is \tilde{\chi}(K)=\sum_{-1\leq i\leq d-1}(-1)^i f_{i}(K)=(-1)^{d-1}. There are more linear relations, called the Dehn-Sommerville relations. They have a nicer form when expressed in terms of the hvector of K, defined by

\sum_{0\leq i\leq d}h_i(K)x^{d-i}= \sum_{0\leq i\leq d}f_{i-1}(K)(x-1)^{d-i}.

We see that there are invertible maps f(K) \leftrightarrow h(K).

What’s called “Stanley’s trick” is a convenient way to practically compute one from the other, as illustrated in the difference table below, taken from Ziegler’s book `Lectures on Polytopes’, p.251:


1           6

1          5            12

1          4           7             8

h= (1        3          3            1)

Here, we start with the f-vector of the Octahedron (1,6,12,8) (bold face entries) and take differences as shown in this picture to end with the h-vector (1,3,3,1).

We see that h_d(K)=(-1)^{d-1}\tilde{\chi}(K)=1=h_0(K). More is true. The Dehn-Sommerville relations state that h(K) is symmetric, i.e. h_i(K)=h_{d-i}(K) for every 0\leq i\leq d. This result can be proved combinatorially, for the larger family of Eulerian posets, and actually these relations span all the linear equalities among the f-vector of K.

What about inequalities?


We say that a vector h is an M-vector (M for Macaulay) if it is the f-vector of a multicomples, i.e. of a collection of multisets (elements can repeat!) closed under inclusion. For example, h=(1,1,1) is an M-vector, as is demonstrated by the multicomplex \{1=x^0,x,x^2\}, written in monomial notation – the exponent tells how many copies of x to take. Macaulay gave a numerical characterization of such vectors. (The proof uses compression – see this post for a general description of the method.) We will revisit Macaulay theorem in the next part, when discussing face rings.

g-vector and the g-theorem

Let g_0(K):=h_0(K)=1, g_i(K):=h_i(K)-h_{i-1}(K) for 1\leq i\leq \lfloor d/2\rfloor. g(K):=(g_0(K),...,g_{\lfloor d/2\rfloor}(K)). By the Dehn-Sommerville relations, f(K) can be recovered from g(K). McMullen asked whether g(K) is always an M-vector, and conjectured that this the case if K is the boundary of a simplicial polytope. He conjectured further that any M-vector is the g-vector of the boundary of a simplicial polytope.

A major result is the proof of this conjecture in the polytopal case, known as the g-theorem, which gives a complete characterization of the f-vectors of boundaries of simplicial polytopes. Billera and Lee constructed in 1979 a simplicial polytope with boundary K satisfying g(K)=m for any given M-vector m. Stanley proved, in the same year, that if K is the boundary of a convex polytope then g(K) is an M-vector. We will discuss this proof in the next section.

The g-conjecture (or, one version of it) is:

If K is a simplicial sphere then g(K) is an M-vector.

This conjecture is around since McMullen first asked it in 1970.

Next time: how does Stanley’s proof go?

This entry was posted in Combinatorics, Convex polytopes, Guest blogger, Open problems and tagged , , , , , , , . Bookmark the permalink.

13 Responses to (Eran Nevo) The g-Conjecture I

  1. Gil Kalai says:

    Thanks, Eran! The g-conjecture for spheres is probably the single problem I worked longest and hardest to solve (without success), and several other people worked on it too. There are various interesting problems around it and it is connected to all sort of fascinating mathematics.

  2. Pingback: How the g-Conjecture Came About? « Combinatorics and more

  3. Pingback: (Eran Nevo) The g-Conjecture III: Algebraic Shifting « Combinatorics and more

  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

  6. Pingback: Convex Polytopes: Seperation, Expansion, Chordality, and Approximations of Smooth Bodies | Combinatorics and more

  7. Pingback: Hodge Theory in Combinatorics | Matt Baker's Math Blog

  8. Pingback: Eran Nevo: g-conjecture part 4, Generalizations and Special Cases | Combinatorics and more

  9. Gil Kalai says:

    Here is a beautiful survey on the g-conjecture by Ed Swartz “35 Years and Counting” https://arxiv.org/abs/1411.0987
    The abstract
    It has been 35 years since Stanley proved that f-vectors of boundaries of simplicial polytopes satisfy McMullen’s conjectured g-conditions. Since then one of the outstanding questions in the realm of face enumeration is whether or not Stanley’s proof could be extended to larger classes of spheres. Here we hope to give an overview of various attempts to accomplish this and why we feel this is so important. In particular, we will see a strong connection to f-vectors of manifolds and pseudomanifolds. Along the way we have included several previously unpublished results involving how the g-conjecture relates to bistellar moves and small g_2, the topology and combinatorics of stacked manifolds introduced independently by Bagchi and Datta, and Murai and Nevo, and counterexamples to over optimistic generalizations of the g-theorem.

  10. Pingback: Beyond the g-conjecture – algebraic combinatorics of cellular spaces I | Combinatorics and more

  11. Pingback: Amazing: Karim Adiprasito proved the g-conjecture for spheres! | Combinatorics and more

  12. Pingback: Karim Adiprasito: The g-Conjecture for Vertex Decomposible Spheres | Combinatorics and more

  13. Pingback: To Cheer You Up in Difficult Times 31: Federico Ardila’s Four Axioms for Cultivating Diversity | 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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s