The Polynomial Hirsch Conjecture: Discussion Thread, Continued

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.

polymath3

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 d and the number of facets n.

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?

About these ads
This entry was posted in Convex polytopes, Open discussion, Open problems and tagged , . Bookmark the permalink.

16 Responses to The Polynomial Hirsch Conjecture: Discussion Thread, Continued

  1. Pingback: Polymath3 update « Euclidean Ramsey Theory

  2. I have an idea for dealing with this problem. It may take a while for me to develop it since the reference I am basing it on went back to the library yesterday. The idea is that a proof using active facets may use the fact that active facets tend to cluster together. I naively picture a polytope splitting into two hemispheres one that consists of active facets the other that consists of active facets when the objective function is replaced by its negative. The proof would use this fact somehow to find paths on both hemispheres that connect thus having a low length. I realize that there would be facets on which the objective function might be constant again I picture them as possibly forming a band between the two hemispheres. Anyway that is what I am thinking about now.

  3. I have just managed to find the book I was thinking about online and I see there was a problem with the above. A facet is active with respect to a vertex it contains as well as a linear function. So I would need a defintion that does not depend on a specific vertex but only on a linear function and then try to use that to find a limit on graph diameter.

  4. Oinky says:

    I confess to being confused by vertex decomposibility. Is there an easy algorithm to decide if a pure simplicial complex is VD?

  5. Gil Kalai says:

    Dear Oinky

    There is an easy algorithm (but it is exponential in the number of vertices): To check if a complex K is vertex decomposible(VD) go over all its vertices v and check if the antistar of v is VD and the link of v is VD. (If this is true for some vertex then the complex is VD.) The antistar of a vertex v is the complex containing all faces not containing v and the link of v is the complex containing all faces containing v after we delete v from all of them.

  6. Oinky says:

    Dear Gil,

    Thanks. I think my confusion comes from a difference in definitions.

    Do you require that the link and the antistar of v remain pure simplicial complexes, as defined here:

    http://www.eg-models.de/models/Simplicial_Manifolds/2003.06.001/_preview.html

    In another paper, (http://arxiv.org/abs/math/0604018), Lutz defines VD as follows:

    A triangulated d-ball or d-sphere is vertex-decomposable if we can remove the star of a vertex v such that the remaining complex is a vertex-decomposable d-ball (with a single d-simplex being vertex-decomposable) and such that the link of v is a vertex-decomposable
    (d − 1)-ball or a vertex-decomposable (d − 1)-sphere, respectively.

    That doesn’t seem like an equivalent definition. For example, take a hexagon — (a 1-sphere). Number the vertices 1 to 6 counter clockwise. Now delete vertex 1 and vertex 4. The edges (2,3) and (5,6) remain. And clearly that’s not a ball or a sphere since it’s disconnected.

    But I would argue that a polygon is vertex VD with your definition.

    I apologize for my naivety.

    Thanks again.

  7. Gil Kalai says:

    Oinky, I was a bit careless in the definition.

    Yes, you have to demand that a VD complex is pure. Once you make this requirement it follows that the complex is shellable and hence homehomorphic to either a sphere or a ball.

    The two definitions you mentioned are equivalent: in the example of a hexagon deleting vertex 1 and vertex 4 will leave us with a pure but a non VD subcomplex (the union of two disjoint edges). There is no way to delete another vertex leaving the antistar pure. But the hexagon itself is VD: you have to delete the vertices in another order.

    (One way to think about vertex decomposibility is as a strong form of shellability: You can start the shelling by deleting all facets containing some vertex; and this property is hereditary; it applies to the shelling of the facets containing the vertex; and to the shelling of all facets not containng the vertex.)

    There is another similar notion called “non evasiveness”. A simplicial complex is non evasive if it is a single point or if it has a vertex v so that both the link of v and the antistar of v are “non evesive”.

    (Non-evasiveness is a strong form of “collapsibility” in a similar way that VD is related to “shellability. There also is a more general notion of “nonpure shellability” but I am not sure if the analogous notion to VD or non-evasiveness (which should be wider than both) was studied.)

  8. Oinky says:

    Dear Gil,
    Thank you very much. My confusion is gone.

  9. I’m also extremely interested in seeing whether weak vertex decomposability is preserved under dual Pachner moves. This feels very plausible to me, and the resulting bound of 2(n-d) would also perhaps be concordant with current lower bounds on spheres and unbounded polyhedra — thus removing the need to restrict our attention to polytopality-preserving moves.

    However, I still don’t think I understand the operations of vertex deletion or (in the dual setting) facet removal. I gather that facet removal as a dual operation to vertex deletion is distinct from projective facet removal, since in the latter operation objects are guaranteed to remain polytopal even as hyperplanes are removed.

    If v maps into facet F in the polar, the dual of antistar(v) is the set containing all faces not contained in the facet F. Is this correct? Thus, the dual of vertex deletion is removing all faces contained in some facet F.

    I presume the square is known to be weakly facet-decomposable. However, removing any F from the complex of a square S would entail removing an edge e={1,2} and some vertices {1} and {2} from complex(S). Doesn’t this result in the complex of an unbounded three-facet polyhedron, not in a 2-simplex?

  10. Oinky says:

    Just some musings I thought I’d share….

    It occurred to me that it might be easier to show that the d-step and Hirch conjectures are true in odd dimensions (if they are true), due to consequences of the Upper Bound Theorem for polytopes, which states that the number of facets in a d-dimensional polytope is O(n^floor(d/2)). Consider the number of faces in neighborly simplicial polytopes with 2d vertices:

    dimension number of faces
    6 112
    7 150

    8 660
    9 858

    10 4004
    11 5096

    12 24752
    13 31008

    Intuitively, in order to obtain a graph with a high diameter, one needs more verticies to work with. The the odd dimensions simply do not provide as “many” faces as the even dimensions for their duals to have high diameter.

    Odd dimensions also have an interesting bisteller flip that preserves the f-vector of the complex: the m-to-m flip where m=ceil(d/2). If one could show that the m-to-m flip preserves diameter and all neighborly simplicial polytopes in odd dimension are connected via a sequence of m-to-m flips, that would prove the d-step conjecture for a wide class of polytopes.

  11. I apologize for my naivety, but I must still admit to some continued confusion regarding vertex decomposability.

    Would someone be willing to provide a basic example of the vertex decomposition of a small simplicial polytope? (Or equivalently, the facet decomposition of a simple polytope?)

    With an eye to determining whether VD is preserved under Pachner moves, here is a related result by Lee applying this strategy to Hirsch: http://www.springerlink.com/content/w587g7r771p429l4/

  12. Gil Kalai says:

    Dear Oinky,

    (Belated) thanks for your comment. One interesting remark is that the graphs of d-polytopes with n facets that has maximum number of vertices, have all diameter less than n^6 (or so). This was my first (and, by far, the hardest) result regarding diameter of graphs of polytopes.

    Dear Anand,

    Consider the Octahedron. The star of a vertex looks like a cone over a rectangle and so is the antistar. So to vertex decompose the octahedron we need to see that a cone over a square is vertex decomposible (VD), and that a square itself is VD.

    In general, if K is a cone over L with apex v (i.e. the join of L with a new vertex v) then if L is VD so is K since the link and antistar of v in K are both isomorphic to L.

    We need to show that the square is VD. Consider a vertex of the square: the link of a vertex is a complex consisting of 2 points. The antistar of the vertex is a complex consisting of two edges. Again, the antistar is a cone over the link so it is enough to demonstrate that the link is VD.

    The link of a vertex for a complex consisting of 2 isolated points is the complex consisting of the empty set alone which is VD. The antistar is a single vertex (again a cone over the link) which is also VD.

  13. Pingback: Plans for polymath3 « Combinatorics and more

  14. realsamurai says:

    Forex abner grenselose muligheder, giver for at oge uendeligt hovedstaden til erhverve uafhangighed, frihed.
    Vores fri forex signal
    -en af mader at denne formalet. mere info pa smartfxsol.com
    New Launch soon! come on smartfxsol.com

  15. Pingback: Subexponential Lower Bound for Randomized Pivot Rules! | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s