Counter-examples to the Hirsch conjecture
Introduction
The Hirsch conjecture stated that for any d-dimensional polytope defined by n inequalities, there would be a path of length no more than (n-d) edges between any two vertices of the polytope.
The Hirsch conjecture had some important implications on Linear Programming, as the length of the path gives a lower bound on the complexity of the simplex method. The conjecture has remained open for more than 50 years, and was finally disproven in 2010 by Paco Santos, who proved that there exists a 43-dimensional polytope defined by 86 inequalities, such that a particular pair of vertices could only be connected by paths of length at least 44.
In fact, Paco Santos solved the dual problem of finding a d-dimensional polytope of n vertices such that in the adjacency graph of the facets of the polytope, some two facets would not be connected by a path of length (n-d) or less. He proved that this can be attained by prismatoids, which are polytopes where two parallel facets (called bases) cover all vertices.
What Paco Santos proved is that if we find a d-dimensional prismatoid of n vertices (with n>2d), such that its width (the distance between the two parallel facets in the facet adjacency graph) is more than d, then we can modify it into another prismatoid, (d+1)-dimensional, with n+1 vertices, and a width of more than d+1. By doing this n-2d times, we get a prismatoid of dimension n-d, with 2n-2d vertices, and a width of more than n-d. The dual of this polytope is then a counter-example to the Hirsch conjecture.
Paco Santos also found a 5-dimensional polytope of 48 vertices with a width of 6, which leads to a 43-dimensional counter-example with 86 vertices, and a width of 47.
Low-dimensional counter-examples
Because the size of a counter-example is exponentially related to its dimension, it is important to find counter-examples in dimensions as low as possible.
The counter-example of Paco Santos was based on the very particular properties of a Minkowski sum of two 4-dimensional polytopes. When the two polytopes are placed on parallel planes, their convex hull is a 5-dimensional prismatoid of width 6 which can be used to build a counter-example. If the two polytopes (and so the prismatoid) have n vertices together, the counter-example has dimension n-5 and 2n-10 facets.
The original counter-example of Paco Santos was based on two polytopes of 24 vertices each, leading to a 43-dimensional counter-example. Since then, he found a simpler solution based on two polytopes of 14 vertices each, leading to a 23-dimensional counter-example. Starting from this simpler solution, I managed to find a sum leading to a in 20-dimensional counter-example. This is currently the lowest dimension for which a counter-example is known:
This is a poster I made for the IPAM workshop "Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?", presenting my discovery of a 20-dimensional counter-example to the Hirsch conjecture.
This is a Polymake file of the 25-vertices prismatoid which leads to my counter-example in 20 dimensions.
I have since managed to build the actual counter-examples, on which the Hirsch conjecture can be checked and disproven explicitly.
Computing and checking explicit counter-examples
As Paco Santos himself noted in his paper, the construction he first proposed gives a counter-example which would apparently have over a trillion vertices. The constructions presented in the previous page start from much smaller polytopes, and so they give counter-examples with much smaller number of vertices.
Even so, it was a priori unclear whether it was possible to compute the counter-examples themselves, as our estimates placed their number of vertices around a million. Thankfully, I found that this prediction was overly pessimistic, and that they could be computed, and even checked, in a reasonable amount time. I explain here the methods involved.
Recall that the counter-examples are built from a 5-dimensional prismatoid of width 6. If the prismatoid has n vertices, we execute n-10 times the following operation:
- Double a vertex in the base facet of the prismatoid, giving them coordinate +1/-1 in a new dimension
- Perturb vertices of the opposite facet in the new dimension
At every iteration, the dimension, the number of vertices and the width should augment by one. While the dimension and the number of vertices are automatically ensured, the perturbation needs to be done with some care in order to have the proper width. I devised a way to check the width after each step.
Checking the width is a simple task. From the vertices of the polytope, you find its facets, then compute the adjacency graph of the facets. It is then easy to use a shortest-path algorithm to find the distance in the graph between the two bases. However, the polytopes in my computations eventually had tens of thousands of facets, and so computing the facets, and especially the adjacency graph of facets, had to be done very efficiently.
The polytopes used throughout the construction are nearly-simplicial, in the sense that they have very few vertices (up to 46), but thousands of facets. The program lrs of David Avis is ideally suited for computing the facets of such polytopes. Even using rational arithmetic, the largest computation only takes about a minute.
I know of no way to compute the adjacency graph of facets except by brute force; i.e. testing for every pair of facets whether they are adjacent. The test can of course be done through linear programming, but with tens of thousands of facets, this is not practical in our situation. I started by computing for each facet the list of its incident vertices. I was able to also get this from lrs. For a d-dimensional polytope, the program lrs actually computes a triangulation of the boundary of a polytope, and outputs only once each facet it finds. It is however possible, using the options allbases and printcobasis, to have it output for every simplex of the triangulation the list of vertices of the simplex. It also indicates whether the simplex forms the whole facet it is part of. Since the polytopes are nearly-simplicial, most of the simplices are facets, and so we directly get the list of their incident vertices. For the small number of simplices that only form part of a facet, it does not take much time to compare the inequalities they define, and merge the list of vertices of simplices that define the same inequality. And so we get the list of facets and their incident vertices.
If a d-dimensional polytope is simplicial, every facet has d vertices, and two facets are adjacent if and only if they have d-1vertices in common. Since the polytopes involved in my computations have very few vertices (up to 48), we can encode the list of vertices of a facet in a 64-bits integer. Finding the list of vertices two facets have in common can then be done by a simple AND operation on the two corresponding integers. Counting the number of vertices in common is then done by counting the number of set bits in the result.
The question of doing this particular task efficiently has been studied thoroughly over the years, not least because it is very commonly asked in job interviews for Software Engineers. In our case, the integers tested are mostly very sparse, since two facets taken randomly have generally very few vertices in common; and choosing a method which runs in time linear of the number of set bits is the most efficient.
As our polytopes are not simplicial, but nearly-simplicial, it may happen that some non-adjacent facets have d-1 vertices in common. Since this corresponds to a lower-dimensional face, the corresponding list of common vertices is contained in the list of more than d-1 common vertices for a different pair of facets. I tested for such cases by storing the rare lists of more than d-1 common vertices and checking whether any other list was contained in them.
Using these methods, I was able to test after each iteration on the prismatoids that their width still exceeded their dimension. From the construction of Paco Santos, I was thus able to build a 23-dimensional prismatoid of 46 vertices and 73'224 facets, and to check that its width is 24. Thanks to the optimized adjacency tests, the 2.6 billions of pairs of facets were tested in 445 seconds. From my own solution, I built a 20-dimensional prismatoid of 40 vertices and 36'425 facets, and check that its width was 21. The 600 millions of pairs of facets were tested in 105 seconds. Computations were done on a MacBook Pro laptop with a 2.5Ghz processor.
Files
The following files describe the counter-examples. Note that they actually represent prismatoids that are dual of counter-examples to the Hirsch conjecture, as they have a width larger than n-d, where n is their number of vertices and d is their dimension.
Vertices of the 20-dimensional counter-example
Prismatoid of 40 vertices based on my construction.
Vertices of the 23-dimensional counter-example
Prismatoid of 46 vertices based on the construction of Paco Santos.
Facets of the 20-dimensional counter-example (2.2 Mb)
This is the output obtained by feeding the list of vertices of the polytope to lrs, with the options allbases and printcobasis. Each line describing an inequality is preceded by a line which lists the vertices incident to the facet (discounting the one indicated by an asterisk * which is an artifact from lrs). The uncompressed file takes 15 Mb.
Facets of 23-dimensional counter-example (3.3 Mb)
Idem for the 23-dimensional counter-example. The uncompressed file takes 22 Mb.
Adjacency of the 20-dimensional counter-example (1.6 Mb)
This file gives the adjacency list of each facet. For each facet, there is a line listing its incident vertices, then a line which gives the facet ID, the number of facets adjacent to it, then the list of IDs of adjacent facets. The uncompressed file takes 8 Mb.
Adjacency of the 23-dimensional counter-example (3.5 Mb)
Idem for the 23-dimensional example. The uncompressed file takes 18 Mb.