Monthly Archives: July 2009

The Polynomial Hirsch Conjecture – How to Improve the Upper Bounds.


I can see three main avenues toward making progress on the Polynomial Hirsch conjecture.

One direction is trying to improve the upper bounds, for example,  by looking at the current proof and trying to see if it is wasteful and if so where it can be pushed further.

Another direction is trying to improve the lower-bound constructions for the abstract setting, perhaps by trying to model an abstract construction on the ideas of the upper bound proof.

The third direction is to talk about entirely different avenues to the problem: new approaches for upper bounds, related problems, special classes of polytopes, expansion properties of graphs of polytopes, the relevance of shellability, can metric properties come to play, is the connection with toric varieties relevant, continuous analogs, and other things I cannot even imagine.

Reading the short  recent paper by  Freidrich Eisenbrand, Nicolai Hahnle, and Thomas Rothvoss will get you started both for the upper bounds and for the lower bounds.

I want to discuss here very briefly how the upper bounds could be improved. (Several people had ideas in this direction and it would be nice to discuss them as well as new ideas.) First, as an appetizer, the very basic argument described for polytopes. Here \Delta (d,n) is the maximum diameter of the graph of a d-dimensional polyhedron with n facets.



(Click on the picture to get it readable.)

The main observation here (and also in the abstract versions of the proof) is that

if we walk from a vertex v in all possible directions \Delta(d,k) steps we can reach vertices on at least k+1 facets.

But it stands to reason that we can do better.

Suppose that n is not too small (say n=d^2.). Suppose that we start from a vertex v and walk in all possible directions t steps for

t=\Delta (d,10d)+\Delta (d-1,10d)+\Delta(d-2,10d)+\dots +\Delta(2,10d).  (We can simply take the larget quantity t = d \Delta (d,11d).)

The main observation we just mentioned implies that with paths of this length starting with the vertex v we can reach vertices on 10d facets  and on every facet we reach we can reach vertices on 10d facets and in every facet of a facet we can reach vertices on 10d facets and so on. It seems that following all these paths we will be able to reach vertices on many many more than 10d facets. (Maybe a power greater than one of d or more.)  Unless, unless something very peculiar happens that perhaps we can analyze as well.

The Polynomial Hirsch Conjecture, a Proposal for Polymath3 (Cont.)

The Abstract Polynomial Hirsch Conjecture


A convex polytope P is the convex hull of a finite set of points in a real vector space. A polytope can be described as the intersection of a finite number of closed halfspaces. Polytopes have a facial structure: A (proper) face of a polytope P is the intersection of  P with a supporting hyperplane. (A hyperplane H is a supporting hyperplane of P if P is contained in a closed halfspace bounded by H, and the intersection of H and P is not empty.) We regard the empty face and the entire polytope as trivial faces. The extreme points of a polytope P are called its vertices. The one-dimensional faces of P are called edges. The edges are line intervals connecting a pair of vertices. The graph G(P) of a polytope P  is a graph whose vertices are the vertices of P and two vertices are adjacent in G(P) if there is an edge of P connecting them. The (d-1)-dimensional faces of a polytop are called facets.  

The Hirsch conjecture: The graph of a d-polytope with n  facets has diameter at most n-d.

A weaker conjecture which is also open is:

Polynomial Hirsch Conjecture: Let G be the graph of a d-polytope with n facets. Then the diameter of G is bounded above by a polynomial in d and n.

The avenue which I consider most promising (but I may be wrong) is to replace “graphs of polytopes” by a larger class of graphs. Most known upper bound on the diameter of graphs of polytopes apply in much larger generality. Recently, interesting lower bounds were discovered and we can wonder what they mean for the geometric problem.    

Here is the (most recent) abstract setting:

Consider the collection {\cal G}(d,n) of graphs G whose vertices are labeled by d-subsets of an n element set.

The only condition we will require is that if  v is a vertex labeled by S and u is a vertex labeled by the set T, then there is a path between u and v so that all labels of its vertices are sets containing S \cap T.

Abstract Polynomial Hirsch Conjecture (APHC): Let G \in {\cal G}(d,n)  then the diameter of G is bounded above by a polynomial in d and n.

Everything that is known about the APHC can be described in a few pages. It requires only rather elementary combinatorics; No knowledge about convex polytopes is needed.

A positive answer to APHC (and some friends of mine believe that n^2 is the right upper bound) will apply automatically to convex polytopes.

A negative answer to APHC will be (in my opinion) extremely interesting as well, Continue reading

How to Debate Beauty


 Who is the most beautiful queen of cards? Opinions vary.

 From Gina Says part 2

How to debate Beauty

[cosmic variance. Gina Says: May 10th, 2007 at 6:18 am ] The issue of beauty and physics is quite prominent in this discussion. Lee Smolin warns against adopting a physics theory based on aesthetic consideration and brings Kepler’s theory relating the five planets and five platonic solids (regular polytopes) as an example. Peter Woit makes (repeatedly, again and again and again) the claim that string theory is simply ugly, very ugly.

