Here is a link for the just-posted paper Diameter of Polyhedra: The Limits of Abstraction by Freidrich Eisenbrand, Nicolai Hahnle, Sasha Razborov, and Thomas Rothvoss.
And here is a link to the paper by Sandeep Koranne and Anand Kulkarni “The d-step Conjecture is Almost true” – most of the discussion so far was in this direction.
We had a long and interesting discussion regarding the Hirsch conjecture and I would like to continue the discussion here.
The way I regard the open collaborative efforts is as an open collective attempt to discuss and make progress on the problem (and to raise more problems), and also as a way to assist people who think or work (or will think or will work) on these problems on their own.
Most of the discussion in the previous thread was not about the various problems suggested there but rather was about trying to prove the Hirsch Conjecture precisely! In particular, the approach of Sandeep Koranne and Anand Kulkarni which attempts to prove the conjecture using “flips” (closely related to Pachner moves, or bistaller operations) was extensively discussed. Here is the link to another paper by Koranne and Kulkarni “Combinatorial Polytope Enumeration“. There is certainly more to be understood regarding flips, Pachner moves, the diameter, and related notions. For example, I was curious about for which Pachner moves “vertex decomposibility” (a strong form of shellability known to imply the Hirsch bound) is preserved. We also briefly discussed metric aspects of the Hirsch conjecture and random polytopes.
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. Here is a link to Eddie Kim and Francisco Santos’s survey article on the Hirsch Conjecture.
Here is a link from the open problem garden to the continuous analog of the Hirsch conjecture proposed by Antoine Deza, Tamas Terlaky, and Yuriy Zinchenko.
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 .
Here are again some basic problems around the Hirsch Conjecture. When we talk about polytopes we usually mean simple polytopes (although looking at general polytopes may be of interest).
Problem 0: Study various possible approaches for proving the Hirsch conjecture.
We mainly discussed this avenue, which is certainly the most tempting.
Problem 1: Improve the known upper bounds for the diameter of graphs of polytopes, perhaps even finding a polynomial upper bound in terms of the dimension and the number of facets .
Strategy 1: Study the problem in the purely combinatorial settings studied in the EHRR paper.
Strategy 2: Explore other avenues.
(Nicolai Hahnle remarked that the proof extends to families of monomials.)
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 like those used by EHRR.
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.
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.
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.
A polynomial upper bound for graphs of polytopes is not known also for random polytops.
Problem 13: How many dual graphs of simplicial d-spheres with n facets are there?