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 
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.
Combinatorics and more 
Problem six looks interesting I think the lowest case in which this problem is open is four dimensions. I downloaded the chapter it looks interesting thank you for posting it. Ziegler’s website also looks interesting.
Pingback: Proposed Polymath3 « Euclidean Ramsey Theory
I hope you’ll forgive a comment made before I’ve properly understood the background material. For now I’m going to ignore the abstract framework and just think of polytopes as geometric objects. I want to ask a few questions of people who have thought much harder about the problem than I have. Apologies also if the answers to these questions are already contained in what you’ve written.
I know of two obvious ways of constructing large families polytopes. One is to take a bunch of points, on a sphere, say (though this is not essential at all), and take their convex hull. The other is the dual process, which is to take a few half spaces, defined, say, by means of tangent hyperplanes to a sphere, and intersect them. Is it known that producing random polytopes of this kind will not give an example?
A preliminary reaction would be that the dual process should be the process that has a chance if either does, since the number of facets is small and the number of vertices large. So what is known if you take about
tangent planes at random to the 
-sphere and intersect the corresponding half spaces?
Hmm, perhaps this fails badly and a random walk on the graph mixes rapidly. In fact, that seems quite plausible to me. Is it known?
I’m asking this because if the conjecture is true for generic polytopes, then that changes quite a bit how one thinks about it.
Also, what about ideas like randomizing the simplex algorithm as follows? Rotate the polytope randomly and then greedily choose edges to take you as steeply downwards as you can. If you get to the bottom vertex in polynomial time with high probability, then the distance to a random point is polynomial and you’re done. Now let’s call the efficiency of an edge the difference in height between its top vertex and its bottom vertex. If the edge is randomly rotated, then its efficiency should be around
times its length. So one might expect to be able to get to the bottom in a time that’s something like 
divided by the average length of an edge, which doesn’t sound too bad.
Presumably such thoughts have been investigated thoroughly. Where do the difficulties arise? What is known about the average edge length for various kinds of polytopes?
Dear Tim, these are indeed very good questions;
1) random polytopes
The relevant geometric model of random polytopes is indeed when you take random generic hyperplanes which lead to a simple polytope. (A d-dimensional polytope is simple if every vertex belongs to d facets, so the facets meet in a generic way. these polytopes have often much more vertices than facets and their graph is a d-regular graph.)
The question if a random polytope has a diameter which is polynomial in term of d and n was apparently only answered recently and is related to progress on the average case behavior of the simplex algorithm. There are several. The article by Kim and Santos refers to works by Vershynin, following works of Spielman Teng.
In these works the random model is even this mixture of worse case/average case model you take a small random perturbation of the facets of an arbitrary polytope. There were earlier works on other such mixtures: (E.g. a random cell in an arbitrary arrangement of hyperplanes.) Initially the results did not refer directly to the diameter but to the length of a certain monotone path from a vertex to the optimal vertex, and talking about the actual diameter was harder.
In any case it looks that under various geometric models of random polytopes or even mixtures of random perturbation of an arbitrary polytope or random mixture of arbitrary hyperplane arrangement the diameter of the graph is polynomial (even polynomial in d times polylogarithmic factor in n.) But I am not entirely sure what was proved.
2) Rapid mixing.
A rapid mixing on the graph of a random polytope will be an even stronger property than smaller diameter. It is plausible but not known.
(We cannot expect this property for all polytopes.)
3) Random-rotation-steepest-step simplex
There is overall the impression that if you do a simplex method too greedily you may face exponential worse case examples. I am not sure if this applies to your version. It is known that choosing the steepest edge is exponential in the worse case; I do not know if a random rotation can help. The difficulty in analyzing such a variant of the simplex algorithm is that you can analyze matter for one steps but then when you try to walk more than one step you are in truble.
4) Edge length
I do not know what can be said about edge length in polytopes. The Hirsch conjecture will say that there is always an edge wose length is at least 1/(n-d) of the diameter (in the metric sense) of the polytope. I am not aware of any result in this direction.
As I said there is an extensive knowledge about random polytope (but I am not sure myself about what can be proved for diameter of random polytopes. I dont think any of the other questions was studied thoroughly.
From the wikipedia article at
http://en.wikipedia.org/wiki/Simplex_algorithm
“In 1972, Klee and Minty[2] gave an example of a linear programming problem in which the polytope P is a distortion of an n-dimensional cube. They showed that the simplex method as formulated by Dantzig visits all 2n vertices before arriving at the optimal vertex. This shows that the worst-case complexity of the algorithm is exponential time. Since then it has been shown that for almost every deterministic rule there is a family of simplices on which it performs badly. It is an open question if there is a pivot rule with polynomial time, or even sub-exponential worst-case complexity.
Nevertheless, the simplex method is remarkably efficient in practice. It has been known since the 1970s that it has polynomial-time average-case complexity under various distributions. These results on “random” matrices still didn’t quite capture the desired intuition that the method works well on “typical” matrices. In 2001 Spielman and Teng introduced the notion of smoothed complexity to provide a more realistic analysis of the performance of algorithms.[3]”
So nobody has got the exponential case out but on average it works well.
I think a lot of people have tried to get rid of the exponential case out and nothing has worked.
My vague intuition, maybe informed subconsciously by Dvoretzky’s theorem, is that a “random” polytope will be very round in high dimensions. If one wants to guess how far a “worst case” polytope will be from a “typical case” polytope, then one natural(?) question is the following: given an abstract combinatorial polytope that one knows can be realized as a convex polytope (cut out by hyperplanes), does one know how “round” one can make it? By “how round” I mean, for instance: what is the smallest
so that the polytope has boundary contained between concentric spheres of radis 
and 
. One could further insist that one restricts to realizations in which every edge (or maybe just a definite proportion of the edges) have length bounded above and below by universal constants (depending on dimension, but with better constants for large dimension).
I guess I forgot to say one reason why it might be relevant to know that the polytope is “almost round”. One way to check that a path from one vertex is making progress towards a final vertex is to check that they are contained in facets whose normals are close in the sphere of normal directions. Just how close is close depends on knowing that the facets “turn” at a definite rate when one moves along an edge (in the “right” direction); knowing that the polytope is almost round, and has faces of definite size, gives one a lower bound on the rate of turning. (polynomial in the dimension and number of vertices?)
Dear Danny, the question of what restriction on the combinatorial type does the assumption of “being round” poses is very natural. I suspect that both “being round” and even more so “being random” poses severe restriction on the combinatorics. (Actually it is also interesting if a random perturbation of an arbitrary polytope is “round”.)
(There is another notion of “random” which is a random combinatorial type. It is much more elusive and probably very different from random in the metric sense.)
I do not know what happens if you insist that all edge length are bounded above and below by some universal constants. (Requiring this in addition to being round may impose some upper bound on the number of facets. So maybe the lower bounds for edge length should allow some dependence on n.) I dont remember seeing this condition before.
I looked at Vershynin’s paper “Beyond the Hirsch Conjecture …” http://www-personal.umich.edu/~romanv/papers/simplex.pdf
and I do not think it gives a polynomial upper bound for the diameter of random polytopes. (Although this and earlier results indicated that such bounds exist.) The paper gives an improved upper bound for the number of pivot step for the “shaddow” pivot rule, for random perturbations of arbitrary polytopes, which, in terms of the dependence on n are even better than the Hirsch bound.
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. If one of the hyperplanes has only 2n-2 or less other hyperplanes intersecting it then the graph of its intersection with the polytope has diameter n-1 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. I will continue this in the next post.
continued. 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. I don’t see what is wrong with this but if there is a mistake maybe it can be fixed. I know the 2d conjecture holds for below 6 so a more modest goal would be to try and use something like this to prove the case n=6.
Dear Kristal, just to fill the readers with some notions: The d-step conjecture asserts that the graph of every d-polytope with 2d facets has diameter at most d. Indeed the full Hirsch conjecture (for all values of d and n) can be reduced to this special case (for all velues of d). Certainly deciding the case d=6 will be interesting. Regarding your earlier comment there are known randomized variants of the simplex algorithm which requires supexponential number of steps
. (This is “subexponential” in the way mathematicians use the world but not in the way CS would use it.)
I am going to put this on the wiki. I think the idea still works but I need to change what I have done to deal with one thing. That is that there may be less then 2k-2 hyperplanes intersecting a hyperplane. I have to deal with this. I think that I can do this by modifying the argument.
I got the proof up on the wiki and I made the changes I wanted. It still appears to work.
Some remarks on previous comments:
Kristal: The only problematic part of your argument appears to be guaranteeing the existence of an edge from the (2d-2)-facet F to the destination vertex. Can you clarify why such an edge should always be present?
The remainder is not controversial; Koranne and I show in a paper that it is sufficient during induction to consider the case of Dantzig figures where at least two (2d-2)-ridge facets exist.
The 6d case was recently verified computationally, in a paper by Bremner and Schewe: http://arxiv.org/abs/0809.0915
Daniel:
As the number of facets goes to infinity, it becomes more and more likely that the combinatorial type of the polytope may be realized as a sphere with infinitesimal-length edges. I once played around with this approach. It seems likely you could use it to show that Hirsch is true in the limit (not currently known). I thought this kind of reasoning might yield a polynomial bound, if you were to bound the decrease in the maximum edge length as more and more facets show up.
A rigorous case by case analysis of the conditions under which a potential counterexample to d-step could exist (if at all it does exist) has been performed by Kulkarni and myself, paper is available on http://ieor.berkeley.edu/~anandk/pubs/d-step.pdf
We show that the search space for this counter example is extremely narrow, and with some additional work can be made to vanish completely, thus proving the d-step conjecture.
The method uses several results from our previous paper on “Combinatorial Polytope Enumeration” http://ieor.berkeley.edu/~anandk/pubs/polyenum.pdf
Both these papers are also available from the arxiv pre-print server, and especially the Case VII problem we identify can be a good starting point for further discussion on this forum.
Quick question: can the polynomial Hirsch conjecture (as opposed to the Hirsch conjecture itself) be reduced to a statement about polytopes with 2d (or Cd, or poly(d), or something non-trivial) facets?
Yes, it can. Klee and Walkup’s construction guarantees it.
A polynomial bound on (d,2d) polytopes will yield a polynomial bound on all polytopes. In particular, if diam(d,2d) is bounded above by N, then diam(k,d+k) is bounded above by N.
I’ve just released a draft paper (with Sandeep Koranne) proving that no counterexamples to the d-step conjecture can arise except under a very restrictive set of conditions. We almost prove the full d-step conjecture, leaving only one case unresolved:
Click to access d-step.pdf
The last open case could be a good starting point for polymath3, since any bounds in this special case would yield overall diameter bounds for polytopes.
The strategy is drawn from an earlier paper outlining a method for induction over polytopal graphs; section 6.1 of the following:
Click to access polyenum.pdf
This kind of attack on Hirsch has the advantage of being 1) relatively unexplored, 2) semi-geometric, and 3) closely tied to previously successful “local moves”-type proofs on polytopes. The approach also seems likely to be useful for Problem 7 above, proving edge expansion bounds on polytopes.
Indeed it is correct that if D(d,n) is the maximum diameter for a d-polytope with n facets then D(d,n) <= D(n-d, 2(n-d)).
. Somehow when n is linear in d there are some helpful reccurence relation, however when you go ahead with the reccursion the ratio between n and d deteriorates. The assertion of the Hirsch conjecture is knoen (and easy) if every k-face has at most 2k facets. It is also not hard that there is a polynomial upper bound when for some constant T, for every k-face the number of its facets is at most Tk.
This applies (eaven more easily) to the various abstract versions. I tend to regard "the most difficult case" for the polynomial Hirsch conjecture the case that n is larger than 2d, say
In the last thread there was interest in ‘local moves’ approaches to Hirsch. Sandeep Koranne and I are working on a paper using a method for induction over polytopal graphs:
Click to access d-step.pdf
We use it to prove that no counterexamples to the d-step conjecture can arise except under a very restrictive set of conditions, almost (but not quite) yielding the d-step conjecture.
The last unresolved case from this paper would make a good alternative starting point for polymath3, if the abstract bounds do not work out. This method has the advantage of being 1) relatively unexplored, 2) somewhat geometric, and 3) closely tied to other successful “local moves”-type proofs on polytopes (g-theorem, Euler’s formula).
Many of the ideas come from an earlier paper on inductive generation of polytopes; see Section 6.1:
Click to access polyenum.pdf
The technique seems likely to me to also be useful in establishing edge expansion properties of polytopal graphs.
“Kristal: The only problematic part of your argument appears to be guaranteeing the existence of an edge from the (2d-2)-facet F to the destination vertex. Can you clarify why such an edge should always be present?
The remainder is not controversial; Koranne and I show in a paper that it is sufficient during induction to consider the case of Dantzig figures where at least two (2d-2)-ridge facets exist.”
The existence of an edge in this case might not be true. I want to look at it further and either fix it or find a counterexample and then see if I can work around it.
Sandeep Koranne and I have been working on a couple of papers which will be of interest to those interested in “local moves” types of approaches to Hirsch.
We outline a method for induction over polytopal graphs and use it to show that in most cases diameter is preserved during the inductive step for (d,2d) polytopes:
Click to access d-step.pdf
Handing the remaining case might be a good alternative to pursuing abstract diameter bounds. The method is relatively unexplored.
Apologies for the multiple identical posts… WordPress was not cooperating for some reason last night 🙂
Dear Anand and Sundeep,
Certainly trying to prove geometrically the d-step conjecture itself is something worth exploring. You are most welcome to contribute a post describing your approach and perhaps other developments (such as the d=6 case) and we can try to eplore this direction. Sorry for the wordpress difficulties.
I wonder if the following line of thought could be useful.
For the
-step conjecture, suppose it is sufficient to consider simple polytopes for which all facets are also simple polytopes. We suppose the conjecture holds for every polytope 
where 
.
Let
be a Dantzig figure with 
facets and dimension 
. Let 
, containing 
, be a projectively removable facets and $$ D'$$ be the polytope obtained by removing 
. Since 
is a simple polytope of dimension 
every vertex in 
has 
neigbor in 
and one outside 
. Let 
be the neighbor of 
outside 
, then 
is also a vertex in $$ D'$$ and by the induction hypothesis 
, so 
.
We use the property cited in the paper of Kulkarni and Koranne, that Dantzig figures are known to have maximal diameter over all
polytopes.
Is there any problem with this approach? Is it okay to only consider simple polytopes for which all facets are also simple polytopes?
I think in the d-step problem if the polytope is not simple then there will be one vertex with more than d facets passing through it and that vertex will have a facet in common with any other vertex and that can be used to solve the conjecture.
“Kristal: The only problematic part of your argument appears to be guaranteeing the existence of an edge from the (2d-2)-facet F to the destination vertex. Can you clarify why such an edge should always be present?
I am not sure it always is present. I think I found a counterexample to that. I think that a geometric proof of a polynomial bound via the d-step conjecture is feasible though.
Hi Mathieu,
When you projectively remove and reintroduce a facet, you need to guarantee that you are not damaging the path between x and w. So the reason the argument cannot stop here is that the inductive hypothesis does not necessarily apply once you have reintroduced the facet. This is why we go to such lengths in our second paper to show that this path is preserved.
I’ll post a description of the approach, as Gil suggested, and this should clarify the strategy better.
The high-level idea is this. Suppose we have a polytope whose diameter is known, and we perturb one of its hyperplanes very slightly until it makes a small change to the graph of the polytope. What effect does this have on the diameter? We showed that for most (d,2d) polytopes, the diameter cannot increase under this operation, and in many cases it will decrease. Moreover, this kind of construction is universal; any polytope may be obtained via a sequence of such perturbations from a polytope whose diameter is already known.
The way we obtain a polytope with known diameter is as follows: if you remove any one hyperplane of a polytope, then under an appropriate projective transformation (“projective removal”) you’ll obtain a polytope with one fewer facet whose diameter is known by induction. Then, when you gradually slide the hyperplane back into the polytope from some external point, you can recover the original shape. This method works on any combinatorial type of polytope.
We applied this approach to (d,2d) polytopes, in particular, Dantzig figures, whose diameter is defined by two vertices x and y each lying on d distinct hyperplanes (an “estranged pair”).
As we show in the first paper, when you remove a hyperplane from a Dantzig figure, you obtain a polytope whose diameter is at most diam(d-1,2d-2), because when n<2d on any polytope every pair of vertices lies on a common facet that is itself a (d-1,2d-2) polytope. Thus, you can assume by induction that we have a bound on the diameter of the starting shape.
As we slide the last hyperplane back into its original location, the combinatorial structure of the polytope only changes when the hyperplane passes through a vertex. When hyperplane cuts off the first vertex, the diameter of the Dantzig figure becomes at most diam(d-1,2d-2) + 1, since this operation induces a d-clique in the graph. As we translate the hyperplane further, we simply need to make sure that the diameter does not increase further, and we can moreover assume that one endpoint x can always lie on the hyperplane that is being moved. So much for the first paper.
Unfortunately, there are a lot of different ways that the hyperplane can conceivably interact with the shortest path between x and y. In our second paper, we classify all of them, and show that for all but one of them you can guarantee that the diameter is preserved somehow — sometimes you can find an alternate path, and sometimes you can prove that the case does not arise on Dantzig figures. There's only one situation that we weren't able to handle. It's geometrically quite specific and requires several conditions to occur simultaneously on the Dantzig figure. Indeed, it seems to us to be very difficult for this case to arise on low-dimensional polytopes. Thus, it is unsurprising that no counterexample to the d-step conjecture has yet been found, since when one first occurs it must arise in this particular specific way.
Aside from situations where this case appears, the diameter of Dantzig figures grows by at most 1 as dimension increases. This excludes all sorts of polytopes from serving as minimal counterexamples to the d-step conjecture: for instance, polytopes with any facet with a "small" number of vertices, or polytopes with a facet that's a prism over a simplex, or polytopes obtained by cutting away sets of vertices that have a small number of cycles, and so on.
Two possible strategies going forward with this approach would be 1) to try and obtain a bound on the number of times this last case occurs in polytopes, which immediately yields an upper bound on the diameter of a Dantzig figure, or 2) to try and build a counterexample using this specific set of conditions. Neither one seems too difficult to achieve. There are certainly also other ways to transition between polytopes using perturbations without removing a facet completely; it is possible that when looking at one of these, the last remaining case never arises.
I'm personally optimistic that some version of this approach will be able to resolve the d-step conjecture (either way), but my endorsement should be taken with a heavy grain of salt since it's part of my PhD dissertation.
Anand: Thank you for your response, I overlooked the very simple case where the path between x and w in D’ could contain vertices that are in D’ but not in D. In that case the path between x and w in D’ would not be a path in D.
Let me try to identify some directions from this thread.
1) The large edge conjecture:
Let P be a polytope in
whose metric diameter is 1. Does P has an edge of length at least 
where 
is polynomial in 
and 
? (or even 
?).
I do not know of any approach to this problem, but it looks of interest.
2) Random polytopes
As far as I can tell a polynomial upper bound on the diameter of random polytopes is not known. But there are related results that strongly suggest that this is the case. (And even suggest that the dependence on n is better than linear.)
Is theThe large edge conjecture holds for random polytopes or “smothened polytopes”!?This follows from known results. It still comes short of proving that the diameter of random polytopes is small.3) The Hirsch conjecture and d-step conjecture on the nose.
The original problems certainly have their appeal and most of the discussion was in this (welcome) direction. I will be happy to host further discussion in this direction.
If a the Hirsch conjecture does not have a polynomial bound then the d-step conjecture will also exceed any polynomial bound and the same will be true for the change in size between different directions. Since some of the facets will have less than 2n-1 intersections with other facets the only way this can happen is that the path to one of these facets must not have a polynomial bound. Also there must be some facets that are not this far they must have 2n-1 intersections with other facets and the increase in diameter by going from 2n-2 to 2n-1 must also be greater than any polynomial.
I think a lot of the attempts to get the result exactly on the nose can be changed to try to get a polynomial bound. Also perhaps different methods can be combined. I am still going through some of the papers and other material posted here and in past threads.
I think I can show there are at least 2 facets with 2n-1 ridges If we have two points which are opposite a diameter then each will have n lines and for at least one facet a line will touch it for each of these two and that gives two facets which must have 2n-1 ridges or else there will be a smaller dimensional counterexample. Now from “The D-step condition is almost true” we have
D must have at least 2 facets of 2n-2 ridges as well. So I think I have two facets of 2n-1 ridges and 2 of 2n-2 ridges.
I think I can improve the 2 facets of the last post to 4 that have 2n-1 ridges. If we have two points which are opposite a diameter then each will have n lines each line must intersect a facet not in the point but if all n intersect one facet then that facet will be a simplex and by the paper “The D-step condition is almost true” we have a facet can’t be a simplex so we have a contradiction and each set of lines must touch 2 facets which must have 2n-1 ridges giving 4 facets total that have 2n-1 ridges.
Regarding the direction of proving the d-step conjecture on the nose using Dantzig figures, there is an interesting paper by Lagarias and Prabhu
Click to access d-paths.pdf
One direction we can try to discuss is trying to understand expansion properties of polytopes. Graphs of d-polytopes with n facets which are
expanders, where 
is bounded above by a polynomial in d and n will have diameter bounded above by a polynomial in 
and $n$. The graph of the $lated d-cube$ has expansion constant 1.
However, such a mild expansion property does not hold for general graphs of polytopes since we can merge two large simple d-polytopes along a vertex of each.
If we have 4 facets with 2n-1 ridges and 2 with 2n-2 then I think we can prove the d-conjecture does not hold for three dimensions. The 4 facets with 2n-1 ridges must each have a ridge in common. They must have a ridge in common with every other facet. So picking any other facets we have 5 facets that have a ridge in common. Taking the dual of the graph we have the complete graph of five points which means the dual is not three dimensional because the graph of a three dimensional is planar. So if the dual is not three dimensional three original polytope is not three dimensional and we are done. Of course this already known but this shows that these methods can eliminate lower dimensional cases.
I downloaded the paper by Lagarias and Prabhu. I could read it but the pages seemed to be in reverse order.
“since some of the facets will have less than 2n-1 intersections with other facets the only way this can happen is that the path to one of these facets must not have a polynomial bound.” Because of this no lines or hyperplanes below a certain bound can touch the facet with less than 2n-1 intersections and because of this the hyperplanes in its skeleton remain unchanged if they are above a certain size. So this facet would be close to a simplex in its higher facets. There is a result in the chapter 19 that if the facets of size d-2 or less are the same the polytope is the same but here we are missing the lower facets. Still perhaps something could done with this using some of the other results.
“So this facet would be close to a simplex in its higher facets” And its dual would have the graph of a simplex.
Dear Kristal, I do not follow your claim and argument –Gil
If we don’t have a polynomial bound on diameter then eventually for any polynomial in eventually the increase in diameter for consecutive values will exceed this. Suppose we have two points separated by a path equal to the diameter a, b. There is a facet F with less than 2n-1 of the hyperplanes touching them these will have the old diameter say it intersects point a and and so must be separated by a long path from point b. If there is a line from the other point to the facet F then we have a short path to the facet and a contradiction. If we have a two dimensional hyperplane intersecting to a point on F then I thought that I could get a similar contradiction now that I look at this there is a gap here that I need to fill if possible. If we don’t have lines to points in F then there are no vertices formed in the interior of F, if there are no planes then there are no vertices formed in the facets of F. I thought this meant that the structure of these facets were unchanged and were that of a simplex there is another gap and this looks harder to fill than the previous one. Finally if I have the structure of the higher dimensional facets are that of simplex then I could take the dual which would have the graph of simplex and would (I think ) be simple and hence its graph would determine what it is and it would be a simplex and hence its dual would be a simplex and then perhaps we could use some of the results from “The D-step condition is almost true” I think that in that paper there is a condition that no facet can be a simplex. Anyway that was what I was trying to do but I am not sure the gaps can be filled especially the second and other things that I am not seeing may be wrong or incomplete as well.
Thanks! I can see what you are up to!, G./
A couple of simple question I have regarding the abstract setting: Consider an extension of the original problem where the vertices are labelled with multisets (or monomials) rather than with sets. Do the upper bounds continue to hold. (I tend to think they do). Is there a polynomial reduction between the multiset case and case of sets?
The second question is: does it help in the context of the Hirsch conjecture to assume that the labels are “multi colored” (or, in other words, completely balanced): there are d disjoint sets and all the d-subsets contain one element from each set.
Interesting discussion!
Gil: About your question re abstractions with multisets. The upper bounds continue to hold (you can carry over the proof essentially verbatim), and there is at least some kind of reduction between the two by a generalization of our construction. The relationship is
, where 
is the upper bound for the set case, and 
is the upper bound for the multi-set case, and 
is the size of disjoint covering families you can get.
The second inequality is the interesting one. A very rough sketch: You get it by replacing each of the n original elements by a set of m new elements. That is, starting from a (d,n) abstraction with multisets, you end up with a (d,nm) abstraction with sets whose diameter is larger by a factor of f(m). Each vertex in the original, multi-set abstraction becomes an entire block of vertices spanning f(m) layers.
I don’t know of a reduction that preserves the “type”, i.e. that does not change the parameter n.
Dear nh, this is interesting. One advantage for multisets is that if you define sets in terms of systems of linear equations it is somewhat easier to guarantee that, say, every m-set id scovered by a set in your system or other conditions of that kind.
I think I can fix one of my earlier attempts at a proof. In that proof I tried to prove the d-step conjecture using the fact that it is equivalent to the following case we have n dimensional space and two sets of hyperplanes intersecting in two points. What I couldn’t show that for every hyperplane through one point there is a line connecting it to the other point.
I think I can fix that now. label the points a and b. Let H be the facet of the cone formed by the hyperplanes through a formed by a hyperplane through a with dimension d-1, Let G be a facet of the cone of formed by hyperplanes through b of any dimension. If H intersects G then H also intersects a face of smaller dimension of the cone going through b. Specifically it must intersect one of G’s boundry planes in the cone generated by the hyperplanes of dimension d-1 passing through b. If it does not then the fact that the whole figure is convex means that additional hyperplanes will pass through b aside from those generated through the d-1 hyperplanes passing through it already mentioned.
To see this look at the polytope formed by the intersection of G and H near its edges it will lift out of G and that lift will be taken to vertex b by convexity. So it must touch one of the boundry planes and we repeat this with the lower dimension boundry planes until we get it must touch a line.
Then with the line the earlier proof works ie there must be a face with less than 2n-1 planes and by induction that has diameter n-1 and the line adds one to that giving n.
In regards to the above:
“To see this look at the polytope formed by the intersection of G and H near its edges it will lift out of G and that lift will be taken to vertex b by convexity. So it must touch one of the boundry planes and we repeat this with the lower dimension boundry planes until we get it must touch a line.”
I need to look at the case where the polytope doesn’t lift out it sinks in. It could be cutting G. So if this proof is to work more needs to be done.
I think there is a way around this. Look at the polytope formed by the intersection of G and H it is separate from point b and there is a plane separating b from the polytope either that plane will cut and it will block out part of G that will go all the way to point b or it will go outwards and add something to g that again will go to point b because of convexity.
I am going to write up what I have and put it on the wiki. I will post here when I have it up.
Dear Kristal,
I think what you’re trying to prove is false. From what I understand, you’re trying to prove the following: Let (P,x,y) be a Dantzig figure, and let F be an arbitrary facet of P. Suppose x is contained in F, then there is some vertex in F which is adjacent to y.
Consider the following three dimensional polytope P obtained as the intersection of two simplicial cones. The first simplicial cone Cx with apex x you can think of as one corner cone of a cube (it doesn’t really matter anyway). The second simplicial cone Cy with apex y is spanned by rays starting in y such that two of the rays intersect the *same* facet of Cx and the third ray intersects another facet of Cx. The rays must be spaced in such a way that the point x still lies in the cone Cy, but that is easily possible. Then the facet of P corresponding to the facet of Cx which was not hit by any of the rays does not have a vertex adjacent to y. Similarly, the facet of P corresponding to the facet of Cy which is spanned by the two rays hitting the same opposite facet contains no vertex adjacent to x.
Here are polymake inequalities defining such a polytope:
INEQUALITIES
0 16 -20 25
0 20 20 -25
0 -16 20 20
5 -1 0 0
5 0 -1 0
5 0 0 -1
Here are the vertex coordinates and vertex-facet incidences:
VERTICES
1 5 5 5
1 5/4 5 5
1 0 5 4
1 5 5/4 5
1 5 0 4
1 0 0 0
1 5 5 4/5
1 5 4 0
FACETS_THRU_VERTICES
{0 4 5}
{3 4 5}
{2 3 4}
{0 3 5}
{0 1 3}
{1 2 3}
{0 2 4}
{0 1 2}
I forgot to mention: The points x and y in the polymake example are the first (5 5 5) and sixth (0 0 0). The facet which does not neighbour x is facet 1, the facet which does not neighbour y is facet 5.
Thank you for the counterexample.
Let (P,x,y) be a Dantzig figure as I noted before from “The D-step condition is almost true” we have (P,x,y) must have at least 2 facets of 2n-2 ridges.
Without loss of generality let one of these F be adjacent to x it must form a ridge with each of the n-1 elements through x. then it must form ridges with n-1 elements through y. If there is line through y to F then by induction we have the theorem.
So the question is if a facet F in a Dantzig figure P(x,y) which is through x forms ridges with n-1 of the facets through y is there a line connecting it to y. Or if not then does forbidding it force another such facet.
I think that the above is true but I can’t prove it yet.
“So the question is if a facet F in a Dantzig figure P(x,y) which is through x forms ridges with n-1 of the facets through y is there a line connecting it to y. Or if not then does forbidding it force another such facet.”
I think this is true for three dimensions I am not sure for four or more.
Dear Kristal, nh and others, many thanks for your efforts in this interesting direction. I will try to think more about this direction and perhaps post on some other possible directions.
“So the question is if a facet F in a Dantzig figure P(x,y) which is through x forms ridges with n-1 of the facets through y is there a line connecting it to y. Or if not then does forbidding it force another such facet.”
Let me try to prove this for three dimensions. We have three possible cases
all three lines from y go through one facet, they each go through a different facet or two go through one facet and one goes through a different facet.
If all three go through a different facet then we are done.
If all three go through one facet then we have a geometric impossibility.
So this can’t occur and we are left with the final case:
Two lines from y go through one facet and one goes through another facet. then one facet through y will intersect one facet through x then
the other facets through x will have at most facets intersecting them and hence cannot have a line from y connecting it to y. But there is one other line from y unaccounted for it will connect y to one of the two remaining facets with at most 4 intersecting facets and we will be able to prove the theorem for dimension 3. So we will have to look for a counterexample in a higher dimension.
I think I can prove problem one finding a polynomial bound for diameter of graphs of polytopes in n and d. I will get a polynomial bound on (d,2d) polytopes which will apply to the more general case.
We will prove that between d-1 and d the increase in size of the diameter of (d,2d) is bounded by 2d. Then this will imply the bound of d^2 on (d,2d).
Let us start with a Dantzig figure P(x,y) in dimension d whose increase from the maximum bound in the previous dimension is greater than 2d-2. We have that d must be greater than 6 from previous results. There must be a facet which doesn’t touch all facets. If a line from x touches a facet through y then that facet must form ridges with all other facets otherwise we can use induction
and get the difference from the previous dimension is 1 which contradicts the induction hypothesis.
Let F be the facet that doesn’t touch all facets without loss of generality let it pass through x. From the above all lines through y must not pass through F but only though those facets that form ridges with all other facets. Now if a plane passes through F it will form a point with one of the boundary ridges of F it will be bounded by lines which form points in other facets of F there will be a path between these points and F it will be of length at most n since if all the face planes of the Dantzig figure intersect it each will form at most one side and thus the number of sides of the polygon formed is 2n. Its diameter will be n hence there will be a path of length n+1 from y to F and this will make the difference in diameters n+1 which contradicts the induction hypothesis.
So we only need to show that a plane passes through F if the above is true. I will continue this in the next post.
If no lines or planes pass through F then I claim that no higher dimensional hyperplane can. start with the three dimensional hyperplanes they are bounded by lines and planes intersection will form on intersection with the hyperplanes through y a set of planar regions bounded by lines formed by the planes intersecting the hyperplanes through y and lines formed by the hyperplanes through y each of these regions is convex and hence is formed by linear combinations of its boundary none of which pass through F. We can repeat this process for dimensions 4 and higher and eventually get that no ridge passes through F. But a ridge passes through F because there a facets which have ridges in common with all other facets. So we have a contradiction. So a plane must pass through F and we have our theorem.
Dear Kristal, I will try to go over your arument carefully tommorow. Certainly it is very exciting if it works.
There seem to be some difficulties in the purported proof, but I would welcome a clarification. Let me see if I can restate the argument succinctly to see if I understand the claim.
The general argument follows the thread so far: from papers and arguments posted upthread, in an inductive proof of the (polynomial) d-step conjecture it is sufficient to consider a Dantzig figure (P,x,y) that has a facet F with at most (2d-2) ridges. As usual for a Dantzig figure, assume x lies on F and y does not. We will find a path from x to y through F.
If F connects to y via an edge, by induction there is a path of length $\Delta(d-1,2d-2)+1$. Suppose it does not, as in the example given by nh.
The claim now is that there always exists (rather than an edge, as claimed before), a 2-face G of P connecting F to y. G satisfies the following properties:
1) G intersects F
2) G has at most 2d edges
3) G contains y
Did I state the claim correctly? Clearly, if such a G exists there will be a path from y to x of length at most $\Delta(d-1,2d-2)+d$, since the diameter of G is at most d. Such a result would mean the diameter increases by at most d as the dimension grows.
However, I’m not sure how Property 2 follows from the given proof. If G intersects every hyperplane of the Dantzig figure, as argued, it can have far more than 2d edges, since edges are formed at the intersection of every set of (d-1) facets, not every pair of facets as in two dimensions. This would seem to make the diameter of G arbitrarily bad. I would welcome a clarification if I have missed something.
If G is two dimensional then it is the intersection of d-2 facets so all of its edges are the intersection of these and another facet for a total of d-1 at most all of the 2d-(d-2) = d+2 remaining facets can be edges for a total of d+2 edges. The point is d-2 of the facets are fixed as their intersection forming G.
Thanks. Indeed, for any (d,2d)-polytope, any 2-face can have at most d+2 edges, rather than 2d as initially stated.
Provided Properties 1 and 3 do simultaneously hold, this would actually provide a diameter bound better than what is claimed.
Since the growth in diameter is at most
per inductive step, the bound would become
yielding an overall diameter bound (depending on the sign of d) of something smaller than
where the exact value depends on the sign and the greatest dimension below d for which the d-step conjecture is known to hold exactly.
Reposting to get the formula right:
Thanks. Indeed, for any (d,2d)-polytope, any 2-face can have at most d+2 edges, rather than 2d as initially stated.
Provided Properties 1 and 3 do simultaneously hold, this would actually provide a diameter bound better than what is claimed.
Since the growth in diameter is at most 1 + floor[d/2] per inductive step, the bound would become
Delta(d,2d) \leq Delta(d-1,2d-2) + 1 + floor[d/2]
yielding an overall diameter bound (depending on the sign of d) of something smaller than
Delta(d,2d) < (d^2)/4 + d
where the exact value depends on the sign and the greatest dimension below d for which the d-step conjecture is known to hold exactly.
I suppose the central proposed claim is: Let (P,x,y) be a Dantzig figure, and let F be an arbitrary facet of P. Suppose x is contained in F, then there is a 2-dimensional face G which contains both y and some vertex in F.
We can say that two vertices are k adjacent if there is a k-face that contains them both. So the claim is that y is 2-adjacent to a vertex of F.
I could not quite follow yet the proof of this claim.
The problem in the proof seems to be as follows.
The claim is that if the 2-dimensional face G does not exist, then there cannot exist any higher-dimensional face H containing both y and and some vertex z of F. H is chosen to be the facet that intersects all other facets, so H does contain z.
As I read it, the argument seems to be that since H is a convex combination of its lower-dimensional faces, if no lower-dimensional face contains both y and z, then H cannot contain both y and z. Absent additional reasoning, this conclusion would appear to be invalid. I would appreciate a correction if I have misunderstood the argument.
Moreover, it would still need to be shown that H must contain y (this part seems plausible and would be of independent interest, but is not proven).
I have looked at the proof again and part of it doesn’t seem to work.
I think if I had the result that there was a facet with 2n-2 ridges I might be able to repair it. I think in the“The D-step condition is almost true”
one of the results is that there must be a facet with 2n-2 ridges if I could get that here result perhaps I could fix the gap.
I will look at whether I can show H must contain y.
[Thanks a lot for the efforts Kristal. Don’t give up! G.]
I have been looking at Ziegler’s book on polytopes and in one exercise he mentions that it is possible for all pairs of different 2d planes to have ridges in common if the dimension is 4 or greater. So if that is true then there is a problem with all proofs based on a face with less than 2d-1 ridges here and also I think with part of the paper “The D-step condition is almost true” because it assumes from geometric reasons there is a facet with 2d-1 ridges. Ziegler mentions that this property makes it hard to attempt proofs based on induction.
This is correct: the property you are referring to is called neighbourliness. A simplicial d polytope can have the property that every k of its vertices form a simplex as long as k is at most [d/2] and for the dual simple polytope this means that every k facets have non emepty intersection. For a dual-to-neighbourly polytope with n facets every facet will have n-1 facets (ridges of the orifinal polytope) and every subfacet will have n-2 subsubfacets, etc.) The fact that we cannot contril the number of facets of a lower dimensional faces makes the problem harder.
I don’t think you should interpret what Ziegler wrote as an argument against induction in general. It just means that inductive strategies require a little more work beyond the obvious strategy.
What Ziegler observes in this exercise is that it is hard to attempt proofs based on -naive- induction over dimension; in other words, there is no guarantee that every facet of a Dantzig figure will be a (d-1,2d-2) polytope for which the diameter is already known. If it were, the diameter question would be quite easy 🙂
The strategy of projective removal presented in our paper was specifically intended to circumvent this problem; if you projectively remove any facet of a Dantzig figure that might violate the d-step conjecture, it is proved (not assumed) that the resulting shape will have a facet with at most 2d-2 ridges. This does indeed enable an inductive attack on diameter, and it doesn’t seem to be an approach people have tried before.
The inductive bound you get is
D(d,2d) \leq D(d-1,2d-2) + cost(projective removal).
The main challenge with this approach is that analysis of the effect of projective removal on the graph of a polytope is complex. But most of the inductive step is solved in the paper; the cost is usually 1 or 0.
It is also, separately, true that there must be a pair of facets on the original Dantzig figure D that have fewer than (2d-2) ridges, in addition to a facet that has (2d-1) ridges, as Ziegler observed. It’s easy to see why without reading the paper. However, this fact is unrelated to the inductive argument.
Hi Gil,
I was quite interested to learn from your earlier comment that a polynomial bound on the conductance of a polytopal graph would result in a polynomial diameter bound.
I would be very interested in discussing this direction further, since I think expansion could be easier to bound than diameter.
Could you say a few words about what is currently believed about expansion properties of polytopal graphs? How does the proof go that conductance bounds imply diameter bounds?
Dear Anand, Here is a bried response. It is a general property of graphs that good expansion implies small diameter. As a matter of fact, good expansion is equivalent to quick mixing of a random walk (if you start a random walk from any vertex you reach quickly a close-to-uniform distribution) snd quick mixing of a random walk implies that the diameter is small.
But, graphs of simple polytopes need not be good expanders. (And the problem of approximately reaching a random vertex according to the uniform distribution is probably computationally hard in general).
There is more to be said and discussed about expansion properties of graphs of polytopes. So for sure we can explore more this direction.
For d is greater than 4 the cyclic polytope has the complete graph so for n = 2d that will be the complete graph on 2d points. The dual of this graph will have 2d facets each one having a ridge in common with all of the other facets. thus in this case there are no smaller facets.
I think this is what Ziegler was referring to. for one thing he specified each facet must have a ridge in common with every other facet. Also this would make induction hard as each facet would not be a lower dimensional case of the theorem.
I think there is a proof that the duals of the cyclic polynomials satisfy the Hirsch conjecture so for this case to be a problem there would have to be another polytope in the same dimension with the same graph. I don’t know if that could happen. I know that there are polytopes in different dimensions that have the same graph.
It cannot happen that a d-regular graph corresponds to two different simple polytopes; by a theorem of Blind and Mani (later improved by Gil) a simple polytope is uniquely defined by its graph.
You’re right that the duals of cyclic polytopes are known to satisfy the Hirsch conjecture, so the example you suggest cannot be a counterexample. Thus there must be at least one facet with (2d-2) ridges or fewer in any potential counterexample. Even naive induction, without using any new techniques, is therefore still a conceivable (though in my opinion, difficult) route to a solution.
My own view is that direct induction using this facet will still be nontrivial, particularly since its existence was surely observed during early attempts at the problem. It seems difficult to establish a general relationship between F and y in a Dantzig figure. I’d conjecture (though I’d be very happy to be wrong!) that there are counterexamples for any k<d to the existence of a k-face connecting F and y.
Even if such a facet did not exist and direct induction were impossible, other kinds of inductive approaches could still be considered. For instance, projective induction works even for the dual of a cyclic polytope. Projectively removing any facet produces a new polytope where each facet has one fewer neighbor; each facet would thus be a (d-1,2d-2) polytope, which is a lower-dimensional case of the d-step conjecture. In my view, a nontraditional inductive strategy is less likely to have been already investigated.
There is a distinction between cyclic polytopes and neighorly polytopes. Cyclic d-polytopes have complete [d/2]-skeletons but there are many other polytopes with the same property (called “neighborly), and even more examples of polytopes which are only 2-neighborly: every two vertices form an edge. The Hirsh bound is known for dual-to-cyclic polytopes but not for dual to neighborly polytopes and certainly not for dual to 2-neighborly polytopes. So the examples Kristal suggested are considerably more general than duals to cyclic polytope. So I do not think it is true that there must be one facet with (2d-2) or less ridges in any counter example.
For dual to neighborly polytopes, I proved a polynomial upper bound on the diameter by showing that in this case the graphs have expansion property.
Thanks for the correction! I withdraw the statement; we can only require that a (2d-1)-ridge facet exists in a Dantzig figure.
Thus, it seems you have to use projective facet removal, or something similar, if you want to induct over the dimension.
Even in four dimensions there are neighborly but not cyclic that have eight vertices.
What is your maximal cost of projective removal? If you could get a polynomial bound on it then you would have a polynomial bound for the Hirsch conjecture as you could remove a facet pay the penalty and go the next dimensional case and repeat and the sum of the kth degree polynomials would be a polynomial of degree k+1.
Yes, what you’ve proposed was our initial goal.
In almost all cases the cost of projective removal is at most 1, but for one particular case we could not obtain any upper bound at all on the cost of projective removal. This case is extremely specific, however, which gives some hope that with some more thought a bound could be obtained for this case as well.
Obviously, some bound must apply here too, or else Gil’s subexponential bound wouldn’t be possible. If you look at the paper, it’s case 7, where a diameter-defining path doubles back through a high-dimensional face.
A silly thought:
Let P be a d-polytope and I the unit interval, and cut PxI with a hyperplane H. This can be made into a d+1 polytope Q in an obvious way, with each “level” corresponding to a local move in the sense of Kulkarni and Koranne. Any diameter bounds one gets for Q will induce diameter bounds for its top and bottom boundaries, one of which can be assumed to be P, and the other being P after some local moves have been performed. Q is quite a special polytope though… I wonder whether one can say anything about the diameter of a polytope which one can construct in this manner. I wonder also whether the above procedure can be iterated, and whether one can say anything about the limit.
The idea is cobordism.
Having some larger dimensional polytope records various local operation on P itself is certainly an interesting idea but do not understand the beginning. I can see that P x I is a d+1 dimensional polytope but then you intersect it with a hyperplane. Xan you elaborate a little?
Sorry- that was stated wrong. I meant to look at one of the two connected components of PxI minus the hyperplane H which intersects it. I think this keeps track of the Kulkarni-Koranne local moves, which involve (as I understand them) “moving” a hyperplane through a stationary polyhedron.
Maybe in fact a more general setting is necesary, such as taking H to be a “broken hyperplane” rather than a hyperplane. Also, can we usefully iterate the idea and move a hyperplane through the stationary connected compoenent of PxI-H (“moves between moves”) to improve the results of Kulkarni and Koranne?
In fact, maybe the most naive idea is best- to have a larger-dimension polytope which records the local moves, whose “vertical” arcs are from P x {0} to P x{I} except where the local move occurs, where the vertical arcs are determined by how the hyperplane moves (in the Kulkarni-Koranne setup).
I don’t know whether this is related, but Calegari’s idea looks quite nice and might combine with this idea- it certainly would make sense for high-dimensional polytopes to be “very round”, and proving a bound for sufficiently high dimension looks intuitively in some vague imprecise way like it really should be easier than lower dimensions.
If I understand correctly, one direction discussed here would be to give an inductive argument for upper bound on the diameter of graphs of polytopes using local moves; and such local moves may have a simple description by certain high dimensional polytopes containing our polytope P.
I do not understand well enough these local moves in the original description for the polytope P (or Dantzig figures) and for the higher dimensional polytopes. Are these local moves dual to “Pachner moves”? (a.k.a. bistaller operations)
There were over the years several thoughts to relate the diameter (or certain pivot rules for linear programming) of a polytope P with certain high dimensional polytopes. The simplest operation is forming a pyramid which leads to a polytope with diameter 2. I think there is a result of Carl Lee that you can move to a simple d+1 polytope Q by spiltting the apex of this pyramid so Q will have small diameter.
In the dual setting we talk about a simplicial d-polytope (or a triangulation K of a (d-1)-dimensional sphere) , and the problem about the diameter refers to the dual graph whose vertices are the facets and two facets are adjacent if their intersection id (d-2)-dimensional.
Also here one can ask if replacing K by a higher dimensional object – for example, a trangulation of the d-ball whose boundary is the given triangulation of the (d-1)-sphere – (perhaps at random) can lead to something interesting. But I do not know.
Random polytopes being very round is an interesting idea. I do not know how to relate it to the diameter of random polytopes. Polynomial upper bounds for diameter of random polytopes are also beyond reach at present.
The diameter defining path doubling back in case 7 reminds me of one of the equivalent forms of Hirsch conjecture which is that a diameter defining path never reenters a facet. I think that if the polynomial bound fails there will be not only multiple entries to a face but arbitrarily long sequences of entering and leaving faces will have to occur as there is only a polynomial number of such sequences and we have a super polynomial bound.
Pingback: Polymath on other blogs « The polymath blog
The local moves we proposed consist of translating a d-hyperplane of the polytope along its normal vector until the polytope’s combinatorial type changes.
This operation is directly related to bistellar flips; it looks like they are dual but perhaps someone who is more familiar with the flip can confirm.
This operation is indeed dual to the Pachner move! This allows a concise description of the results:
1) Any simple Dantzig figure may be obtained through a sequence of dual Pachner moves from one whose diameter is bounded by induction
2) The dual Pachner move is usually diameter-preserving for Dantzig figures, except in one special case
In fact, this suggests another way to continue this approach. Pachner moves switch between triangulations of a d-sphere, but (as I understand them) they do not always preserve a sphere’s realizabilty as a polytope. Since the d-step conjecture fails for d-spheres, dual Pachner moves must therefore occasionally increase diameter unless one imposes additional combinatorial conditions to preserve polytopality.
We didn’t use any such conditions, so perhaps this is why we couldn’t get a bound in the final case. But for all we know, it could only arise in non-polytopal spheres.
This suggests that in order to extend the method, we would want to find additional criteria that force Pachner moves (or dual Pachner moves) to remain polytopal, and use these criteria to restrict the last case. I only know a handful of necessary conditions, but was never able to show they are sufficient — are a full set of conditions known?
Dear Anand, is it easy to describe in the language of Pachner moves what is the one special case that causes trouble? There is a stronger property that implies the Hirsch conjecture (in the dual form – for triangulations of spheres): “vertex decomposability” (It is known not to hold for all polytopes). Does your inductive argument for all but one case applies to vertex decomposability and not just to the Hirsch bound?
Pachner’s well known result asserts that a simplicial sphere is PL iff it cab be obtained from the boundary of a simplex by a sequence of Pachner moves.
I will try to define the notions I refer to in a later post; meanwhile here is a link to a picture of Ewald, Kleinschmidt and Pachner. http://owpdb.mfo.de/detail?photo_id=1062
Dear Anand,
First, I think it would be useful to have a concrete example in hand of a polytope turning into something which is not a polytope via one of these moves- can we think of such an example?
I am not sure that restricting the set of dual Pachner moves would work- if we can’t use all (dual) Pachner moves, for me that suggests that Pachner moves are the wrong moves. The very loose analogy for me is http://front.math.ucdavis.edu/0509.5039 , where Habiro couldn’t use all Kirby moves and still stay in the category of integral homology spheres, so he found a new move in which two Kirby moves are combined, which keeps us inside that category (integral homology 3-spheres), and proved that these were sufficient. So my intuition would be that we perhaps need to translate 2 hyperplanes at once (if one takes us out of “polytopes”, the other takes us back in), generating a move which takes us from polytopes to polytopes…. or something vaguely like that- anyway, I think we need a natural set of moves which keeps us inside our category, and I’m a bit pessimistic about the prospects of any attempt to impose combinatorial conditions on which hyperplanes we are allowed to translate, or anything like that.
Then, I wonder whether these moves can be described in an abstract setting?
This general direction of attack looks beautiful and natural… I hope there is a way to make it work.
It is fairly easy to find an example of a simplicial 4-polytope transforming into a non-polytopal 3-sphere via a bistellar flip. (It’s actually easier to describe the inverse.) Take for example, the Bruckner sphere. Now apply any allowable 2-3 or 3-2 flip on this, and I believe you are guaranteed to have a polytope.
See Ewald, “Combinatorial convexity and algebraic geometry” p. 88.
I looked at Ewald, and found that nobody knows a set of necessary and sufficient conditions for a cell-decomposed sphere to be the boundary complex of a polytope (this is called the Steinitz problem).
Dear Daniel, right! There are very good reasons to believe that no such necessary and sufficient conditions can be found. (Deciding if a simplicial complex is the bounday complex of a simplicial polytope is decidable by a theorem of Tarski but otherwise, it looks mathematically and computationally hopeless.) There are various interesting necessary conditions.
Yes, deciding whether a simplicial complex is polytopal seems hopeless. But suppose you have a simplicial complex that you know is polytopal. Is there a way to determine if a particular bistellar flip on that complex will preserve polytopality? That almost seems possible.
For our purposes it wouldn’t be necessary to fully resolve the Steinitz problem, but simply to identify enough additional necessary conditions that we can exclude some situations where the diameter grows. As they stand, the moves do at least seem to restrict us to abstract polytopes, which are also conjectured to have small diameter.
Dear Gil,
I will need to read up a little further to give a description of the problematic case in terms of Pachner moves, but perhaps someone who’s more fluent in the language of flips can take a look at the figure in the paper and give it a try.
It would be very interesting and unexpected if the argument implied weak vertex decomposability (which gives a twice-Hirsch linear bound), but we looked at paths through the graph rather than shellability. If I understand the definition correctly, a simplicial complex is weakly VD iff we can delete a sequence of vertices (and their containing faces) and be left with a simplex. Thus, in the polar setting, a simple polytope is weakly VD if we can delete a sequence of facets (and all of their subfaces) and be left with a simplex. I don’t know whether this property is preserved under dual flips, but it certainly seems plausible and worth looking into.
There may be some superficial connection between weak VD and projective removal; a theorem of Klee and Kleinschmidt implies that projective removal of any n-(d+1) facets from any simple polytope will result in a simplex, which is almost the same as weak VD.
Dear Daniel,
Another way to construct an example of a polytopal->nonpolytopal move in the dual flip setting is by violating one of the known necessary conditions (see ‘Combinatorial Polytope Enumeration’, Thm 3.1). Label the vertices of a 3-cube as abcd on the top face and efgh on the bottom face. Now, consider a d-hypercube P and a translated hyperplane which progressively truncates vertices {a,b,c,g,h} from some 3-cube C contained in P. Since the hyperplane disconnects C and C is a convex subset of P, the resulting lattice is not polytopal. However, this example does not (apparently) increase diameter, nor is it a Dantzig figure.
Gil, are there known examples of simple polytopes that are not _weakly_ vertex decomposable as well?
I am curious why the Klee-Kleinschmidt result does not imply this property for all simple polytopes.
Something silly- translating a hyperplane does not realize an arbitrary dual Pachner move. It’s more a cut-the-cheese move (excuse the term)- you have a polytope which you can imagine as being a large cheese, and you cut off a slice. You can’t uncut an existing cheese. So these moves can’t be inverted. I don’t know how comfortable I am with that, but anyway…
Another candidate for a possibly natural move are the anti-prismatic subdivisions of Izmestiev and Joswig in http://arxiv.org/abs/math/0108202 (considered for totally different reasons). These are certain combinations of Pachner moves which I will sumarize later maybe. I have no clue whether performing one of these on a polytope yields another polytope or not.
Regarding problem 10: How about defining n-diameter as the minimal number N such that for any two points a and b on the n-skeleton of polytope P, the minimal number of n-faces through which a path from a to b must pass is less than or equal to N. There is a duality here, as the n-diameter of a polytope is the d-n – diameter of the dual complex…
An irrelevant correction to a previous post (nothing at all to do with the Hirsh conjecture): Habiro’s category is surgery presentations of integral homology 3-spheres by +-1 framed links with pairwise 0 linking number.
I’m not sure I agree — “uncutting” a cheese, as you describe it, corresponds to translating an existing hyperplane of a polytope out towards infinity. Isn’t this the inverse of the move described? It’s conceivable that the proposed moves are dual only to a subset of Pachner moves, but it’s not because they can’t be inverted.
I think we may have been a little sloppy in our language earlier. Translating a real hyperplane always yields another real polytope, obviously, since any set of real hyperplanes is necessarily realizable. We should be clear that we’re talking about a combinatorial generalization of a hyperplane translation applied to an arbitrary face lattice.
Regarding high dimensional analogs of “diameter”. Indeed one can look at the incidence graph between k-faces and r-faces and such notions played some role in studying the “ordinary” diameter. But this is not what I had in mind. Ordinary diameter can be regarded as a refinement of “connectivity” which is a condition on
and I wonder if there are similar conditions about higher homology. For example, given a k-gon in the graph of a simple d-polytope with n facets. Is it always the case that it is the boundary of a 2-chain involving at most a polynomial number of 2-faces in k d and n? Or, an equivalent condition to the Hirsch conjecture is that between every two vertices there are paths which do not revisit any facet, namely the intersection of the path with every facet is connected. (And while this is not known for all polytopes it is known for the dual graphs of a large class of simplicial complexes, those which are vertex-decomposable). Is there a similar statement that can be asked for 2-chains?
Dear Anand, I think I was misunderstanding your move- now I understand it. What I thought you were doing is to take another hyperplane H, and to replace polytope P with a connected component of
(slicing a piece off P). This is a Pachner move (or a combination of Pachner moves), but is not invertible…
Pachner moves are reversible.
I’m not sure where you’re going with this, but Francisco Santos is an expert in these operations, and he’s written a beautiful survey about the Hirsch conjecture. If he didn’t find a way to apply bisteller flips to the problem, then my hunch is that they’re probably not applicable. But I could be wrong.
Upon further reflection on the matter, I don’t see a way to constrain the choice of Pachner moves to preserving polytopality, without some underlying geometry upon which to base the choices.
Some comments: When we talk about Pachner’s moves we move to the dual desription of the problem. We want to walk between very two facets of a simplcicial d-polytope with n vertices (or just 2d vertices) in n-d steps where in every step we move from a facet to an adjacent facet. We can assume that the two facets are disjoint. Anand and Sundeep showed that when n=2d only one type of move does not allow an inductive argument to work.
The Hirsch conjecture is known to be violated for simplicial spheres (not by much though) so we will need to use the geometry and not just the combinatorics.
One question I was interested in was if in the cases where the inductive argument of Anand and Sundeep work one can prove also “vertex-decomposability”, a strong combinatorial property (must stronger than shelling) that implies the Hirsch bound.
Vertex decomposability asserts that there is a vertex whose link is vertex decomposible, and also so is his antistar (the complex of all faces disjoint to the vertex). Not every simplicial polytope is vertex decomposable.
(There is a weaker notion of “weak vertex decomposability” where you only require the condition inductively for the antistar (to the best of my memory); This suffices for twice the Hirsch bound and no examples of polytopes violating this weaker condition are known.)
One simple property that simplicial polytopes have and general simplicial spheres do not have is that when you delete a vertex and create a “hole” you can fill in this hole without a need for more vertices. (This property holds for a larger class of “matroidal spheres”. I do not know if a counter example to the Hirsch conjecture is known for matroidal spheres.)
By the way, many people tried to find an inductive proof of the g-conjecture using Pachner moves. Peter McMullen finally succeeded for the case of simplicial polytopes so his proof relied on the geometry. A proof for the general case is still missing but this is probably one of the promising direction for proving the g-conjecture (for PL-spheres).
I can take a stab at describing the problematic case in Pachner terms on a simplicial sphere, although it will be a little messier than in the dual setting.
We showed it is sufficient to consider a sequence of full-dimensional Pachner moves of type (k+1,d-k), where 1 \leq k \leq d-2. Recall that we seek to bound the length of a path between two disjoint facets X and Y.
For the unresolved case, consider a minimal X-Y path containing facets F1, F2, F3, and suppose that all three of these share a common vertex V with both X and each other. Suppose F2 is destroyed by a (k+1,d-k) move, and neither F1 nor F3 are deleted in this move. During the move, F2 is replaced by two facets F4 and F5, increasing the length of the path by 1.
For the first (d-1) moves where this situation arises (in a sequence of Pachner moves), we showed you can always find an alternate path that does not increase in length, so the diameter of the sphere is unchanged. But in subsequent moves, we were unable to prove why the diameter couldn’t continue to increase if this phenomenon continues to recur along the same path.
I suspect there is a combinatorial reason why this case must be bounded, since otherwise this growth would conflict with Gil’s existing bound for abstract polytopes. It seems likely there are also good geometric reasons this cannot continue to occur.
A handful of other conditions need to hold concurrently for the case to cause problems. For instance, you can show that the number of (2,d-1)-moves in any such sequence must be exactly (d-1).
Additionally, since we can choose different sequences of moves to reach a dual Dantzig figure, the described phenomenon must occur more than (d-1) times in every such sequence that could be used to produce a particular dual-Dantzig figure. This latter appears to be a very strong condition.
Dear Anand, I am not entirely sure what you mean by full dimensional Pachner mves of type (k+1,d-k); Certainly it will be very interesting for me to understand the way Pachner moves effect the diameter and related combinatorial properties.
This type of argument appears to give a path which gradually changes along the Pachner moves, so I am not sure if such local changes in the path (to the extent they are local) support the known upper bound for the diameter.
I suppose that the number of Pachner moves required to pass from a simplex to a given simplicial polytope with n facets can be huge; (This is certainly the case for PL-spheres.)
I agree, exploring the how Pachner moves can change the diameter is quite interesting.
The number of moves required to pass from a simplex to a given simplicial polytope is O(n^floor(d/2)). In fact, Pachner moves are used in many industrial Delaunay triangulation algorithms.
Click to access edels_shah.pdf
It’s also worth noting that given any two simplicial polytopes P1,P2, with n verticies, there exists a sequence of Pachner moves to transform P1 to P2 without using flips that insert a new vertex or delete a vertex. Each intermediate complex is also polytopal. This isn’t the case with PL-spheres.
I apologize if my notation is nonstandard; it varies between the
references I found. I’m following that given in the survey on flips by Santos.
As I used it, an (x,y)-Pachner move on a triangulated d-sphere is one which converts a set of x (d-1)-simplices into a set of y (d-1)-simplices. In the dual space, this corresponds to a dual-Pachner move that deletes x vertices and introduces y vertices.
A “full-dimensional” move is one where x+y = d+2, again following Santos.
Using this terminology, the specific sequence of moves we used for induction between a (2d-1)-vertex polytope of known diameter and a (2d)-vertex -polytope was a (1,d) move followed by a sequence of (k+1,d-k) moves, where k can be any integer from 1 to d-2.
I was actually unaware of the result about the existence of a non-vertex-deleting Pachner move sequence between arbitrary n-vertex simplicial polytopes, although this seems very natural. That’s great! There may be a slightly different sequence of moves than the ones we considered that would enable us to avoid the problematic case. There are also a number of Dantzig figures which are known to have exponential numbers of short paths (extremal polytopes, cubes) that one could try to move to or from.
Could you tell us more about the result, or suggest a reference?
Induction from a simplex to an arbitrary simplicial polytope does indeed require a large number of flips; for an n-vertex polytope it will require at least n (1,d) flips and an exponential number of (k,d-k) moves. Indeed, even translation between a pair of n-vertex simplicial polytopes requires an exponential number of Pachner moves in general.
Before your comment, Gil, I thought we were tracking how every vertex-disjoint shortest path was modified during the dual Pachner move (which would support the known bounds), but upon further thought it’s likely that we’re not considering some of them. This might be another direction to extend the analysis to avoid the problematic case.
I don’t have an exact reference for the non-inserting/non-deleting sequence of flips for polytopes. I remember someone telling me that result 15 or so years ago and I found it credible.
The closest thing I can find is:
Constrained paths in the flip-graph of regular triangulations
L. Pournin, Th.M. Liebling
I think their method could be extended to work with polytopes as well.
Do you have ways to generate the coordinates of these Danzig figures? It would be fun to flip them around to see if a counterexample could be found.
Dear Anand,
You wrote:
A handful of other conditions need to hold concurrently for the case to cause problems. For instance, you can show that the number of (2,d-1)-moves in any such sequence must be exactly (d-1).
Perhaps I’m crazy, but you are incrementally constructing neighborly polytopes, correct? if so, when would you ever execute a (2,d-1) move?
Oops. I was crazy. I think when constructing a neighborly polytope, you would only execute (2,d-1) flips.
Please ignore my last two posts. Thanks.
So, you’re in luck — Sandeep and I did implement our subset of the dual Pachner moves as a program some months back, and we also set up a counterexample search by constructing Dantzig figures from the simplex via dual moves. The search produces abstract polytopes, but there are a number of ways to check whether they are realizable as polytopes (for instance, an algorithm by Bokowski and Sturmfels).
Using the result on PL-spheres you suggested, this search process could be made even simpler. You wouldn’t need to build your way up from the simplex to get Dantzig figures; you could instead start with any single Dantzig figure, such as the d-cube, and apply the appropriate sequence of dual Pachner moves to obtain any other desired Dantzig figure.
The main challenge we faced with this strategy is that the number of Dantzig figures and (d,2d) polytopes is beyond enormous, and counterexamples to the Hirsch conjecture are likely to be well-hidden. Thus, undirected flipping produced no counterexamples; it’d be necessary to come up with a strategy for how to choose moves to generate an interesting object.
One idea would be to use the problematic case currently under discussion as a starting point for the move sequence; even if we don’t get a counterexample, we might find a new reason why paths are preserved in this case.
Another possibility is to take one of the Hirsch-violating nonpolytopal spheres and flip it around to try and recover a polytopal object. Even if the graph becomes Hirsch as it turns back into a polytope, it might do so in a generalizable way.
If there’s interest in experimenting, we can post the flip program online to play with.
Count me in!
Is it the case that the non-polytopal 3-spheres that violate Hirsch can be found here
http://infoshako.sk.tsukuba.ac.jp/~HACHI/math/library/index_eng.html
?
(Mani-Walkup C&D)?
If so, it’s interesting to note that these are not neighborly complexes. Perhaps they can be easily flipped into neighborly ones, giving more counterexamples.
I’d love to use your code.
Best.
Pingback: The Polynomial Hirsch Conjecture: Discussion Thread, Continued « Combinatorics and more
Pingback: Polymath again « What Is Research?
Pingback: Plans for polymath3 « Combinatorics and more
Pingback: Polymath Reflections « Combinatorics and more
What the world really needs is more love and less paper work.
google