An update on the Hirsch conjecture

Introduction

Let $n>d\geq 2$. Let $P$ be a $d$-dimensional polytope with $n$ facets. Then $\operatorname{diam}(G(P))\leq n-d$.

Consider the following examples; all of them satisfy the inequality strictly, except for the cube where it is tight:

Polytopes and polyhedra are the central objects in the area of geometric combinatorics, but they also appear in diverse mathematical fields: From the applications point of view, a polyhedron is the feasibility region of a linear program . This is the context in which the Hirsch conjecture was originally posed (see below). In toric geometry, to every (rational) polytope one associates a certain projective variety (see, e.g., ). The underlying interaction between combinatorics and algebraic geometry has proved extremely fruitful for both areas, leading for example to a complete characterization of the possible numbers of faces (vertices, edges, facets, …) that a simplicial polytope can have. The same question for arbitrary polytopes is open in dimension four and higher . Polytopes with special symmetries, such as regular ones and variations of them arise naturally from Coxeter groups and other algebraic structures . Last but not least, counting integer points in polytopes with integer vertex coordinates has applications ranging from number theory and representation theory to cryptography, integer programming, and statistics .

In this paper we review the current status of the Hirsch conjecture and related questions. Some proofs are included, and many more appear in an appendix which is available electronically . Results whose proof can be found in are marked with an asterisk. An earlier survey of this topic, addressed to a more specialized audience, was written by Klee and Kleinshmidt in 1987 .

We now review several concepts that will appear throughout this paper. For further discussion, we refer the interested reader to .

A polyhedron is the intersection of a finite number of closed half-spaces and a polytope is a bounded polyhedron. A polytope is, equivalently, the convex hull of a finite collection of points. Although the geometric objects are the same, from a computational point of view it makes a difference whether a certain polytope is represented as a convex hull or via linear inequalities: the size of one description cannot be bounded polynomially in the size of the other, if the dimension $d$ is not fixed. The dimension of a polytope is the dimension of its affine hull $\operatorname{aff}(P)$. A $d$-dimensional polytope is called a $d$-polytope.

If $H$ is a closed half-space containing $P$, then the intersection of $P$ with the boundary of $H$ is called a face of $P$. A non-empty face is the intersection of $P$ with a supporting hyperplane. Faces are themselves polyhedra of lower dimension. A face of dimension $i$ is called an $i$-face. The -faces are the vertices of $P$, the $1$-faces are edges, the $(d-2)$-faces are ridges, and the $(d-1)$-faces are called facets. In its irredundant description, a polytope is the convex hull of its vertices, and the intersection of its facet-defining half-spaces.

For a polytope $P$, we denote by $G(P)$ its graph or $1$-skeleton, consisting of the vertices and edges of $P$: the vertices of the graph $G(P)$ are indexed by the vertices of the polytope $P$, and two vertices in the graph $G(P)$ are connected by an edge exactly when their corresponding vertices in $P$ are contained in a $1$-face. The distance between two vertices in a graph is the minimum number of edges needed to go from one to the other, and the diameter of a graph is the maximum distance between its vertices. Let $H(n,d)$ denote the maximum diameter of graphs of $d$-polytopes with $n$ facets. (For an unbounded polyhedron, the graph contains only the bounded edges. The unbounded $1$-faces are called rays.)

Examples of polytopes one can build in every dimension are the following:

The $d$-cube. The vertices of the $d$-cube, the product of $d$ segments, are the $2^{d}$ points with $\pm 1$ coordinates. Its facets are given by the $2d$ inequalities $-1\leq x_{i}\leq 1$. Its graph has diameter $d$: the steps needed to go from a vertex to another equals the number of coordinates in which the two vertices differ.

Their numbers $m$ of vertices, $n$ of facets, dimension $d$ and diameter are:

Of special importance are the simple and simplicial polytopes. A $d$-polytope is called simple if every vertex is the intersection of exactly $d$ facets. Equivalently, a $d$-polytope is simple if every vertex in the graph $G(P)$ has degree exactly $d$. We note that the $d$-simplices and $d$-cubes are simple, but cross-polytopes are not simple starting in dimension three. Any polytope or polyhedron $P$, given by its facet-description, can be perturbed to a simple one $P^{\prime}$ by a generic and small change in the coefficients of its defining inequalities. This will make non-simple vertices “explode” and become clusters of new vertices, all of which will be simple. This process can not decrease the diameter of the graph, since we can recover the graph of $P$ from that of $P^{\prime}$ by collapsing certain edges. Hence, to study the Hirsch conjecture, one only needs to consider the simple polytopes:

The diameter of any polytope $P$ is bounded above by the diameter of some simple polytope $P^{\prime}$ with the same dimension and number of facets.

Graphs of simple polytopes are better behaved than graphs of arbitrary polytopes. Their main property in the context of the Hirsch conjecture is that if $u$ and $v$ are vertices joined by an edge in a simple polytope then there is a single facet containing $u$ and not $v$, and a single facet containing $v$ and not $u$. That is, at each step along the graph of $P$ we enter a single facet and leave another one.

Every polytope $P$ (containing the origin in its interior, which can always be assumed by a suitable translation) has a polar polytope $P^{*}$ whose vertices (respectively facets) correspond to the facets (respectively vertices) of $P$. More generally, every $(d-i)$-face of $P^{*}$ corresponds to a face of $P$ of dimension $i-1$, and the incidence relations are reversed.

The polars of simple polytopes are called simplicial, and their defining property is that every facet is a $(d-1)$-simplex. As an example, the $d$-dimensional cross polytope is the polar of the $d$-cube. Since cubes are simple polytopes, cross polytopes are simplicial. The polar of a simplex is a simplex, and simplices are the only polytopes of dimension greater than two which are at the same time simple and simplicial. Since all faces of a simplex are themselves simplices, all faces of a simplicial polytope are simplices. From this viewpoint, one can forget the geometry of $P^{*}$ and look only at the combinatorics of the simplicial complex formed by its faces, the boundary of $P$. Topologically, this simplicial complex is a sphere of dimension $d-1$.

