1 Introduction

It is a long-standing open problem to determine the behavior of \(\Delta (d,n)\), the maximum possible diameter of a d-polyhedron with n facets. Warren M. Hirsch asked in 1957 whether \(\Delta (d,n) \le n-d\). This inequality is known to hold for \(d \le 3\) [15,16,17] and for small or structured polyhedra [2, 24], but not in general: A counterexample for unbounded polyhedra was eventually reported in [18]. Although open for about 50 years, a counterexample for bounded polyhedra, i.e. for polytopes, was reported in the seminal paper by [25]. For the history of the Hirsch conjecture, see [26, 31].

The current best lower bound on \(\Delta (d,n)\) is linear in d and n, and violates \(n-d\) only slightly [22, 25]. Meanwhile, the current best upper bound is subexponential, or quasi-polynomial, having the form of \((n-d)^{\log _2 \mathrm{O}(d)}\) [28,29,30] slightly improving upon [11, 13]. In view of these results, a major open problem on \(\Delta (d,n)\) is now the polynomial Hirsch conjecture: Is there any polynomial upper bound on \(\Delta (d,n)\)?

The polynomial Hirsch conjecture is also important from its close relationship to the complexity of the simplex method developed by Dantzig [4] for solving linear optimization problem. Specifically, one can construct an instance of linear optimization problem where the diameter of the feasible polyhedron serves as a lower bound on the number of pivots required by the simplex method. This means that if the polynomial Hirsch conjecture fails, then the simplex method cannot be a polynomial time algorithm. In this context, the polynomial Hirsch conjecture is also related to 9th Smale’s problem [27], i.e. the strongly polynomial time solvability of linear optimization problem.

1.1 Main Result

The aim of this paper is to show an improved upper bound on \(\Delta (d,n)\) towards the polynomial Hirsch conjecture although it is still far from being polynomial. More formally, we prove the following.

Theorem 1.1

\(\displaystyle \Delta (d,n) \le (n-d)^{\log _2 \mathrm{O}(d/{\log }_2 \,d )}\) for \(n \ge d \ge 2\).

The function form is motivated by that of the current best upper bound, i.e. \((n-d)^{\log _2 d}\) shown in [30].

Noting that \(a^{\log _2 b} = b^{\log _2 a}\) for \(a,b > 0\) in general, the new upper bound can be rewritten as

$$\begin{aligned} \mathrm{O}\biggl (\frac{d}{\log _2 d}\biggr )^{\log _2 (n-d)} = \mathrm{O}\biggl (\frac{1}{\log _2 d} \biggr )^{\log _2 (n-d)} (n-d )^{\log _2 d}. \end{aligned}$$

Hence, the new upper bound is \(\mathrm{O}(\log _2 d )^{\log _2 (n-d)}\) times smaller than Todd’s bound, which might be a considerable improvement. On the other hand, we should refer to a remark by Gil Kalai about the polynomial Hirsch conjecture in p. 513 of [12]:

Even upper bounds of the form \(\exp c \log d \log {(n-d)}\) and \(n2^{cd}\) for some \(c < 1\) would be a major progress.

By this definition, the new upper bound is not a major progress: To see this, let us rewrite the first upper bound mentioned above, and observe that for any \(c<1\), we have \(d^c < {\Theta }(d/{\log }_2\, d )\) for sufficiently large d.

We are not sure whether such a major progress can be derived by strengthening our approach or not, and want to leave it as future work.

1.2 Related Work

The key ingredient of our proof is a recursive inequality due to [13]. This Kalai–Kleitman inequality has already been utilized in showing upper bounds on \(\Delta (d,n)\); see e.g. [28,29,30]. In particular, it was shown in [28] that

  • \(\Delta (d,n) \le (n-d)^{\log _2 ( d/2 )} = (n-d)^{-1+\log _2 d}\) for \(d \ge 7\), and

  • \(\Delta (d,n) \le (n-d)^{\log _2 ( d/4 )} = (n-d)^{-2+\log _2 d}\) for \(d \ge 37\),

by a computer-assisted proof. Then, it would be natural to ask whether

$$\begin{aligned} \Delta (d,n) \le (n-d)^{\log _2 g(d)} \end{aligned}$$

holds for some function g(d) that is asymptotically smaller than d, which motivated this study. As we see from Theorem 1.1, the answer turned out to be yes. We note that our proof is not computer-assisted at all in contrast to [28]. For the differences from the previous proofs, see Sect. 3.3.1.

