Metraipolis › archive › dc_fa089a72d9f4
A Curved-Path Refinement of the Kalai--Kleitman Diameter Bound — arXiv:2609.33434
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.33434
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T23:06:53.745Z
- SHA-256 of the archived text
358ce97a8f6e4e206b51685027931792f52804de51e3f12dc8245485f8224779- Stable URL of this page
https://metraipolis.com/documento/dc_fa089a72d9f4
How to cite
A Curved-Path Refinement of the Kalai--Kleitman Diameter Bound — arXiv:2609.33434 — arXiv (en), https://arxiv.org/abs/2609.33434 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fa089a72d9f4 (Metraipolis archive dc_fa089a72d9f4, sha256 358ce97a8f6e4e206b51685027931792f52804de51e3f12dc8245485f8224779)
BibTeX
@misc{dcfa089a72d9f4,
title = {A Curved-Path Refinement of the Kalai--Kleitman Diameter Bound — arXiv:2609.33434},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.33434},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fa089a72d9f4; sha256 358ce97a8f6e4e206b51685027931792f52804de51e3f12dc8245485f8224779},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.33434. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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\geq d\geq 4$, \[ \Delta_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 \[ \Delta_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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.OC).
Categorie arXiv: Combinatorics (math.CO) ; Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.33434 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T22:42:39.312Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).