Abstract In 1992, Kalai and Kleitman proved that the diameter of a d -dimensional polyhedron with n facets is at most n 2 + log 2 d . In 2014, Todd improved the Kalai–Kleitman bound to ( n − d ) log 2 d . We improve the Todd bound to ( n − d ) − 1 + log 2 d for n ≥ d ≥ 7 , ( n − d ) − 2 + log 2 d for n ≥ d ≥ 37 , and ( n − d ) − 3 + log 2 d + O 1 ∕ d for n ≥ d ≥ 1 .
We also note that there are studies that attempt to understand the behavior of @math when the number of facets is sufficiently large. Gallagher and Kim @cite_23 provided an upper bound on the diameter of a normal simplicial complex and showed the tail-polynomiality ; more specifically, they showed that the diameter is bounded from above by a polynomial in @math when @math is sufficiently large. An alternative simpler proof for such tail-polynomial upper bounds can be found in Mizuno and Sukegawa @cite_13 . In contrast, in this paper, we assume that @math is large, and try to utilize this assumption to strengthen the previous results.
@cite_13 @cite_23
2338231399 2298099604
Let @math denote the maximum diameter of a @math -dimensional polyhedron with @math facets. In this paper, we propose a unified analysis of a recursive inequality about @math established by Kalai and Kleitman in 1992. This yields much simpler proofs of a tail--polynomial and tail--almost--linear bounds on @math which are recently discussed by Gallagher and Kim. In 1992, Kalai and Kleitman proved a quasipolynomial upper bound on the diameters of convex polyhedra. Todd and Sukegawa-Kitahara proved tail-quasipolynomial bounds on the diameters of polyhedra. These tail bounds apply when the number of facets is greater than a certain function of the dimension. We prove tail-quasipolynomial bounds on the diameters of polytopes and normal simplicial complexes. We also prove tail-polynomial upper bounds on the diameters of polyhedra.