We also remark that for polytopes, the diameter is known to be at most \(2^{d-3}n\) as shown in [21]. This Larman’s bound is not subexponential but linear in n in fixed dimension. As mentioned in the Kalai’s remark, improving Larman’s bound is also a challenging task; see [9, 20] for more discussion on this topic.

On the other hand, parameters other than d and n have also been discussed so far with a view to understand the diameter of polyhedra:

Lattice polytope::

Assume that a polyhedron is given as the convex hull of points drawn from \(\{0,1,\ldots ,k\}^d\). Namely, d and k are the parameters in this setting. The first upper bound of kd was shown in [19] generalizing [24] for 0–1 polytopes. For improvements on upper and lower bounds, see [5,6,7].

Linear inequality system::

Assume that a polyhedron is given as \(\{ x : A x \le b \}\) with \(A \in \mathbb R^n\). In this setting, in addition to m and n, the largest absolute value \(\Delta _A\) of a sub-determinant of A has been studied as a common parameter. The current best upper bound is due to [1] strengthening [8]. Also, it is known that \(\Delta _A\) is useful in analyzing the complexity of the simplex method and its variants; see e.g. [3, 23].

2 Preliminaries

In this section, we first fix some definitions and notations, and then explain the basic strategy of our proof for Theorem 1.1.

2.1 Definitions and Notations

A polyhedron P is defined as an intersection of a finite number of closed halfspaces. The polyhedron can be unbounded. The dimension \(\dim (P)\) of P is defined as the dimension of its affine hull. Given a polyhedron P, a linear inequality \(a^\top x \le \beta \) is said to be valid for P if it is satisfied by every \(x \in P\). We say that F is a face of P if there exists a valid inequality \(a^\top x \le \beta \) for P satisfying

$$\begin{aligned} F=P \cap \big \{ x \in \mathbb {R}^d : a^\top x = \beta \big \}. \end{aligned}$$

In particular, 0-, 1-, and \((\dim (P)-1)\)-dimensional faces are, respectively, referred to as vertices, edges, and facets.

The diameter \(\delta (P)\) of a polyhedron P is the smallest integer k such that every pair of vertices of P can be connected by a path with at most k edges of P. In this paper, we are interested in the behavior of

$$\begin{aligned} \Delta (d,n)=\max {\bigl \{ \delta (P) : P \text { is a }d\text {-dimensional polyhedron with }n\text { facets} \bigr \}}, \end{aligned}$$

and in proving an upper bound on it.

In what follows, we only deal with the case where \(n \ge d\) holds. If otherwise, there is no vertex on the given polyhedron, and hence we can treat it as a trivial case with \(\Delta (d,n)=0\).

2.2 Basic Idea of Our Proof

What we will prove is the following.

Lemma 2.1

For \(n \ge d \ge 2\), \(\Delta (d,n) \le (n-d)^{\log _2 g(d)}\) where \(g(d) = 3\displaystyle \sum _{k=2}^d \frac{1}{\log _2 k}.\)

Theorem 1.1 immediately follows from Lemma 2.1 with the following well-known proposition.

Proposition 2.2

\(\displaystyle g(d) \in {\Theta }\biggl (\frac{d}{\log d}\biggr )\).

Proof

Using the sum-integral argument, it is easily seen that

$$\begin{aligned} \sum _{k=2}^d \frac{1}{\log _2 k}&\le 1+\int _2^d \frac{dt}{\log _2 t} = 1+\ln (2) \int _2^d \frac{dt}{\ln t} = 1+\ln (2) \cdot \mathrm{Li}(d), \end{aligned}$$

where \(\mathrm{Li}(d)\) denotes the offset logarithmic integral. It is well known that \(\mathrm{Li}(d) \in \mathrm{O}(d/{\log }\, d)\) for \(d \ge 2\). Also, it is easily seen that \(g(d) \in {\Omega }(d/{\log }\, d )\). These yield the desired result. \(\square \)

Our proof of Lemma 2.1 is by induction on the dimension d. Namely, letting \(f(d,n) = (n-d)^{\log _2 g(d)}\), i.e. the upper bound we want to prove, we will show the following:

Base step::

We show that the desired inequalities, i.e. \(\Delta (d,n) \le f(d,n)\) hold in low dimensions. As we will see later, we can make use of previously known upper bounds, including Todd’s bound.

Inductive step::

