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.)
Earlier posts are: The polynomial Hirsch conjecture, a proposal for Polymath 3 , The polynomial Hirsch conjecture, a proposal for Polymath 3 cont. , The polynomial Hirsch conjecture – how to improve the upper bounds .
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 and number of facets .
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?
Problem 8: What is the maximum length of a directed path in a graph of a d-polytope with n facets?
Problem 9: Study (and find further) continuous analogs of the Hirsch conjecture.
Problem 10: Find “high dimensional” analogs: for the diameter problem and for shellability.
(The diameter of a graph is a 1-dimensional notion; are there interesting high dimension analogs? Shellability is an abstraction of a 1-dimensional projection, are there interesting abstractions for projections to higher dimensions?)
Problem 11: Find conditions for rapid convergence of a random walk (or of other stochastic processes) on directed acyclic graphs.
Problem 12: Study these problems for random polytopes.
Problem 13: How many dual graphs of simplicial d-spheres with n facets are there?
The way I regard these open collaborative efforts is as an open collective attempt to discuss and have progress on these problems (and to raise more problems), also by helping people who think or work (or will think and will work) on these problems on their own.