For simplicial polytopes we can state the Hirsch conjecture as asking how many ridges do we need to cross in order to walk between two arbitrary facets, if we are only allowed to move from one facet to another via a ridge. This suggests defining the dual graph $G^{\Delta}(P)$ of a polytope: The undirected graph having as nodes the facets of $P$ and in which two nodes are connected by an edge if and only if their corresponding facets intersect in a ridge of $P$. In summary, $G^{\Delta}(P)=G(P^{*})$.

2 Relation to Linear Programming

Suppose the matrix $A$ has full row rank $m\leq n$. Then, the equality $A{\bf x}={\bf b}$ defines a $d$-dimensional affine subspace ($d=n-m$), whose intersection with the linear inequalities ${\bf x}\geq 0$ gives the feasibility polyhedron $P$:

One typically desires not only the maximum value of $c\cdot{\bf x}$ but also (the actual coordinates of) a vector ${\bf x}\in P$ where the maximum is attained. It is easy to prove that such an $x$, if it exists, can be found among the vertices of $P$. If $P$ is unbounded and $c\cdot{\bf x}$ does not have an upper bound on it one considers the problem “solved” by describing a ray of $P$ where the value $c\dot{\bf x}$ goes to infinity.

In 1979, Khachiyan proved that linear programming problems can be solved in polynomial time via the so-called ellipsoid method. In 1984, Karmarkar devised a different approach, the interior point method. Although the latter is more applicable (easier to implement, better complexity) than the former, still to this day the most commonly used method for linear programming is the simplex method devised by G. Dantzig in 1947. For a complete account of the complexity of linear programming, see the survey by Megiddo.

In geometric terms, the simplex method first finds an arbitrary vertex in the feasibility polyhedron $P$. Then, it moves from vertex to adjacent vertex in such a way that the value $c\cdot{\bf x}$ of the linear functional increases at every step. These steps are called pivots and the rule used to choose one specific adjacent vertex is called the pivot rule. When no pivot step can increase the functional, convexity implies that we have arrived to the global maximum.

Clearly, a lower bound for the performance of the simplex method under any pivot rule is the diameter of the polyhedron $P$. The converse is not true, since knowing that $P$ has a small graph diameter does not in principle tell us how to go from one vertex to another in a small number of steps. In particular, many of the results on diameters of polyhedra do not help for the simplex method.

In fact, the complexity of the simplex method depends on the local rule (known as a pivot rule) chosen to move from vertex to vertex. The a priori best pivot rule, the one originally proposed by Dantzig, is “move along the edge with maximum gradient”, but Klee and Minty showed in 1972 that this can lead to paths of exponential length, even in polytopes combinatorially equivalent to cubes. The same worst-case exponential behavior has been proved for essentially every deterministic rule devised so far, although there are subexponential, but yet not polynomial, randomized pivot algorithms (see Theorem 2.8). However, the simplex algorithm is highly efficient in practice on most linear optimization problems.

There is another reason why investigating the complexity of the simplex method is important, even if we already know polynomial time algorithms. The algorithms of Khachiyan and Karmarkar are polynomial in the bit length of the input; but it is of practical importance to know whether a polynomial algorithm for linear programming in the real number machine model of Blum, Cucker, Shub, and Smale exists. That is, is there an algorithm that uses a number of arithmetic operations that is polynomial on the number of coefficients of the linear program, rather than on their total bit-length; or, better yet, a strongly polynomial algorithm, i.e. one that is polynomial both in the arithmetic sense and the bit sense? These two related problems were included by Smale in his list of “mathematical problems for the next century” . A polynomial pivot rule for the simplex method would solve them in the affirmative.

In this context, the following polynomial version of the conjecture is relevant, if the linear one turns out to be false. See, for example, :

Is there a polynomial function $f(n,d)$ such that for any polytope (or polyhedron) $P$ of dimension $d$ with $n$ facets, $\operatorname{diam}(G(P))\leq f(n,d)$?.

3 Overview of this paper

Our initial purpose with this paper was two-fold: on the one hand, we thought it is about time to have in a single source an overview of the state of the art concerning the Hirsch conjecture and related issues, putting up to date the 20 year old survey by Klee and Kleinschmidt . On the other hand, since there seems to be agreement on the fact that the Hirsch conjecture is probably false (with opinions about the polynomial version of it being divided) we wanted to give a fresh look at the past attempts to disprove the conjecture.

These two goals turned out to be in conflict, or at least too ambitious, so the first version of the paper was too long and too technical for the intended readership. After wise comments from our editor Jörg Rambau and an anonymous referee, we decided to take most of the proofs out of the main paper, and compiled them in the companion paper . Results whose proof can be found in are marked with an asterisk.

Our two-fold intentions are still reflected in the two quite distinct parts that the paper has, Sections 2 and 3. The first one is devoted to positive results, comprising general upper bounds for polytope diameters, special cases where the Hirsch conjecture is known, etc, and the second one contains mainly constructions and results aimed at disproving the Hirsch conjecture.

The two sections differ in several other respects: Section 2 is written in an informative style. No proofs are included (although some appear in ) since this section covers quite different topics and the techniques and ideas used are too technical and, more importantly, too diverse. In Section 3, in the contrary, we provide proofs for essentially all the results (some here and some in ); on the one hand the tools needed are more homogeneous and elementary; on the other hand, in this section we feel that having a new look at old results is useful. We have tried to identify the basic ingredients in each construction, obtaining in some cases much simpler (to our taste) proofs and expositions than the original ones. In particular, the main novelty in this survey, if any, is probably in our descriptions of the non-Hirsch polyhedron and Hirsch-sharp polytope found by Klee and Walkup in 1967 (Section 3.3) and of the non-Hirsch sphere found by Mani and Walkup in 1980 (Section 3.6).

