The Polynomial Hirsch Conjecture: Discussion Thread

This post is devoted to the polymath-proposal about the polynomial Hirsch conjecture. My intention is to start here a discussion thread on the problem and related problems. (Perhaps identifying further interesting related problems and research directions.)

First, for general background: Here is a  chapter that I wrote about graphs, skeleta and paths of polytopes. Some papers on polytopes on Gunter Ziegler’s homepage  describe very interesting and possibly relevant current research in this area,  and also a few of the papers under “discrete geometry” (which follow the papers on polytopes) are relevant. Here are again links for the recent very short paper by  Freidrich Eisenbrand, Nicolai Hahnle, and Thomas Rothvoss, the 3-pages paper by Sasha Razborov,  and to Eddie Kim and Francisco Santos’s survey article on the Hirsch Conjecture.

Here are the basic problems and some related problems. When we talk about polytopes we usually mean simple polytopes. (Although looking at general polytopes may be of interest.)

Problem 1: Improve the known upper bounds for the diameter of graphs of polytopes, perhaps finding a polynomial upper bound in term of the dimension $d$ and number of facets $n$.

Strategy 1: Study the problem in the purely combinatorial settings proposed in the EHR paper.

Strategy 2: Explore other avenues.

Problem 2: Improve  the known lower bounds for the problem in the abstract setting.

Strategy 3: Use the argument for upper bounds as some sort of a role model for an example.

Strategy 4:Try to use recursively mesh constructions as those used by EHR.

Problem 3: What is the diameter of a polytopal digraph for a polytope with n facets in dimension d.

A polytopal digraph is obtained by orienting edges according to some generic linear objective function. This problem can be studied also in the abstract setting of shellability. (And even in the context of unique sink orientations.)

Problem 4: Find a (possibly randomized) pivot rule for the simplex algorithm which requires, in the worse case, small number of pivot steps.

A “pivot rule” refers to a rule to walk on the polytopal digraph where each step can be performed efficiently.

Problem 5: Study the diameter of graphs (digraphs) of specific classes of polytopes.

Problem 6: Study these problems in low dimensions.

Here are seven additional relevant problems.

Problem 7: What can be said about expansion properties of graphs of polytopes? Continue reading

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

How the g-Conjecture Came About

This post complements Eran Nevo’s first  post on the $g$-conjecture

1) Euler’s theorem

Euler

Euler’s famous formula $V-E+F=2$ for the numbers of vertices, edges and faces of a  polytope in space is the starting point of many mathematical stories. (Descartes came close to this formula a century earlier.) The formula for $d$-dimensional polytopes $P$ is

$f_0(P)-f_1(P)+f_2(P)+\dots+(-1)^{d-1}f_{d-1}(P)=1-(-1)^d.$

The first complete proof (in high dimensions) was provided by Poincare using algebraic topology. Earlier geometric proofs were based on “shellability” of polytopes which was only proved a century later. But there are elementary geometric proofs that avoid shellability.

2) The Dehn-Sommerville relations

Dehn

Consider a 3-dimensional simplicial polytope, – Continue reading

(Eran Nevo) The g-Conjecture I

This post is authored by Eran Nevo. (It is the first in a series of five posts.)

Peter McMullen

The g-conjecture

What are the possible face numbers of triangulations of spheres?

There is only one zero-dimensional sphere and it consists of 2 points.

The one-dimensional triangulations of spheres are simple cycles, having $n$ vertices and $n$ edges, where $n\geq 3$.

The 2-spheres with $n$ vertices have $3n-6$ edges and $2n-4$ triangles, and $n$ can be any integer $\geq 4$. This follows from Euler formula.

For higher-dimensional spheres the number of vertices doesn’t determine all the face numbers, and for spheres of dimension $\geq 5$ a characterization of the possible face numbers is only conjectured! This problem has interesting relations to other mathematical fields, as we shall see. Continue reading

Combinatorics, Mathematics, Academics, Polemics, …

1. About:

My name is Gil Kalai and I am a mathematician working mainly in the field of Combinatorics.  Within combinatorics, I work mainly on geometric combinatorics and the study of convex polytopes and related objects, and on the analysis of Boolean functions and related matters. I am a professor at the Institute of Mathematics at the Hebrew University of Jerusalem and also have a  long-term visiting position at the departments of Computer Science and Mathematics at Yale University, New Haven.

Gosset polytope- a hand drawing by Peter McMullen of the plane projection of the 8-dimensional 4-simplicial 4-simple Gosset polytope. Continue reading