Archive for the ‘Convex polytopes’ Category

Euler’s Formula, Fibonacci, the Bayer-Billera Theorem, and Fine’s CD-index

June 22, 2008

 

Bill Gessley proving Euler’s formula (at UMKC)

 

In the earlier post about Billerafest I mentioned the theorem of Bayer and Billera on flag numbers of polytopes. Let me say a little more about it.

1. Euler

Euler’s theorem asserts that for a 3-polytope P

V-E+F=2.  

The extension to d-dimensions asserts that for every d-polytope

The Euler Relation: f_0(P) - f_1(P) +F_2(P) + \dots + (-1)^d f_{d-1}(P) = 1 - (-1)^d.

There were several incomplete proofs of Euler’s theorem in the late 19th century, but the first complete proof came via Poincare’s work in algebraic topology and the Euler-Poincare theorem. Later, simple geometric proofs were found and the gap in certain 19th theory proofs which relied on an unproved assumption of shellability was completed when Bruggesser and Mani proved in 1970 that the boundary of every d-polytope is shellable.

 

2. Fibonacci

 Fibonacci sunflower

Let’s move now to flag numbers. Consider a d-polytopes P. for a set S \subset {-1,0,1,2,…,d-1,d}, S={ i_1,i_2,\dots,i_k} , i_1<i_2< \dots, define the flag number f_S as the number of chains of faces F_1 \subset F_2 \subset \dots F_k, where \dim F_j=i_j.  We will assume from now on that S contains both ‘-1′, and ‘d’. (Adding or deleting these entries from S does not change the value of the flag number.) Let c_d be the dth Fibonacci number. (c_1=1, c_2=2, c_3=3, c_4=5, etc.)  Bayer and Billera proved:

Theorem: the affine dimension of flag numbers of d-polytopes is c_d-1

There are many linear relations among the flag numbers that are implied by Euler’s theorem. For example: f_{01}=2f_1. This follows from the fact that every 1-polytope has 2 vertices. (This is Euler’s formula for dimension 1.) Another example: f_{02}=f_{12}. This follows from the fact that a polygon has the same number of vertices as edges which is Euler’s formula for d=2. Here are two, more complicated, examples: f_{1569}=f_{1469}-f_{1369}+f_{1269} and f_{1679}=f_{1579}-f_{1479}+f_{1379}-f_{1279}+2f_{179}. Let’s understand the first of the two: Fix a flag of faces (more…)

Billerafest

June 12, 2008
Lou Billera
I am unable to attend the conference taking place now at Cornell, but I send my warmest greetings to Lou from Jerusalem. The titles and abstracts of the lectures can be found here. Let me tell you about two theorems by Lou.
 
The first is the famous g-theorem: The g-theorem is a complete description of f-vectors (= vecors of face numbers) of simplicial d-polytopes. This characterization was proposed by Peter McMullen in 1970, and it was settled in two works. Billera and Carl Lee proved the sufficiency part of McMullen’s conjecture, namely for every sequence of numbers which satisfies McMullen’c conjecture they constructed a simplicial d-polytope P whose f-vector is the given sequence. Richard Stanley proved the necessity part based on the hard Lefschetz theorem in algebraic geometry. The assertion of the g-conjecture (the necessity part) for triangulations of spheres is open, and this is probably the one single problem I spent the most time on trying to solve. 
 
The second theorem is a beautiful theorem by Margaret Bayer and Billera. Consider general d-polytopes. for a set S \subset {0,1,2,…,d-1}, S={ i_1,i_2,\dots,i_k} , i_1<i_2< \dots, define the flag number f_S as the number of chains of faces F_1 \subset F_2 \subset \dots F_k, where \dim F_j=i_j.  Bayer and Billera proved that the affine dimension of flag numbers of d-polytopes is c_d-1 where c_d is the dth Fibonacci number. (c_1=1, c_2=2, c_3=3, c_4=5, etc.) The harder part of this theorem was to construct c_d d-polytopes whose sequences of flag numbers are affinely independent.  The construction is simple: It is based on polytopes expressed by words of the form PBBPBPBBBPBP  where you start with a point, and P stands for “take a pyramid” and B stands for “take a bipyramid.” And the word starts with a P (to the left) and has no two consecutive B’s.
 
Let’s practice the notions of f-vectors and flag vectors on the 24-cell   . (The figure is a 3-dimensional projection into one of the facets of the polytope.)
 
 
 
This  4-polytope has 24 octahedral facets. It is self dual.
So f_0=f_3=24. And f_1=f_2=96. And f_{02}=288, f_{03}=192, etc. 

Five Open Problems Regarding Convex Polytopes

May 7, 2008

  

The problems 

1. The 3^d conjecture

A centrally symmetric d-polytope has at least 3^d non empty faces.

2. The cube-simplex conjecture

For every k there is f(k) so that every d-polytope with d \ge f(k) has a k-dimensional face which is either a simplex or combinatorially isomorphic to a k-dimsnional cube.

3. Barany’s question

For every d-dimensional polytope P and every k, 0 \le k \le d-1,  is it true that f_k(P) \ge \min (f_0(P),f_{d-1}(P))?

(In words: the number of k-dimensional faces of P is at least the minimum between the number of vertices of P and the number of facets of P. )

4.  Fat 4-polytopes

For 4-polytopes P, is the quantity (f_1(P)+f_2(P))/(f_0(P)+f_3(P)) bounded from above by some absolute constant? 

5.  five-simplicial five-simple polytopes

Are there 5-simplicial 5-simple 10-polytopes? Or at least 5-simplicial 5-simple d-polytope for some d?

(A polytope P is k-simplicial if all its faces of dimension at most k, are simplices. A polytope P is k-simple if its dual P* is k-simplicial.)

And on a personal note: My beloved, beautiful,  and troubled country celebrates 60 today: happy birthday! 

Update (May 12): David Eppstein raised in a followup a sort of a dual question to Barany’s. For a d-polytope with n vertices and n facets what is the maximal number of k-faces. For a fixed d and large n the free join of pentagons is conjectured to give asymptotically the best upper bound.

(more…)