Another difference between the two sections is that Section 2 contains several very recent developments, while all of Section 3, with the single exception of Theorem 3.11, refers to results that are at least 25 years old.

Let us now give a brief roadmap for the paper.

Section 2.1 lists the pairs of parameters $(n,d)$ such that the Hirsch Conjecture is known to hold for all $d$-polytopes with $n$ facets. That is, denoting $H(n,d)$ the maximum diameter of $d$-polytopes with $n$ facets, we list all pairs for which the Hirsch inequality $H(n,d)\leq n-d$ is known to hold. This comprises the cases $d\leq 3$ (Klee ), $n-d\leq 6$ (Bremner and Schewe ), and $(n,d)\in\{(11,4),(12,4)\}$ (Bremner et al. ).

The next section lists general upper bounds on $H(n,d)$: a linear one in fixed dimension (Barnette and Larman) and a quasi-polynomial one of $n^{\log_{2}(d)+1}$ (Kalai-Kleitman ). These bounds hold not only for diameters of polytopes but also for much more abstract and general objects. A very recent development by Eisenbrand, Hähnle, Razborov and Rothvoß is the identification of one such class for which the proofs of these two bounds work but which admit objects with quadratic diameter. This may be considered evidence against the Hirsch conjecture.

In Section 2.3 we concentrate on algorithmic aspects. For example, we state two algorithmic analogues of the two bounds mentioned above: the proof by Meggido that linear programming can be done in linear time if the dimension is fixed, and randomized pivot rules for the simplex method in arbitrary dimension that finish in $O(\exp(K\sqrt{d\log n}))$ (Kalai , Matoušek, Sharir and Welzl ).

We then turn our attention to special polytopes for which good bounds are known. Polytopes with -$1$ coordinates and linear programming duals of transportation polytopes are known to satisfy the Hirsch conjecture (Naddef , Balinski ). Diameters of network-flow polytopes, which include transportation polytopes, have quadratic bounds .

Section 2 finishes with an account of recent work of Deza, Terlaky and Zinchenko on a continuous analogue of the Hirsch conjecture that arises in the context of interior point methods for linear programming.

Almost all of the results in Section 3 revolve around two basic ingredients. The first one is the wedge operation, which we describe in Section 3.1. Wedging is a very simple operation that increases both the dimension and number of facets of a polytope by one maintaining (or increasing) its diameter. Using it it is easy to prove the following fundamental result:

$H(d+k,d)\leq H(2k,k)$, with equality if (but not only if) $k<d$.

In particular, to prove (or disprove) the Hirsch conjecture one can concentrate in the case where the number of facets equals twice the dimension. This case is sometimes referred to as the $d$-step Conjecture, since the Hirsch conjecture is saying that we can go from any vertex to any other vertex in $d$-steps. Via wedging, the Hirsch conjecture is also equivalent to the following non-revisiting Conjecture: If $u$ and $v$ are two arbitrary vertices of a simple polytope $P$, then there is a path from $u$ to $v$ which at every step enters a facet of $P$ that was not visited before. We prove the equivalence of the three conjectures (Hirsch, $d$-step and non-revisiting) in Section 3.2.

The second ingredient is the construction by Klee and Walkup of a 4-dimensional polytope with 9 facets that meets the Hirsch bound with equality (that is, whose diameter equals $9-4=5$). Polytopes with this property are called Hirsch-sharp. They are easy to construct with a number of facets not exceeding twice their dimension (e.g., cubes). Klee and Walkup’s Hirsch-sharp polytope is the smallest “non-trivial” Hirsch-sharp polytope, with more facets than twice its dimension. In fact, it is also the starting block to the construction of every other Hirsch-sharp polytope with $n>2d$ known to date. In Section 3.3 we give our own description and coordinatization (much smaller than the original one) of the Klee-Walkup polytope.

In Section 3.4 we recount the state of the art on the existence of Hirsch-sharp polytopes, following work of Fritzsche, Holt and Klee . Their results, combined with what is known for small dimension or number of facets, are summarized in Table 1, which gives a “plot” of the function $H(n,d)-(n-d)$. The horizontal coordinate is $n-2d$, so that the column labelled “0” corresponds to the polytopes relevant to the $d$-step conjecture. The cases where we know $H(n,d)$ exactly are marked “$=$” or “$<$” depending on whether Hirsch-sharp polytopes exist or not. The cases where Hirsch-sharp polytopes are known to exist but for which the Hirsch conjecture is not proved are marked “$\geq$”. Cases where we neither know the Hirsch conjecture nor the existence of Hirsch-sharp polytopes are marked “?” and appear only in dimensions 4, 5 and 6. The diagonal dots in the left column reflect the equality case of Theorem 1.5.

The Klee-Walkup polytope is also instrumental in the construction by Klee, Walkup an Todd of counter-examples to two generalizations of the Hirsch conjecture that are quite natural in the context of linear programming: the case of perhaps-unbounded polyhedra (which was the original conjecture by Hirsch) and a monotone version in which we look at the maximum number of monotone steps with respect to a given linear function that are needed to go from any vertex of a polytope $P$ to an optimal vertex. We show these constructions in Section 3.5, and show in Section 3.6 a counter-example, by Mani and Walkup to a third, topological, version of the conjecture.

Bounds and algorithms

In this section, we present special cases for which the Hirsch conjecture holds, upper bounds for diameters of polytopes and subexponential complexity results for the simplex method. We also summarize recent work on analogues of the conjecture for hyperplane arrangements and for paths of interior point methods.

The following statements exhaust all pairs $(n,d)$ for which the maximum diameter $H(n,d)$ of $d$-polytopes with $n$ facets is known. We omit the cases $n<2d$, because $H(d+k,d)=H(2k,k)$ for all $k<d$ (see Theorem 1.5), and the trivial case $d\leq 2$. Remember that an asterisk in front of a statement denotes the proof can be found in .

