A Curved-Path Refinement of the Kalai--Kleitman Diameter Bound

Abstract

Let ${\Delta }_u(d,n)$ be the maximum graph diameter of a pointed $d$-dimensional polyhedron with $n$ facets. Using a curved-path encoding of the iterated Kalai--Kleitman recurrence, we prove, uniformly over $n\ge d\ge 4$, \[ Δ_u(d,n) \leq (n-d)^{\log_2 G_d},\qquad G_d = (4\ln 2+o(1))\frac{d}{(\ln d)^2}, \] where the asymptotic expression for $G_d$ is understood as $d\to \infty$, improving the exponent of the previous best quasi-polynomial bound by an additional logarithmic factor. With the quantitative $d$-step reduction, we also obtain the complementary excess-based bound \[ Δ_u(d,n) \leq (n-d)^{\frac{1}{2}\log_2(n-d)+O(1)}, \] where the implied constant is absolute. In the regime $n-d=\Theta (d)$, the latter bound is asymptotically stronger and halves the leading coefficient in the exponent. We further examine their behavior as $n$ grows relative to $d$, obtaining sharper exponents when $n=d^{1/\gamma +o(1)}$ for fixed $0<\gamma <1$ and an almost-linear bound in the deep-tail regime $(\ln n)/d\to \infty$. We also show that the leading term of the general bound is sharp within this positive path-counting framework.