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? **

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