Since $\max_{d}H(d+k,d)=H(2k,k)$ (see Theorem 1.5 again), the results for $H(8,4)$, $H(10,5)$ and $H(12,6)$ imply:

The Hirsch conjecture holds for polytopes with at most six facets more than their dimension.

It is easy to generalize one direction of Theorem 2.1, giving the following lower bound for $H(n,d)$. Observe that the formula gives the exact value of $H(n,d)$ for $d\in\{1,2,3\}$.

2 General upper bounds on diameters

Diameters of polytopes admit a linear upper bound when the dimension $d$ is fixed. This was first noticed by Barnette and then improved by Larman :

For every $n>d\geq 3$, $H(n,d)\leq n2^{d-3}$.

But when the number of facets is not much bigger than $d$, a much better upper bound was given by Kalai and Kleitman , with a surprisingly simple and elegant proof (the paper is just two pages!).

For every $n>d$, $H(n,d)\leq n^{\log_{2}(d)+1}$.

The proofs of Theorems 2.6 and 2.5 use very limited properties of graphs of polytopes. For example, Klee and Kleinschmidt (see §7.7 in ) show that Theorem 2.5 holds for the ridge-graphs of all pure simplicial complexes, and even more general objects. In the same vein, Eisenbrand, Hähnle, Razborov and Rothvoß have recently shown the following generalization of Theorems 2.6 and 2.5:

Let $G$ be a graph whose vertices are certain subsets of size $d$ of an $n$-element set. Assume that between every pair of vertices $u$ and $v$ in $G$ there is a path using only vertices that contain $u\cap v$.

Then, $\operatorname{diam}(G)\leq\min\{n^{1+\log d},n2^{d-1}\}$.

The novelty in is that the authors show that there are graphs with the hypotheses of Theorem 2.7 and with $\operatorname{diam}(G)\geq cn^{2}/\log n$, for arbitrarily large $n$ and a certain constant $c$. It is not clear whether this is support against the Hirsch conjecture or it simply indicates that the arguments in the proofs of Theorems 2.6 and 2.5 do not take advantage of properties that graphs of polytopes have and which prevent their diameters from growing. For example, observe that any connected graph is valid for the case $d=1$ of Theorem 2.7.

3 Subexponential simplex algorithms

Since the Hirsch conjecture is strongly motivated by the simplex algorithm of linear programming, it is natural to ask about the number of iterations needed under particular pivot rules. Most of the proofs for the upper bounds in the previous sections do not give a clue on how to find a short path towards the vertex maximizing a given functional, or even an explicit path between any pair of given vertices.

Kalai and, independently, Matoušek, Sharir and Welzl proved the existence of randomized pivot rules for the simplex method with subexponential running time for arbitrary linear programs.

There exist randomized simplex algorithms where the expected number of arithmetic operations needed in the worst case is at most $\exp(K\sqrt{d\log n})$, where $K$ is a fixed constant.

If we consider Theorem 2.8 as an algorithmic analogue of Theorem 2.6, then the following result of Megiddo is the analogue of Theorem 2.5. It says that linear programming can be performed in linear time in fixed dimension:

There are pivot rules for the simplex algorithm that run in $O(2^{2^{d}}n)$ time.

It is also known that random polytopes have polynomial diameter, which explains why the simplex method seems to work well in practice. The first results in this direction were proved by Borgwardt and, independently, Smale , who analyzed the “average case” complexity of the simplex method. Average case means that we are looking at a linear program

but the entries of $A$, $b$ and $c$ are considered random variables with respect to certain spherically symmetric probability distributions. In Borgwardt’s model the simplex method runs in expected polynomial time in the size of the input. Smale shows that in his model, if one of the parameters $d$ and $n-d$ is fixed and the other is allowed to grow, the expected running time is only polylogarithmic. The latter was improved to constant by Megiddo, see for details.

Even more surprising is the fact that every linear program can be slightly perturbed to one that can be solved in polynomial time. Let us formalize this. Let $P$ be the feasibility polyhedron

