Monthly Archives: June 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. 

Helly’s Theorem, “Hypertrees”, and Strange Enumeration I

1. Helly’s theorem and Cayley’s formula

Helly’s theorem asserts: For a family of n convex sets in R^d, n > d, if every d+1 sets in the family have a point in common then all members in the family have a point in common.

Cayley’s formula asserts: The number of  trees on n labelled vertices is n ^{n-2}.

In this post (in two parts) we will see how an extension of Helly’s theorem has led to high dimensional analogs of Cayley’s theorem. 


left: Helly’s theorem demonstrated in the Stanford Encyclopedia of Philosophy (!), right: a tree 

2. Background

This post is based on my lecture at Marburg. The conference there was a celebration of new doctoral theses Continue reading

A Small Debt Regarding Turan’s Problem

Turan’s problem asks for the minimum number of triangles on n vertices so that every 4 vertices span a triangle. (Or equivalently, for the maximum number of triangles on n vertices without a “tetrahedron”, namely without having four triangles on four vertices.)  When we discussed Turan’s problem, we stated a lemma without giving the proof. Here is the proof.

Lemma: A three uniform hypergraph G on n vertices, so that every four vertices span a triangle satisfies:

\dim H_1(K,F) \le n-2.

Here, K is the simplicial complex on the n vertices which has all possible edges and, in addition, the triangles in G. F can be any field of coefficients, below we assume that F=Z/2. (But very little changes are required for the general case.)

Proof:  A little background: The space of 1-dimensional cycles of the complete graph with n vertices is of dimension {n-1} \choose {2}. Start with the star T where vertex ‘1’ is adjacent to all other vertices. every edge e={i,j} not in T, determines a cycle c(e) supported by the triangle {1,i} {1,j} and {i,j}. It is easy to see that all these cycles are linearly independent in the space of cycles of the complete graph and span this space.

Now to the proof itself. Let G be a hypergraph with the property that every 4 vertices span a triangle and let K be the 2-dimensional simplicial complex obtained by adding the triangles in G to the complete graph. H_1(K) is still spanned by the cycles c(e) for all edges e={i,j} 1<i<j \le n. Let H be a maximal set of edges e so that all the corresponding c(e) are linearly independent in H_1(K). It suffices to prove:

Claim: H is a forest.

Continue reading

What do Firms Want?

Here is another little sectionette from my book review  “Economics and Common Sense” on Steven Landsburg’s book “More sex is Safe Sex: The Unconventional Wisdom of Economics”, that just appeared on the AMS Notices site. Of course this topic can lead to a lovely discussion. Update (March 2011): Here is a related discussion on Noam Nisan’s blog in the context of research grants offered by Google.

What do firms want? Reading Landsburg’s book, one gets the impression that firms and their owners and executives just want to maximize their profits. They will avoid polluting the environment if and only if this is good for business. They will obey the law if and only if the cost/benefit tradeoff in violating the law are unfavorable.

It is not clear if this characterization of what firms want is just an assumption essential for developing the theory (which is reasonable), or an approximation of reality (which also sounds reasonable), or perhaps a solid precise description of reality (which as such sounds unreasonable), or maybe a normative teaching of economics theory (which sounds unfortunate), or perhaps even a representation of moral values (which also sounds unreasonable).

This description is simplistic even in the context of classical economic theory, Continue reading

Powers of Euler Products and Han’s Marked Hook Formula

Okounkov's homepage background

I heard from Dan Romik and Richard Stanley about a very exciting development in enumerative combinatorics. It is quite amazing how new uncharted sections of the gold mine of tableaux, hooks, partitions, and permutations are repeatedly being discovered. Guo-Niu HAN proved the following:

\sum f^2_{\lambda} \sum h^2= n! n(3n-1)/2.

Here, the first sum runs over all partitions \lambda of n, f_{\lambda} is the number of standard young tableaux corresponding to \lambda, and the second sum runs over all hook lengths of the Ferrers diagram corresponding to \lambda. Of course, this formula reminds us of the classical result \sum f^2_{\lambda} = n!, and of the hook formula for the value of f_{\lambda} itself. 

Han’s result is one of many exciting other applications of a recent remarkable formula for Euler’s product (1-x) (1-x^2) \cdots (1-x^k) \cdots raised to an arbitrary complex power z-1, via an expansion based on tableaux. This later formula was first discovered by Nekrasov and Okounkov in the context of Seiberg-Witten theory, and was later rediscovered by Han himself who provided another proof, and presented many remarkable applications. It also gives new proofs and new perspectives to several classical formulas regarding powers of Euler products going back to Euler himself, Jacobi, Ramanujan, and more recently, Macdonald, Kostant and many others.

Added July 11, long overdue: Dan showed me the actual general Nekrasov-Okounkov’s formula, hints regarding Han’s proof, and how the marked hook formula is derived. The general formula for powers of Euler products goes like this: \prod_{n=1}^{\infty}(1-x^n)^{\beta -1} = \sum _{n=0}^{\infty} (\sum _{\lambda \vdash n} \prod _{c \in \lambda} (1-\beta/h_c^2(\lambda ))x^n. The proof relies on a formula of Macdonald for the case that \beta=t^2 and t is an odd integer. Macdonald found a beautiful expansion in this case of the form  \sum _{(n_1,n_2,\dots,n_t)\in V_t}x^{(n_1^2+n_2^2+ \dots +n_t^2)/2- 1/24}, where  V_t referred to as “t-coding” meaning that the sum of all n_i's is 0 modulo t, and n_i \equiv i (\mod~ t). Anyway, once the “hook expansion” is derived using Macdonald’s formula for the spaciel case of squares of odd integers it extends automatically to all \beta's. The marked hook formula is derived by looking at the coefficients of x^n \beta^{n-1}.

Update (July 17 ): Dominique Foata brought to my attention a special web page on these developments.

Brush Up Your Björner:


Just returning from a conference in Stockholm.

(Cole Porter: Brush up your Shakespeare – new lyrics by Kimmo Eriksson)

The girls today in society
go for great mathematics, see.
So to win their hearts you must quote with ease
Pythagoras and Archimedes.
One must know Newton and Gauss and, hey,
what’s his name, eh? Poincaré!
Unless you know Grothendieck and DesCartes
no sweet lady will give you her heart.
But to really make them fall
and to make your love-life surrealist,
quote the greatest of them all:
a 60-year old comb’naturrealist.

Brush up your Björner,
start quoting him now!
Brush up your Björner,
and the ladies you will wow.

Many women will find it admirable
if you tell her she makes your CHIPS FIRABLE.
If your lady-friend still isn’t yielding
say you’ve got this big place: a TITS BUILDING.
If there still is some source of estrangement
make some cozier SUBSPACE ARRANGEMENT.
Brush up your Björner,
and they’ll all be charmed!

Continue reading