Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 55 min ago
PreprintarXiv licencearXiv

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

  • Tianhao Liu
  • Dongdong Ge
  • Yinyu Ye
Open at sourcePDFDOICite

Abstract

Let Δ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≥ d≥ 4, Δu(d,n) ≤ (n−d)log2 Gd, Gd = (4ln 2+o(1))d/((ln d)2), where the asymptotic expression for Gd is understood as d→∞, 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) ≤ (n−d)1/2log2(n−d)+O(1), where the implied constant is absolute. In the regime n − d = Θ(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 = d1/γ+o(1) for fixed 0<γ<1 and an almost-linear bound in the deep-tail regime (ln n)/d→∞. We also show that the leading term of the general bound is sharp within this positive path-counting framework.

Related

  1. An improved bound on the support diameter of nonnegative planar Euler vorticity
    Daomin Cao, Junhong Fan, Guodong Wang
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  2. Volume growth and integral curvature bound for non-negatively curved three-manifolds
    Pak-Yeung Chan, Man-Chun Lee, Mingxiang Li
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  3. An improved upper bound for oriented diameter of graphs with diameter $4$
    Yaokun Feng, Hui Lei, Xiaopan Lian +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. An asymptotically tight bound on oriented diameter
    Yaojun Chen, Jifu Lin, Xiaolin Wang +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. An asymptotically tight bound on oriented diameter
    Jiangdong Ai, Yaojun Chen, Yaokun Feng +5
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{liu2026curvedpath,
  title = {{A Curved-Path Refinement of the Kalai--Kleitman Diameter Bound}},
  author = {Tianhao Liu and Dongdong Ge and Yinyu Ye},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.33434},
  eprint = {2609.33434},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.33434},
}
RIS
TY  - UNPB
TI  - A Curved-Path Refinement of the Kalai--Kleitman Diameter Bound
AU  - Tianhao Liu
AU  - Dongdong Ge
AU  - Yinyu Ye
PY  - 2026
DA  - 2026/09/27
PB  - arXiv
DO  - 10.48550/arxiv.2609.33434
UR  - https://arxiv.org/abs/2609.33434
AB  - Let Δ_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≥ d≥ 4, Δ_u(d,n) ≤ (n−d)^log_2 G_d, G_d = (4ln 2+o(1))d/((ln d)^2), where the asymptotic expression for G_d is understood as d→∞, 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) ≤ (n−d)^1/2log_2(n−d)+O(1), where the implied constant is absolute. In the regime n − d = Θ(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/γ+o(1) for fixed 0<γ<1 and an almost-linear bound in the deep-tail regime (ln n)/d→∞. We also show that the leading term of the general bound is sharp within this positive path-counting framework.
ER  -