If a linear program is perturbed randomly within a parameter $\sigma$, then its expected diameter of its feasibility polyhedron is $O(log^{7}n(d^{9}+d^{3}\sigma^{-4})$.

As mentioned above, this result is not only structural. The simplex method can find a path of that expected length in the perturbed polyhedron.

4 Some polytopes from combinatorial optimization

There are some classes of polytopes of special interest and for the diameters of which we know polynomial upper bounds.

Of special importance in combinatorial optimization are the -$1$ polytopes, in which every vertex has coordinates or $1$.They satisfy the Hirsch conjecture.

As a generalization, Kleinschmidt and Onn prove the following bound on the diameter of lattice polytopes in $[0,k]^{d}$. A polytope is called a lattice polytope if every coordinate of every vertex is integral.

The diameter of a lattice polytope contained in $[0,k]^{d}$ cannot exceed $kd$.

However, existence of a polynomial pivot rule for the simplex method in -$1$ polytopes is open. The proof of Theorem 2.11 constructs a short path from $u$ to $v$ only assuming that we know the coordinates of both.

Network-flow polytopes

A network flow polytope is defined by an arbitrary directed graph $G=(V,E)$ with weights given to its vertices. Negative weights represent demands and positive weights represent supplies. A flow is an assignment of non-negative numbers to the edges so as to cancel all the demands and supplies. See , , and for details.

For any network $G$ with $e$ edges and $v$ vertices, every sufficiently generic set of vertex weights produces a simple $(e-v+1)$-dimensional polytope with at most $2e$ facets. Its diameter has the following almost quadratic upper bound. The proof yields a polynomial time pivot rule for the simplex method on these polytopes.

The diameter of the network flow polytope on a directed graph $G=(V,E)$ is $O(ev\log v)$. This, in turn, is $O(n^{2}\log n)$, where $n$ is the number of facets of the polytope.

The matrices defining network flow polytopes are examples of totally unimodular matrices, meaning that all its subdeterminants are , $1$, or $-1$. Polytopes defined by these matrices still have polynomially bounded diameters, although the degree in the bound is much worse than the one for network flow polytopes:

Transportation and dual transportation polytopes

As an example, the Birkhoff polytope, whose vertices are the permutation matrices, is the transportation polytope obtained with $p=q$ and $a=b=(1,\dots,1)$.

It is easy to show that (generically) $T_{p,q}(a,b)$ is a $(p-1)(q-1)$-dimensional polytope with at most $pq$ facets. Thus, the Hirsch conjecture translates to its diameter being at most $p+q-1$.

Transportation polytopes are a special case of network flow polytopes; they arise when the network is a complete bipartite graph on $p$ and $q$ nodes with all edges directed in the same direction. In particular, Theorem 2.13 gives an almost quadratic bound for their diameters. But Brightwell et al. have recently proved a linear bound, with a multiplicative factor of eight. This has now been improved to:

The diameter of any $p\times q$ transportation polytope is at most $3(p+q-1)$.

In the context of linear programming, for every $d$-polyhedron with $n$ facets there is a dual $(n-d)$-polyhedron with the same number of facets. Every linear program can be solved in its “primal” or “dual” polyhedron. The optimum achieved is the same in both, but the complexity of the algorithm may not.

The linear programming duals of $p\times q$ transportation polytopes are $(p+q-1)$-polyhedra with $pq$ facets, Balinski proved the Hirsch conjecture for them.

Let $C$ be a $p\times q$ matrix. The diameter of the dual transportation polytope $D_{p,q}(C)$ is at most $(p-1)(q-1)$. This bound is the best possible and it yields a polynomial time dual simplex algorithm.

-way transportation polytopes

Despite their definition being so close to that of transportation polytopes, 3-way transportation polytopes are universal in the following sense:

There is a $3$-way planar transportation polytope $Q$ isomorphic to $P$.

There is a $3$-way axial transportation polytope $Q$ which has a face $F$ isomorphic to $P$.

In both cases there is a polynomial time algorithm to construct $Q$ (and $F$).

Isomorphic here means affinely (and rationally) equivalent. In particular, that the polytope $Q$ or its face $F$ have the same edge-graph as $P$. Thus, it was interesting to try to apply to the 3-way case the methods that gave polynomial upper bounds for the graphs of transportation polytopes. This was attempted in , where a quadratic upper bound was obtained but only for axial transportation polytopes. A generalization of this result to faces of them or to planar transportation polytopes would prove the polynomial Hirsch conjecture.

The diameter of every $3$-way axial $p\times q\times r$ transportation polytope is at most $2(p+q+r-3)^{2}$.

5 A continuous Hirsch conjecture

Here we summarize some recent work of Deza, Terlaky and Zinchenko in which they propose continuous analogues of the Hirsch and $d$-step conjectures related to the central path method—a variant of interior point methods—of linear programming. For a complete description of the method we refer the reader to .) The analogy comes from analyzing the total curvature $\lambda_{c}(P)$ of the central path with respect to a certain cost function $c$ for the polyhedron $P$. By analogy with $H(n,d)$, let $\Lambda(n,d)$ denote the largest total curvature of the central path over all polytopes $P$ of dimension $d$ defined by $n$ inequalities and over all linear objective functions $c$.

It had been conjectured that $\lambda_{c}(P)$ is bounded by a constant for each dimension $d$, and that it grows at most linearly with varying $d$. Deza et al. have disproved both statements: in , they construct polytopes for which $\lambda_{c}(P)$ grows exponentially with $d$. More strongly, in they construct a family of polytopes that show that $\lambda_{c}$ cannot be bounded only in terms of $d$:

For every fixed dimension $d\geq 2$, $\liminf_{n\rightarrow\infty}\frac{\Lambda(n,d)}{n}\geq\pi$.

Deza et al. consider this result a continuous analogue of the existence of Hirsch-sharp polytopes. Motivated by this they pose the following conjecture:

$\Lambda(n,d)\in O(n)$. That is, there is a constant $K$ such that $\Lambda(n,d)\leq Kn$ for all $n$ and $d$.

Theorem 2.19 says that if the continuous Hirsch conjecture is true, then it is tight, modulo a constant factor. Deza et al. also conjecture a continuous variant of the $d$-step conjecture, and show it to be equivalent to the continuous Hirsch conjecture, thus providing an analogue of Theorem 3.2:

The function $\Lambda(2d,d)$ grows linearly in its input. That is to say, $\Lambda(2d,d)$ is $O(d)$.

The continuous Hirsch conjecture is equivalent to the continuous $d$-step conjecture. That is, if $\Lambda(2d,d)\in O(d)$ for all $d$, then $\Lambda(n,d)\in O(n)$ for all $d$ and $n$.

The best upper bound known for $\Lambda(n,d)$ is $O(n^{d})$, derived from Theorem 2.23 below. This theorem refers to the central path curvature for hyperplane arrangements, as studied by Dedieu, Malajovich and Shub .

$\lambda_{c}(\mathcal{A})\leq 2\pi d$, for every simple arrangement.

Put differently, even if individual cells can give total curvature linear in $n$ by Theorem 2.19, the average over all cells of a given arrangement is bounded by a function of $d$ alone.

Turning the analogy back to polytope graphs, Deza et al. consider the average diameter of the graphs of all bounded cells in a simple arrangement $\mathcal{A}$. Denote it $\operatorname{diam}(\mathcal{A})$ and let $\mathcal{H}(n,d)$ be the maximum of $\operatorname{diam}(\mathcal{A})$ over all simple arrangements defined by $n$ hyperplanes in dimension $d$. They relate $\mathcal{H}(n,d)$ to the Hirsch conjecture, as follows:

The Hirsch conjecture implies $\mathcal{H}(n,d)\leq d+\frac{2d}{n-1}$.

