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: 
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
Let’s move now to flag numbers. Consider a d-polytopes P. for a set 
{-1,0,1,2,…,d-1,d}, 
{ 
} , 
, define the flag number 
as the number of chains of faces 
, where 
. 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 
be the dth Fibonacci number. (
, 
, 
, 
, etc.) Bayer and Billera proved:
Theorem: the affine dimension of flag numbers of d-polytopes is 
There are many linear relations among the flag numbers that are implied by Euler’s theorem. For example: 
. This follows from the fact that every 1-polytope has 2 vertices. (This is Euler’s formula for dimension 1.) Another example: 
. 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: 
and 
. Let’s understand the first of the two: Fix a flag of faces
, where 
and 
.
Consider all faces G between 
and 
. This set of faces is in one to one correspondence with the set of faces of a 4-dimensional polytope Q. A k-face 
between and corresponds to a (k-2)-face of Q. Euler’s formula asserts that 
. Summing over all flags 
gives us the required formula.
The proof of the second relation is similar except that in this case Q is 5-dimensional, so Euler’s theorem asserts that the alternating sum is 2. This accounts for the term 
when we sum over all chains 
.
Now we can explain the connection to Fibonacci numbers.
If 
{-1,0,1, …,d} and S contains two consecutives integers i and i+1, consider the pair i and i+1 of consecutive integers that S contains with i nonnegative and minimal. Let j be the maximal element of S below i. Write R= S\i. Just like the two examples above, we can express in terms of the flag numbers 
and 
, where m ranges over all integers between j and i.
Ha! but this shows that if S contains two consecutive elements then can be expressed as a linear combination of flag numbers with “smaller” indices! This implies that every flag number can be expressed as a linear combination of those with no consecutive integers and this gives us the Fibonacci numbers.
The harder part of the Bayer-Billera Theorem was to construct 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. But proving that the flag numbers of all these polytopes are affinely independent is harder. By now there are a few other constructions.
3. The CD index
Every flag number of d-polytopes can be expressed as a linear combination of flag numbers with -1 and d elements of S and with no two consecutive integers. Are there other Fibonacci numbers of parameters of d-polytopes? The cd-index discovered by Fine is a beautiful mysterious parameters for d-polytopes, each given by a linear combination of flag numbers.
Define h flag numbers: 
.
Associate for every subset S of {0,1,…,d-1} a monomial W(S) in non commuting variables a and b. You simply take a word in a’s and b’s where you take a for indices in S and b for indices not in S. For example, if d=10 and S={0,3,6,7} associate to S the monomial W(S)=abbabbaabb.
Write a polynomial with non commutative variables a and b:
consider two new variables c=a+b d=ab+ba.
Express 
as a polynomial in c and d. This is possible! (But requires a proof.)
The cd-index of P are the coefficients of the monomials in the new variables c and d.
Excercise (A solution by Jonathan Vos Post appears in the comment part): What is the cd-index of the 24-cell?
Like this:
Like Loading...
Related
Combinatorics and more 
Pingback: Carnival of Mathematics « Rigorous Trivialities
It seems clear that, in the 24-cell exercise, that the beautiful self-dual 4-polytope has 24 octahedral facets. Hence f_0 = f_3 = 24. Further, f_1 = f_2 =96. Then f_{02} = 288, and f_{03}=192. Anything left to compute?
Pingback: Why Planar Graphs are so Exceptional « Combinatorics and more
Pingback: Bài 3: Phá bỏ Quy tắc Một Phần BaĐịa chỉ thuê máy ảnh & máy quay chuyên nghiệp tại Hà Nội | Thuê máy ảnh
Pingback: Beyond the g-conjecture – algebraic combinatorics of cellular spaces I | Combinatorics and more
Pingback: [Học chụp ảnh] Bố cục trong nhiếp ảnh - Bài 3 | Cameraphone.vn - Cameraphone
Pingback: [Học chụp ảnh] Bố cục trong nhiếp ảnh – Bài 3 – CAMERAPHONE
Pingback: To Cheer You Up in Difficult Times 31: Federico Ardila’s Four Axioms for Cultivating Diversity | Combinatorics and more