Tag Archives: CD-index

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


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


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 Continue reading