Constructions

We now move to interesting constructions of polytopes motivated or related to the Hirsch conjecture. All the proofs that are not included in this section, plus additional comments, can be found in .

Wedging is a very basic, yet extremely fruitful, operation that one can do to a polytope. Its simplicial counter-part is the one-point suspension, see .

Roughly speaking, the wedge of $P$ at a facet $F$ of it is the polytope, of one dimension more, obtained gluing two copies of $P$ along $F$. See Figure 2 for an example. More formally, let $f(x)\leq b$ be an inequality defining the facet $F$. The wedge of $P$ over $F$ is the polytope

the intersection $J\cap C$ is bounded and has nonempty interior, and

Let $P$ be a $d$-polytope with $n$ facets. Let $\operatorname{W}_{F}(P)$ be its wedge on a certain facet $F$. Then, $\operatorname{W}_{F}(P)$ has dimension $d+1$, $n+1$ facets, and

The diameter of $\operatorname{W}_{F}(P)$ is at least that of $P$, since every edge of $\operatorname{W}_{F}(P)$ projects either to an edge of $P$ or to a vertex of $P$. ∎

In particular, if $P$ is Hirsch-sharp then $\operatorname{W}_{F}(P)$ is either Hirsch-sharp or a counterexample to the Hirsch conjecture. The properties that $P$ would need for the latter to be the case will be made explicit in Remark 3.5.

As a corollary of Lemma 3.1 we get that in order to prove (or disprove) the Hirsch conjecture it is sufficient to restrict attention to the case when the number of facets equals twice the dimension:

$H(k+d,d)\leq H(2k,k)$, with equality if (but not necessarily only if) $k<d$.

Let $P$ be a polytope with $n<2d$ and let $u$ and $v$ be vertices of it. Since each vertex is incident to at least $d$ facets, $u$ and $v$ lie in a common facet. This facet $F$ has dimension $d-1$, and each facet of it is the intersection of $F$ with another facet of $P$. Hence, $F$ has at most $n-1$ facets itself. Since every path on $F$ is also a path on $P$, we get (2). ∎

2 The d𝑑d-step and non-revisiting conjectures

The intuition behind the Hirsch conjecture is that to go from vertex $u$ to vertex $v$ of a polytope $P$, one does not expect to have to enter and leave the same facet several times. This suggests the following conjecture:

Let $P$ be a simple polytope. Let $u$ and $v$ be two arbitrary vertices of $P$. Then, there is a path from $u$ to $v$ which at every step enters a facet of $P$ that was not visited before.

Paths with the conjectured property, that they do not revisit any facet, are called non-revisiting paths. (In the literature, they are also called $W_{v}$ paths and Conjecture 3.3 is also known as the $W_{v}$ conjecture.) Non-revisiting paths are never longer than $n-d$: at each step, we must enter a different facet, and the $d$ facets that the initial vertex lies in cannot be among them. Thus, the non-revisiting conjecture implies the Hirsch conjecture. It turns out both are equivalent. A first step in the proof is the following analogue of Theorem 3.2 for the non-revisiting conjecture:

If all $k$-polytopes with $2k$ facets has the non-revisiting property, then the same holds for all $d$-polytopes with $d+k$ facets, for all $d$.

Let $P$ be a polytope with $n\neq 2d$ and suppose it does not have the non-revisiting property. That is, there are vertices $u$ and $v$ such that every path from $u$ to $v$ revisits some facet that it previously abandons. We will construct another polytope $P^{\prime}$ without the non-revisiting property and with:

One less facet and dimension than $P$ if $n<2d$, and

One more facet and dimension than $P$ if $n>2d$.

In the first case, $u$ and $v$ lie in a common facet $F$ and we simply let $P^{\prime}=F$. In the second case, let $F$ be a facet not containing $u$ nor $v$ and let $P^{\prime}=\operatorname{W}_{F}(P)$ be the wedge over $F$. Let $F_{1}$ and $F_{2}$ be the two facets of $P^{\prime}$ whose intersection projects to $F$. Let $u_{1}$ and $v_{2}$ be the vertices of $P^{\prime}$ that project to $u$ and $v$ and lie, respectively, on $F_{1}$ and $F_{2}$ (see Figure 3). Now, consider a path from $u_{1}$ to $v_{2}$ on $P^{\prime}$ and project it to a path from $u$ to $v$ on $P$:

If the path on $P$ revisits a facet (call it $G$) other than $F$, then the path on $P^{\prime}$ revisits the facet that projects to $G$.

If the path on $P$ revisits $F$, then the path on $P^{\prime}$ revisits either $F_{1}$ or $F_{2}$.

In the proof of Lemma 3.1 we noted that, applied to a Hirsch-sharp polytope $P$ the wedge operator produced either another Hirsch-sharp polytope or a counterexample to the Hirsch conjecture. The last proof shows that the latter can happen only if $P$ does not have the non-revisiting property.

Theorems 3.2 and 3.4 say that both in the Hirsch and the non-revisiting conjectures the crucial case is that of $n=2d$. It is not surprising then that they are equivalent, since in this case they both almost restrict to the following:

Let $P$ be a simple $d$ polytope with $2d$ facets and let $u$ and $v$ be two complementary vertices (i.e., vertices not lying in a common facet). Then, there is a path of length $d$ from $u$ to $v$.

There is still something to be proved, though. If $u$ and $v$ are not complementary vertices in a $d$-polytope with $2d$ facets then the $d$-step conjecture does not directly imply the other two. But in this case $u$ ad $v$ lie in a common facet, so the proof of equivalence is not hard to finish via induction:

The Hirsch, non-revisiting, and $d$-step Conjectures 1.1, 3.3, and 3.6 are equivalent.

