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

F_1 \subset F_6\subset F_9, where \dim F_1=1,  \dim F_6 =6 and \dim F_9=9.

Consider all faces G between F_1 and F_6. This set of faces is in one to one correspondence with the set of faces of a 4-dimensional polytope Q.  A k-face H between F_1 and F_6 corresponds to a (k-2)-face of Q. Euler’s formula asserts that f_0(Q)-f_1(Q)+f_2(Q)-f_3(Q)=0. Summing over all flags F_1 \subset F_6 \subset F_9 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 2f_{179} when we sum over all chains F_1 \subset F_7 \subset F_9.

Now we can explain the connection to Fibonacci numbers.

If S \subset {-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 f_S in terms of the flag numbers f_R and f_{R \cup m}, where m ranges over all integers between j and i.

Ha! but this shows that if S contains two consecutive elements then f_S 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 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. 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 f_S 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 c_d parameters for d-polytopes, each given by a linear combination of flag numbers.

Define h flag numbers: h_S = \sum_{T \subset S} (-1)^{|S \backslash T|}f_T .

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:

\Psi= \sum_S h(S) W(S).

consider two new variables c=a+b d=ab+ba.

Express \Psi  as a polynomial in c and d. This is possible! (But requires a proof.)

The cd-index of P are the coefficients of the c_d 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? 

This entry was posted in Combinatorics, Convex polytopes and tagged , , , , , . Bookmark the permalink.

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

  1. Pingback: Carnival of Mathematics « Rigorous Trivialities

  2. 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?

  3. Pingback: Why Planar Graphs are so Exceptional « Combinatorics and more

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

  5. Pingback: Beyond the g-conjecture – algebraic combinatorics of cellular spaces I | Combinatorics and more

  6. Pingback: [Học chụp ảnh] Bố cục trong nhiếp ảnh - Bài 3 | - Cameraphone

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s