Assuming that the desired inequalities hold in dimension \(d-1\), we prove the similar inequalities in dimension d. There are two cases depending on n: The first case \(n <2d\) will turn out to be trivial thanks to a proposition by [18] and the monotonicity property of f(d, n). The second case \(n \ge 2d\) involves detailed and somewhat sophisticated analyses based on the Kalai–Kleitman inequality, which include the main technical difficulties of the proof.

3 Proof of Lemma 2.1

We now get into the detailed proof of Lemma 2.1.

3.1 Base Case

As we will see later in Sect. 3.2, the inductive step turns out to work only when \(d \ge 8\). The base case is hence to show that our bound is valid for \(2 \le d \le 7\). This is ensured by the following lemma.

Lemma 3.1

For \(2 \le d \le 7\), we have \(\Delta (d,n) \le f(d,n)\) for \(n \ge d\).

Proof

Recall that \(g(d)=3 \sum _{k=2}^d (\log _2 k)^{-1}\). Clearly, \(g(d) \ge d\) for \(d=2, 3\). Also, for \(4 \le d \le 7\), we have

$$\begin{aligned} g(d) \ge 3\biggl [ 1+ \frac{1}{2} + \sum _{k=4}^d \frac{1}{\log _2 k} \biggr ] \ge 3\biggl [ 1+ \frac{1}{2} + \frac{d-3}{\log _2 d} \biggr ] \ge 3\biggl [ 1+ \frac{1}{2} + \frac{d-3}{3} \biggr ] \ge d. \end{aligned}$$

Now, recall that Todd’s bound is \((n-d)^{\log _2 d}\), and it is a valid upper bound on \(\Delta (d,n)\) for \(n \ge d\) and for any d. Then, we see that for \(2 \le d \le 7\),

$$\begin{aligned} \Delta (d,n) \le (n-d)^{\log _2 d} \le (n-d)^{\log _2 g(d)} \end{aligned}$$

holds for \(n \ge d\), which completes the proof of this lemma. \(\square \)

3.2 Inductive Step

Now, let us fix d such that \(d \ge 8\), and assume that our bound is valid in dimension \(d-1\). In what follows, we prove the desired inequalities in dimension d by induction on the number of facets, namely, n.

3.2.1 The Case \(n < 2d\)

In this case, we make use of the following proposition.

Proposition 3.2

([18]) For \(n<2d\), we have \(\Delta (d,n) \le \Delta (d-1,n-1)\).

The desired inequality immediately follows from Proposition 3.2 with the induction hypothesis on d since

$$\begin{aligned} \Delta (d,n)&\le \Delta (d-1,n-1) \le f(d-1,n-1) \le f(d,n), \end{aligned}$$

where the last inequality follows from a monotonicity property of f(d, n): we have \(g(d-1) \le g(d)\) by the definition of g, and hence \(f(d-1, n-1) \le f(d,n)\).

3.2.2 The Case \(n \ge 2d\)