In their seminal 1967 paper on the Hirsch conjecture and related issues, Klee and Walkup describe a $4$-polytope $Q_{4}$ with nine facets and diameter five. Innocent as this might look, this first “non-trivial” Hirsch-sharp polytope is at the basis of the construction of every remaining Hirsch-sharp polytope known to date (see Section 3.4). It is also instrumental in disproving the unbounded and monotone variants of the Hirsch conjecture, which we will discuss in Section 3.5. Moreover, its existence is something of an accident: Altshuler, Bokowski and Steinberg list all combinatorial types of simplicial spheres with nine vertices (there are $1296$, $1142$ of them polytopal); among them, the polar of $Q_{4}$ is the only one that is Hirsch-sharp.

Here we describe $Q_{4}$ in the polar view. That is, we will describe a simplicial $4$-polytope $Q_{4}^{*}$ with nine vertices and show that its ridge-diameter is five. The vertices of $Q_{4}^{*}$ are:

[The simple polytope $Q_{4}$ is obtained converting each vertex $v$ of $Q_{4}^{*}$ into an inequality $v\cdot{\bf x}\leq 1$. For example, the inequality corresponding to vertex $a$ above is $-3x_{1}+3x_{2}+x_{3}+2x_{4}\leq 1$].

The key property of this polytope is that:

Any path in $Q_{4}^{*}$ from the tetrahedron $abcd$ to the tetrahedron $efgh$ needs at least five steps.

To prove this, you may simply input these coordinates into any software able to compute the (dual) graph of a polytope. Our suggestion for this is polymake . But we believe that fully understanding this polytope can be the key to the construction of counter-examples to the Hirsch conjecture, so it is worth presenting a hybrid computer-human proof. It is worth mentioning that the coordinates we use for $Q_{4}^{*}$, much smaller than the original ones in , were obtained as a by-product of the description of $Q_{4}^{*}$ contained in this proof.

Paths through some intermediate tetrahedron containing the vertex $w$ necessarily have at least five steps: apart of the step that introduces $w$, four more are needed to introduce, one by one, the four vertices $e$, $f$, $g$ and $h$.

This means we can concentrate on the subcomplex $K$ of $\partial Q_{4}^{*}$ consisting of tetrahedra that do not use $w$. This subcomplex is called the anti-star of $w$ in $\partial Q_{4}^{*}$. We claim (without proof, here is where you need your computer) that this subcomplex consists of the $15$ tetrahedra in Figure 4.

Figure 4 shows adjacencies among tetrahedra; that is, it shows the dual graph of $K$. The two tetrahedra $abcd$ and $efgh$ that we want to join are in boldface and appear repeated in the figure, to better reflect symmetry. The proof finishes by noticing that there is no intermediate tetrahedron that can be reached in two steps from both $abcd$ and $efgh$. Hence, five steps are needed to go from one to the other. ∎

4 Many Hirsch-sharp polytopes?

Recall that we call a $d$-polytope (or polyhedron) with $n$ facets Hirsch-sharp if its diameter is exactly $n-d$, as happens with the Klee-Walkup polytope of the previous section. Here we describe several ways to construct them.

Constructing Hirsch sharp $d$-polytopes with any number of facets not exceeding $2d$ is easy. For this reason we call such Hirsch-sharp polytopes trivial:

Product. If $P$ and $Q$ are Hirsch-sharp, then so is their Cartesian product $P\times Q$. Indeed, the dimension, number of facets, and diameters of $P\times Q$ are the sum of those of $P$ and $Q$. For the diameter, if we want to go from vertex $(u_{1},v_{1})$ to vertex $(u_{2},v_{2})$ we can do so by going from $(u_{1},v_{1})$ to $(u_{2},v_{1})$ along $P\times\{v_{1}\}$ and then to $(u_{2},v_{2})$ along $\{u_{2}\}\times Q$; there is no better way.

In particular, any product of simplices of any dimension is Hirsch-sharp. The dimension of $\Delta_{i_{1}}\times\cdots\times\Delta_{i_{k}}$, where $\Delta_{i}$ denotes the $i$-simplex, is $\sum_{j=1}^{k}i_{j}$, its number of facets is $\sum_{j=1}^{k}(i_{j}+1)$, and its diameter is $k$.

For every $d<n\leq 2d$ there are simple $d$-polytopes with $n$ facets and diameter $n-d$.

Let $k=n-d\leq d$ and let $i_{1},\dots,i_{k}$ be any partition of $d$ into $k$ positive integers (that is, $i_{1}+\cdots+i_{k}=d$). Let $P=\Delta_{i_{1}}\times\cdots\times\Delta_{i_{k}}$. ∎

Consider the polytope $P$ defined by the following $d+k$ inequalities:

where the $\psi_{i}$ are affine linear functionals that vanish at $v$ and are positive at $u$. No matter what choice we make for the $\psi_{j}$’s, as long as they are sufficiently generic to make $P$ simple, $P$ will have diameter (at least) $k$; to go from $v$ to $u$ we need to enter the $k$ facets $x_{j}=0$, $j=1,\dots,k$, and each step gets you into at most one of them. In principle, $P$ may be an unbounded polyhedron; but if one of the $\psi_{j}$’s is, say, $k-\sum x_{i}$, then it will be bounded.

Hirsch-sharp unbounded polyhedra with any number of facets are also easy to obtain:

For every $n\geq d$ there are simple $d$-polyhedra with $n$ facets and diameter $n-d$.

Non-trivial Hirsch-sharp polytopes

Hirsch-sharp $d$-polytopes with $n$ facets exist in at least the following cases: (1) $n\leq 3d-3$; and (2) $d\geq 7$.

Both parts are proved using the Klee-Walkup polytope $Q_{4}$ as a starting block, from which more complicated polytopes are obtained. In a sense, $Q_{4}$ is the only non-trivial Hirsch-sharp polytope we know of.

The case $n\leq 3d-3$ was first proved in 1998 , and follows from the iterated application of the next lemma to the Klee-Walkup polytope $Q_{4}$. Part 2 was proved in for $d\geq 8$ and was improved to $d\geq 7$ in . We sketch its proof in .

