Many triangulated three-spheres!

The news

Eran Nevo and Stedman Wilson have constructed \exp (K n^2) triangulations with n vertices of the 3-dimensional sphere! This settled an old problem which stood open for several decades. Here is a link to their paper How many n-vertex triangulations does the 3 -sphere have?

Quick remarks:

1) Since the number of facets in an n-vertex triangulation of a 3-sphere is at most quadratic in n, an upper bound for the number of triangulations of the 3-sphere with n vertices is \exp(n^2 \log n). For certain classes of triangulations, Dey removed in 1992  the logarithmic factor in the exponent for the upper bound.

2) Goodman and Pollack showed in 1986 that the number of simplicial 4-polytopes with n vertices is much much smaller \exp (O(n\log n)). This upper bound applies to simplicial polytopes of every dimension d, and Alon extended it to general polytopes.

3) Before the new paper the world record was the 2004 lower bound by Pfeifle and Ziegler – \exp (Kn^{5/4}).

4) In 1988 I constructed \exp (K n^{[d/2]}) triangulations of the d-spheres with n vertices.  The new construction gives hope to improve it in any odd dimension by replacing [d/2] by [(d+1)/2] (which match up to logn the exponent in the upper bound). [Update (Dec 19) : this has now been achieved by Paco Santos (based on a different construction) and Nevo and Wilson (based on extensions of their 3-D constructions). More detailed to come.]

Satoshi Murai and Eran Nevo proved the Generalized Lower Bound Conjecture.

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 . Let me tell you a little about it. For more background see the post: How the g-conjecture came about.

Face numbers and h-numbers

Let P be a (d-1)-dimensional simplicial polytope and let f_i(P) be the number of i-dimensional faces of P. The f-vector (face vector) of P is the vector f(P)=(f_{-1}(P),f_0(P),f_1(P),...).

Face numbers of simplicial d-polytopes  are nicely expressed via certain linear combinations called the h-numbers. Those are defined by the relation:

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

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).

The Euler-Poincare relation asserts that h_d(P)=(-1)^{d-1}\tilde{\chi}(P)=1=h_0(P). More is true. The Dehn-Sommerville relations state that h(P) is symmetric, i.e. h_i(P)=h_{d-i}(P) for every 0\leq i\leq d.

The generalized lower bound conjecture

In 1971, McMullen and Walkup posed the following conjecture, which is called the generalized lower bound conjecture (GLBC):

Let P be a simplicial d-polytope. Then

(A) the h-vector of P, (h_0,h_1,...,h_d) satisfies h_0 \leq h_1 \leq ... \leq h_{\lfloor d/2 \rfloor}.

(B) If h_{r-1}=h_r for some r \leq d/2 then P can be triangulated without introducing simplices of dimension \leq d-r.

The first part of the conjecture was solved by Stanley in 1980 using the Hard Lefschetz theorem for toric varieties. This was part of the g-theorem that we discussed extensively in a series of posts (II’, II, IIIB). In their paper, Murai and Nevo give a proof of part (B). This is remarkable!

Earlier posts on the g-conjecture:

I: (Eran Nevo) The g-conjecture I

I’ How the g-conjecture came about

II (Eran Nevo) The g-conjecture II: The commutative-algebra connection

III (Eran Nevo) The g-conjecture III: Algebraic shifting

B: Billerafest