Well, beauty is a subjective matter. I remember my dear grand uncle Lena telling me:” Gina, aren’t we very lucky that people see things in a subjective way? If men were objective they would have all fallen in love with my own beloved wife (her name was incidentally also Gina,) who is clearly the most beautiful woman. This could have caused all sorts of complications.” Continue reading

Gina Says Part two

Download the second part of my book “Gina Says.”

Link to the post with the first part.



 “Gina Says,”

Adventures in the

Blogosphere String War

selected and edited by Gil Kalai


Praise for “Gina Says” 


After having coffee  at the n-category cafe,  Gina moved to  Clliford Johnson’s blog “Asymptotia” where she mainly discussed Lee Smolin’s book “The Trouble with Physics.”

Among the highlights:  Too good to be true (Ch 17); Dyscalculia and Chomskian linguistics (Ch 19); Baker’s fifteen objections to “The Trouble with Physics” (Ch. 25); Maldacena (Ch. 28);  High risks endeavors for the young (Ch 31);How to treat fantastic claims by great people (Ch. 33); Shocking revelations (Ch. 38); How to debate beauty (Ch 41.)

Some little chapters appeared also as posts: Continue reading

A Proof by Induction with a Difficulty


The time has come to prove that the number of edges in every finite tree is one less than the number of vertices (a tree is a connected graph with no cycle). The proof is by induction, but first you need a lemma.

Lemma: Every tree with at least two vertices has a leaf.

A leaf is a vertex with exactly one neighbor.

Well, you start from a vertex and move to a neighbor, and unless the neighbor is a leaf you can move from there to a different neighbor and go on. Since there are no cycles and the tree is finite you must reach a leaf. Of course you describe the argument in greater detail and it seems that everybody is happy.


Theorem: A tree T  with n vertices has n-1 edges.

After checking the basis for the induction we argue as follows: By the lemma T has a leaf v and once we delete v  and the edge containing it we are left with a graph T' on n-1 vertices. Now, T' has no cycles since T did not have any. It takes some effort to show that T' is connected. You describe it very carefully. Once this is done you know that T' is a tree as well and you can apply the induction hypothesis.

Student: Now what about the case where v is not a leaf? Continue reading

What can the Second Prize Possibly be?


You are guaranteed to win one of the following five prizes, the letter says. (And it is completely free! Just 6 dollars shipping and handling.)

a) a high-definition huge-screen TV,

b) a video camera,

c) a yacht,

d) a decorative ring, and

e) a car.

Oh yeah, you think, a worthless decorative ring, and throw the letter away.

But once I got a letter with the following promise:

You are guaranteed to win two of the following five prizes, the letter said. 

a) a high-definition huge-screen TV,

b) a video camera,

c) a yacht,

d) a decorative ring, and

e) a car.

Now, one prize will be a worthless decorative ring, but what will the second prize be?

The Polynomial Hirsch Conjecture: A proposal for Polymath3


This post is continued here. 

Eddie Kim and Francisco Santos have just uploaded a survey article on the Hirsch Conjecture.

The Hirsch conjecture: The graph of a d-polytope with n vertices  facets has diameter at most n-d.

We devoted several posts (the two most recent ones were part 6 and part  7) to the Hirsch conjecture and related combinatorial problems.

A weaker conjecture which is also open is:

Polynomial Diameter Conjecture: Let G be the graph of a d-polytope with n facets. Then the diameter of G is bounded above by a polynomial of d and n.

One remarkable result that I learned from the survey paper is in a recent paper by  Freidrich Eisenbrand, Nicolai Hahnle, and Thomas Rothvoss who proved that: 

Eisenbrand, Hahnle, and Rothvoss’s theorem: There is an abstract example of graphs for which the known upper bounds on the diameter of polytopes apply, where the actual diameter is n^{3/2}.

Update (July 20) An improved lower bound of \Omega(n^2/\log n) can be found in this 3-page note by Rasborov. A merged paper by Eisenbrand, Hahnle, Razborov, and Rothvoss is coming soon. The short paper of Eisenbrand,  Hahnle, and Rothvoss contains also short proofs in the most abstract setting of the known upper bounds for the diameter.

This is something I tried to prove (with no success) for a long time and it looks impressive. I will describe the abstract setting of Eisenbrand,  Hahnle, and Rothvoss (which is also new) below the dividing line.

I was playing with the idea of attempting a “polymath”-style  open collaboration (see here, here and here) aiming to have some progress for these conjectures. (The Hirsch conjecture and the polynomial diameter conjecture for graphs of polytopes as well as for more abstract settings.) Would you be interested in such an endeavor? If yes, add a comment here or email me privately. (Also let me know if you think this is a bad idea.) If there will be some interest, I propose to get matters started around mid-August. 

 Here is the abstract setting of Eisenbrand, Hahnle, and Rothvoss: Continue reading