If there are Hirsch-sharp $d$-polytopes with $n>2d$ facets, then there are also Hirsch-sharp $(d+1)$-polytopes with $n+1$, $n+2$, and $n+3$ facets.

Let $u$ and $v$ be vertices at distance $n-d$ in a simple $d$-polytope with $n$-facets. Let $F$ be a facet not containing any of them, which exists since $n>2d$. When we wedge on $F$ we get two edges $u_{1}u_{2}$ and $v_{1}v_{2}$ with the properties that the distance from any $u_{i}$ to any $v_{i}$ is again (at least) $d$. We can then truncate one or both of $u_{1}$ and $v_{1}$ to obtain one or two more facets in a polytope that is still Hirsch-sharp. See Figure 5. ∎

Hirsch-sharp polytopes of dimensions two and three exist only when $n\leq 2d$ (see Section 2.1). Existence of Hirsch-sharp polytopes with many facets in dimensions four to six remains open. We do know that they do not exist in dimension four with 10, 11 or 12 facets (see Theorem 2.2), which may well indicate that $Q_{4}$ is the only Hirsch-sharp $4$-polytope.

5 The unbounded and monotone Hirsch conjectures

In the Hirsch conjecture as we have stated it, we only consider bounded polytopes. However, in the context of linear programming the feasible region may well not be bounded, so the conjecture is equally relevant for unbounded polyhedra. In fact, that is how W. Hirsch originally posed the question.

Moreover, for the simplex method in linear programming one follows monotone paths: starting at an initial vertex $u$ one does pivot steps (that is, one crosses edges) always increasing the value of the linear functional $\phi$ to be maximized, until one arrives at a vertex $v$ where no pivot step gives a greater value to $\phi$. Convexity then implies that $v$ is the global maximum for $\phi$ in the feasible region. This raises the question whether a monotone variant of the Hirsch conjecture holds: given two vertices $u$ and $v$ of a polyhedron $P$ and a linear functional that attains its maximum on $P$ at $v$, is there a $\phi$-monotone path of edges from $u$ to $v$ whose length is at most $n-d$?

Both the unbounded and monotone variants of the Hirsch conjecture fail, and both proofs use the Klee-Walkup Hirsch-sharp polytope $Q_{4}$ described in Section 3.3. In fact, knowing the mere existence of such a polytope is enough. The proofs do not use any property of $Q_{4}$ other than the fact that it is Hirsch-sharp, simple, and has $n>2d$. Simplicity is not a real restriction since it can always be obtained without decreasing the diameter (Lemma 1.3). The inequality $n>2d$, however, is essential.

We now turn to the monotone variant of the Hirsch conjecture:

There is a simple $4$-polytope $P$ with eight facets, two vertices $u$ and $v$ of it, and a linear functional $\phi$ such that:

$v$ is the only maximal vertex for $\phi$.

Any edge-path from $u$ to $v$ and monotone with respect to $\phi$ has length at least five.

In both the constructions of Theorems 3.14 and 3.16 one can glue several copies of the initial block $Q_{4}$ to one another, increasing the number of facets by four and the diameter by five, per $Q_{4}$ glued:

There are unbounded $4$-polyhedra with $4+4k$ facets and diameter $5k$, for every $k\geq 1$.

There are bounded $4$-polyhedra with $4+4k$ facets and vertices $u$ and $v$ of them with the property that any monotone path from $u$ to $v$ with respect to a certain linear functional $\phi$ maximized at $v$ has length at least $5k$.

This leaves the following open questions:

Improve these constructions so as to get the ratio “diameter versus facets” bigger than $5/4$. A ratio bigger than two for the unbounded case would probably yield counter-examples to the bounded Hirsch conjecture.

Ziegler [60, p. 87] poses the following strict monotone Hirsch conjecture: “for every linear functional $\phi$ on a $d$-polytope with $n$ facets there is a $\phi$-monotone path of length at most $n-d$ from the minimal to the maximal vertex”. Put differently, in the monotone Hirsch conjecture we add the requirement that not only $v$ but also $u$ has a supporting hyperplane where $\phi$ is constant.

6 The topological Hirsch conjecture is false

Another natural variant of the Hirsch conjecture is topological. Since (the boundary of) every simplicial $d$-polytope is a topological triangulation of the $(d-1)$-dimensional sphere, we can ask whether the simplicial version of the Hirsch conjecture, the one where we walk from simplex to simplex rather than from vertex to vertex, holds for arbitrary triangulations of spheres. The first counterexample to this statement was found by Walkup in 1979 (see ), and a simpler one was soon constructed by Walkup and Mani .

Both constructions are based on the equivalence of the Hirsch conjecture to the non-revisiting conjecture (Theorem 3.7). The proof of the equivalence is purely combinatorial, so it holds true for topological spheres. Walkup’s initial example is a $4$-sphere without the non-revisiting property, and Mani and Walkup’s is a $3$-sphere:

There is a triangulated 3-sphere with 16 vertices and without the non-revisiting property. Wedging on it eight times yields an $11$-sphere with $24$ vertices and with ridge-graph diameter at least $13$.

As in the monotone and bounded cases, several copies of the construction can be glued to one another. Doing so provides triangulations of the 11-sphere with $12+12k$ vertices and diameter at least $13k$, for any $k$.

Acknowledgments

This paper grew out of several conversations during the second author’s sabbatical leave at UC Davis in 2008 and the authors’ participation in the I-Math DocCourse on Discrete and Computational Geometry at the Centre de Recerca Matemàtica in 2009. We thank both institutions for hosting us and the financial support from the National Science Foundation and the Spanish Ministry of Science.

We also thank David Bremner, Jesús De Loera, Antoine Deza, Jörg Rambau, Günter M. Ziegler and the anonymous referee for their valuable comments on the first version of the paper.

References