Problem detail · source-aware

1.28249... Lower Bound and Partial Upper Bounds for Cost-Preserving Single-Source Unsplittable Flows

partialconfidence 70%

VibeMathed reports this item as partial. VibeMath preserves that report as a source assertion and has not independently authored a plain-language mathematical explanation.

Precise statement

For a single-source unsplittable flow, find the optimal universal additive constant $C$ s.t. every feasible fractional flow $x$ with arc costs $c$ should admit an unsplittable routing $y$ with $c^\top y \le c^\top x$ and $y_a \le x_a + C \cdot d_{\max}$ on every arc. Goemans conjectured $C=1$; this was disproved in July 2026 by a separate seven-vertex counterexample with critical constant $16/15$ (see the Dinitz–Garg–Goemans entry), leaving the optimal $C$ open. Lower bound: a seventeen-terminal common-point interval instance certifies $$ C\ \ge\ \frac{1282494797984843521}{10^{18}}=1.28249\ldots $$ Upper bounds: the paper proves the first unconditional ceiling below 2, but for the codimension-two case only, at complement mass $q=2$. The record cells lie outside it, the $k=17$ instance having $q=11$, so that ceiling does not bound the record ladder. Two figures are conjectures rather than results: $4/3$ as the supremum of critical constants over common-point cells, approached but not attained and not an extrapolation from the ladder (Conjecture 1.1, Theorem 5.1), and $2$ for the universal constant itself (Conjecture 1.2). The proved gap remains $[1.28249\ldots,\ 2]$.

The source statement is reproduced for indexing with attribution. Mathematical correctness requires domain-expert or mechanical review. VibeMath has not independently audited statement fidelity, correctness, priority, or novelty.

What AI did

GPT-5.6 Sol, Claude Fable 5, Claude Opus 5

GPT-5.6 Sol, Claude Fable 5 and Claude Opus 5 carried out the search for constructions, symbolic envelope derivations, proofs, and the exact-verifier development; the human author framed the program, directed the search, set the claim scope, and verified all results independently by hand.

Provider: OpenAI, Anthropic · Prompt public: unknown · Independence: unknown

Verification boundary

unreviewed

The k=17 lower bound is a finite certificate: the verifier rebuilds the 67-arc instance from raw interval data, rediscovers all paths by DFS, and enumerates all 2^17 routings in exact rational arithmetic. Re-run by the site from a clean clone on 2026-08-01; the exact constant, 15 minimizers, and 18-atom hull certificate reproduce. The deletion-star ceiling theorems are conventional proofs in an unreviewed preprint, checked by the author only, with no independent expert review and no formalization. Tier reflects the site's confirmation of the certificate; the structural results remain unreviewed.

Correctness: unknown · statement fidelity: unaudited · peer review: none

Timeline

  1. Unsplittable flows repository

    Record lower bound only. The sub-2 ceiling is the codimension-two case and does not bound the record ladder (k=17 has complement mass 11). 4/3 and 2 are conjectures; the proved gap is [1.28249, 2].

Known method families

construction (source-reported)

Source-reported tools: construction.

Independent: unknown · difference confidence: 0

What remains uncertain

The source did not supply a subject field. VibeMath has not independently audited the mathematical statement, proof, or novelty claim.

  • VibeMath has not independently verified the mathematical claim.
  • AI-attempt independence and training-data exposure are unknown unless explicitly documented.
  • The source did not supply a subject field. VibeMath has not independently audited the mathematical statement, proof, or novelty claim.