The polynomial Hirsch conjecture

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

A possible proof

The Hirsch conjecture is equivalent to the d-step conjecture. The d-step conjecture is equivalent to the following case we have n dimensional space and two sets of hyperplanes intersecting in two points what is required is an n-step path between the two points.

Let us assume that we are at the lowest value for which the d-step conjecture holds.

If one of the hyperplanes has only 2n-2 other hyperplanes intersecting it then the graph of its intersection with the polytope has diameter n-1 by the inductive hypotheses and if we can get a edge connecting it with the other set of n points we are done but I think there is such an edge because the other n-1 hyperplanes in its bundle don’t block this hyperplane so the hyperplanes in the other bundle must do this and the result is that the hyperplane intersects the cone formed by the other set of hyperplanes in a n-1 dimensional polytope which includes vertices and each of those vertices is a line on the cone of the other hyperplanes.

The result is we get a line to the hyperplane which combined with the fact it has diameter n-1 gives us the d-step conjecture.

If all the hyperplanes intersects all the other hyperplanes then the polar of the polytope has the graph of a simplex in a higher dimensional space which since simple graphs have equivalent polytopes means that the dual is that simplex but the simplex is self dual so the polytope itself must be that simplex but that simplex has higher dimension which gives a contradiction and so the d step conjecture and hence Hirsch’s conjecture holds.

So the only case left is that only 2n-3 or less other hyperplanes intersect one hyperplane. The diameter of this graph must be greater than n-1 or as above we can get an edge connecting it with the other set of points and we are done. In this case we can take the intersection of this plane as a lower dimensional counterexample to the hirsch conjecture if the ratio of hyperplanes to dimensions is 2 to 1 we contradict the induction hypothesis and we are done. If not the ratio is less than 2 to 1 and we proceed as follows:

We take two points which are a diameter apart on the graph. Then since there are the ratio is less than 2 to 1 these points have a common plane and the diameter of the two points on that plane is greater than or the same as on the polytope. We take the intersection of the plane with the polytope as the new polytope then the dimension goes down by one as does the number of hyperplanes and we repeat with the new polytope eventually the ratio will go to 2 to 1 or the dimension will be three or less. In one case the inductive hypotheses is contradicted and we are done in the other case the the polytope must satisfy the Hirsch conjecture and again we are done.

Links

• The polynomial Hirsch conjecture, a proposal for Polymath 3 (July 17)
• The polynomial Hirsch conjecture, a proposal for Polymath 3 cont. (July 28)
• The polynomial Hirsch conjecture - how to improve the upper bounds (July 30)
• Wordpress posts on the Hirsch conjecture