Now, it can be assumed that for each pair \((d', n')\) with \(d' <d\) or \(d'=d\) but \(n'<n\), we have the desired inequality. As mentioned before, the following proposition, the Kalai–Kleitman inequality, will be the key ingredient of our proof.

Proposition 3.3

([13]) For \(\lfloor n/2 \rfloor \ge d \ge 2\),

$$\begin{aligned} \Delta (d, n) \le \Delta (d-1, n-1) + 2 \Delta \biggl (d, \biggl \lfloor \frac{n}{2} \biggr \rfloor \biggr ) + 2. \end{aligned}$$

Combined with the induction hypotheses, Proposition 3.3 tells us that

$$\begin{aligned} \Delta (d,n)&\le \Delta (d-1, n-1) + 2 \Delta \biggl (d, \biggl \lfloor \frac{n}{2} \biggr \rfloor \biggr ) + 2 \\&\le f(d-1, n-1) + 2 f\biggl (d, \biggl \lfloor \frac{n}{2} \biggr \rfloor \biggr ) + 2. \end{aligned}$$

Therefore, it suffices to show

$$\begin{aligned} f(d-1, n-1) + 2 f\biggl (d, \biggl \lfloor \frac{n}{2} \biggr \rfloor \biggr ) + 2 \le f(d,n). \end{aligned}$$

Since \(f(d,n)>0\) for \(n \ge 2d\), it can be rewritten as

$$\begin{aligned} \frac{f(d-1, n-1)}{f(d,n)} + 2 \frac{f(d, \lfloor n/2 \rfloor )}{f(d,n)} + \frac{2}{f(d,n)} \le 1. \end{aligned}$$
(1)

Now, noting that \(a^{\log _2 b} = b^{\log _2 a}\) holds for \(a,b > 0\) in general, observe

$$\begin{aligned} f(d,n)=(n-d)^{\log _2 g(d)} = g(d)^{\log _2 (n-d)}. \end{aligned}$$

Employing the last expression in the above equations, LHS of (1) can be rewritten as

$$\begin{aligned} \biggl [ \frac{g(d-1)}{g(d)} \biggr ]^{\log _2(n-d)} + \frac{2g(d)^{\log _2(\lfloor n/2 \rfloor -d )}}{g(d)^{\log _2(n-d)}} + \frac{2}{g(d)^{\log _2(n-d)}}. \end{aligned}$$

Since \(\lfloor n/2 \rfloor -d \le (n-d)/2\), it is bounded from above by

$$\begin{aligned}&\biggl [ \frac{g(d-1)}{g(d)} \biggr ]^{\log _2(n-d)} + \frac{2g(d)^{\log _2((n-d)/2 )}}{g(d)^{\log _2(n-d)}} + \frac{2}{g(d)^{\log _2(n-d)}} \nonumber \\&\qquad \qquad = \biggl [ \frac{g(d-1)}{g(d)} \biggr ]^{\log _2(n-d)} + \frac{2g(d)^{-1 + \log _2(n-d )}}{g(d)^{\log _2(n-d)}} + \frac{2}{g(d)^{\log _2(n-d)}} \nonumber \\&\qquad \qquad = \biggl [ \frac{g(d-1)}{g(d)} \biggr ]^{\log _2(n-d)} + \frac{2}{g(d)} + \frac{2}{g(d)^{\log _2(n-d)}}. \end{aligned}$$
(2)

Furthermore, since \(g(d-1)/g(d)<1\) and \(g(d)>1\) for \(d \ge 8\), and the assumption of \(n \ge 2d\) implies \(n-d \ge d\), we observe that (2) can be bounded from above by

$$\begin{aligned} \biggl [ \frac{g(d-1)}{g(d)} \biggr ]^{\log _2 d} + \frac{2}{g(d)} + \frac{2}{g(d)^{\log _2 d}}. \end{aligned}$$
(3)

Now, observe that for \(d \ge 8\),

$$\begin{aligned} \sum _{k=2}^d \frac{1}{\log _2 k} \ge \sum _{k=2}^7 \frac{1}{\log _2 k}&= \frac{1}{\log _2 2}+\frac{1}{\log _2 3}+\frac{1}{\log _2 4}+\frac{1}{\log _2 5}+\frac{1}{\log _2 6}+\frac{1}{\log _2 7}\\&\ge 1 + 2 \cdot \frac{1}{2} + 3 \cdot \frac{1}{3} = 3. \end{aligned}$$

Therefore, \(g(d) \ge 9\) for \(d \ge 8\). Using this inequality, the third term of (3) is now bounded from above as follows:

$$\begin{aligned} \frac{2}{g(d)^{\log _2 d}} \le \frac{2}{g(d)^{3}}&= \frac{2}{g(d)^{2}} \cdot \frac{1}{g(d)} \le \frac{2}{81} \cdot \frac{1}{g(d)}. \end{aligned}$$

Therefore, it suffices to confirm the following.

Lemma 3.4

For \(d \ge 8\),

$$\begin{aligned} \biggl [ \frac{g(d-1)}{g(d)} \biggr ]^{\log _2 d} + \biggl ( 2+\frac{2}{81} \biggr )\, \frac{1}{g(d)} \le 1. \end{aligned}$$

Proof

It follows from the definition of g(d) that \(g(d)-g(d-1)=3/{\log }_2 \,d\), which implies

$$\begin{aligned} \frac{g(d-1)}{g(d)} = 1-\frac{3}{g(d) \log _2 d}. \end{aligned}$$

We now make use of the following proposition whose proof immediately follows from the fact that \(1+x \le \exp (x)\) for \(x \in \mathbb {R}\):

Proposition 3.5

For \(x>-n\) with \(n > 0\),

$$\begin{aligned} \biggl ( 1+ \frac{x}{n} \biggr )^n \le \exp (x). \end{aligned}$$

Observe that setting \(n \equiv \log _2 d\) and \(x \equiv -3/g(d)\), the conditions required in Proposition 3.5 are satisfied because for \(d \ge 8\), we have

  • \(\displaystyle n \equiv \log _2 d \ge \log _2 8> 1 > 0\), and

  • \(\displaystyle x \equiv -\frac{3}{g(d)} \ge -\frac{3}{g(8)} = -\frac{3}{9} \ge -1 > -n\).

Then, Proposition 3.5 tells us that

$$\begin{aligned} \biggl [ \frac{g(d-1)}{g(d)} \biggr ]^{\log _2 d} = \biggl [ 1+\frac{-{3}/{g(d)}}{\log _2 d} \biggr ]^{\log _2 d}&\le \exp \biggl ( -\frac{3}{g(d)} \biggr ) = \frac{1}{\exp ({3}/{g(d)} )}\\&\le \frac{1}{1+{3}/{g(d)}}= \frac{g(d)}{g(d)+3}, \end{aligned}$$

where the last inequality follows from the fact that \(1+x \le \exp (x)\) for \(x \in \mathbb {R}\). By the discussion so far, it suffices to show

$$\begin{aligned} \frac{g(d)}{g(d)+3} + \biggl ( 2+\frac{2}{81} \biggr )\, \frac{1}{g(d)} \le 1, \end{aligned}$$

which can be simplified to

$$\begin{aligned} g(d) \ge \frac{3( 2+{2}/{81} )}{3-( 2+{2}/{81} )}. \end{aligned}$$
(4)

It is easily seen that RHS of (4) is less than seven. On the other hand, it follows from the proof of Lemma 3.1 that \(g(d) \ge 7\) for \(d \ge 8\), which ensures (4) when \(d \ge 8\). This completes the proof of the claim. \(\square \)

Our inductive step therefore works correctly for \(d \ge 8\). Hence, combined with Lemma 3.1 showing that the base step holds for \(2 \le d \le 7\), this completes the proof of Lemma 2.1, and hence that of Theorem 1.1.

3.3 Remarks on the Proof

3.3.1 Difference from the Previous Studies

Note that in our proof, when deriving (3) form (2), we use d as a lower bound on the term \(n-d\). This is because we can assume \(n \ge 2d\) in the inductive step. In [30], it was proposed to use 8 as a lower bound on the term \(n-d\). This implies \(\log _2(n-d) \ge 3\), which simplifies the inequality that we need to analyze to

$$\begin{aligned} \biggl [ \frac{d-1}{d} \biggr ]^{3} + \frac{2}{d} + \frac{2}{d^{3}}. \end{aligned}$$

One may notice that this is much simpler when compared to ours (3). An improved approach proposed in [28] was to use \(2^m\) as a lower bound on the term \(n-d\) for some fixed m, but this is again a fixed constant.

3.3.2 Refinement

We note that the constant factor of 3 in the definition of \(g(d)=3\sum _{k=2}^d (\log _2 k)^{-1}\) can be reduced further. For example, it is possible to apply a computer-assisted technique of [28] to our setting. Recall that the constant factor 3 was determined in the analysis of (4). Also, observe that RHS of (4) is affected by the threshold drawing the line between the base step and the inductive step. Therefore, using the techniques of [28], one can make this threshold higher to obtain a smaller constant factor.

4 Conclusion

In this paper, we gave a strengthened analysis to the Kalai–Kleitman inequality established in [13] to obtain an improved upper bound of \((n-d)^{\log _2 \mathrm{O}(d/{\log }_2 \,d )}\) on \(\Delta (d,n)\), the maximum possible diameter of a d-dimensional polyhedron with n facets. This is, however, still far from being a polynomial upper bound, i.e. far from a settlement of the polynomial Hirsch conjecture.

The Kalai–Kleitman inequality is known to hold for several abstractions, namely, objects generalizing polyhedra including the connected layer families and the subset partition graphs. Hence, one can easily extend our new upper bound to these abstractions. For further discussion on this topic, we refer to [9, 10, 14].

On the other hand, it is said that we may need to develop novel geometric tools to strengthen analyses of the diameter of high-dimensional polyhedra. One could argue that the Kalai–Kleitman inequality is powerful but not so geometric as we see from its generalizability. Nevertheless, we think that the potential of the Kalai–Kleitman inequality, for deriving upper bounds on \(\Delta (d,n)\), is still unclear, and hence needs further investigations.