Partition polytope diameter ⌈4κ₁/3⌉ bound

Conjecture 1.3 · arXiv:2507.12748

arXiv Conjecture high confidence— first stated 2025-07-28

Authors: Steffen Borgwardt, Zdeněk Dvořák, Bryce Frederickson, Abigail Nix, Youngho Yoo

Status open high confidence

Conjecture 1.3 from arXiv:2507.12748 posits that the diameter of the partition polytope PP(κ₁,…,κₙ) is at most ⌈4κ₁/3⌉ + c for some absolute constant c. The source paper itself establishes the upper bound ⌈3κ₁/2⌉ (Theorem 1.1) and notes the known lower bound is ⌈4κ₁/3⌉; the conjecture asserts the true diameter matches the lower bound up to a constant. No follow-up paper resolving or making further progress on this conjecture was found in the ~10 months since posting.

Reviewer notes. No follow-up found. The paper is recent (posted 2025-07-28); the conjecture is open with high confidence. The source paper notes that even the special case κ₁=3 (diameter ≤ 4) is open, suggesting the conjecture requires substantially new techniques.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. There exists a constant $c$ such that for any positive integers $n$ and $\kappa_1 \geq \cdots \geq \kappa_n$, the partition polytope $\mathrm{PP}(\kappa_1, \ldots, \kappa_n)$ has diameter at most $\lceil 4\kappa_1/3 \rceil + c$.

Context

Theorem 1.1 establishes an upper bound of $\lceil 3\kappa_1/2 \rceil$ on the diameter of $\mathrm{PP}(\kappa_1,\ldots,\kappa_n)$, while the known lower bound (generalizing a construction from [6]) is $\lceil 4\kappa_1/3 \rceil$. The authors suspect the true diameter is closer to the lower bound, motivating this conjecture. They also note that the natural proof strategy—showing diameter at most 4 when $\kappa_1 = 3$—fails, so new techniques will be required.

Source paper

Improved Decomposition Bounds for Partition Polytopes and Odd-Covers
Steffen Borgwardt, Zdeněk Dvořák, Bryce Frederickson, Abigail Nix, Youngho Yoo · 2025-07-28
https://arxiv.org/abs/2507.12748 PDF source