(Eran Nevo) The g-Conjecture I

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

mcmullen

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 f-vector (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 h-vector 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

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?

M-vectors

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?

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

5 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

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