1.17353 planar lower bound and exact local envelopes for cost-preserving single-source unsplittable flow

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$ on every arc. We provide several new results on $C$ :

(1) record lower bound for planar instances (against known ceiling 2): $C \ge \frac{58676765987259}{50000000000000} = 1.17353531974518;$
(2) local envelope ladder (proved): $E(2) = 1$ , $E(3) = 9/8$ , $E(4) = (299 - 41\cdot\sqrt{41})/32 = 1.13974707\ldots$ , attained by the counterexamples from our previous work; record constants of our previous work are now exact local envelopes of the general theory;

(3) global results: every exact-two-path instance with rows touching at most three terminals satisfies $C \le 2$ (first unconditional constant for an unbounded class); interaction arity m gives $\lceil\lfloor 3m/2\rfloor /2\rceil \cdot D$ ;

(4) classes closed exactly: out-trees 0; two-layer hubs 1; outerplanar two-exit interval spines 1 (sharp); series-parallel $\le 1$ ;

(5) band merger constant $K^* \ge 2.5652\ldots$ (twice the general lower bound $1.2826\ldots$ ).

Result: Proved(see note)
Status: Partial result
AI contribution: AI co-developed
Method: Argument
Field: Combinatorics
Posed by: Dinitz, Garg, Goemans
Year posed: 1999
Years open: 27y
Solved: 2026-08-13
Model: GPT-5.6 Sol, Claude Fable 5, Claude Opus 5
Vendor: OpenAI, Anthropic
Collaborators: —
Verification: Site-confirmed
Publication: Preprint
Significance: 15 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Part III of a series, and the first unconditional positive results in it. Settled exactly: the local envelope ladder $E(2)=1$ , $E(3)=9/8$ and $E(4)=(299-41\sqrt{41})/32=1.13974707\ldots$ , which recasts the earlier record constants as exact envelopes of the general theory rather than isolated instances, plus exact constants for four classes - out-trees 0, two-layer hubs 1, outerplanar two-exit interval spines 1 (sharp), series-parallel at most 1. Improved but not settled: the planar lower bound rises to $1.17353531974518$ against the known ceiling 2, and every exact-two-path instance whose rows touch at most three terminals satisfies $C\le2$ , the first unconditional constant for an unbounded class. The universal question is untouched - it reduces here to a single factor-two merger statement with certified wall $K^*\ge2.5652\ldots$ , twice the refined general lower bound $1.28260069\ldots$ .

What the AI did

Like the previous parts (https://vibemathed.com/problem/1-28249-lower-bound-and-partial-upper-bounds-for-cost-preserving-single-source-u), this work was written in close collaboration with GPT 5.6 Sol, Claude Fable 5, and Claude Opus 5, which contributed proofs, failed routes, adversarial reviews, code for the verification campaign, and more. This time, I cannot claim that it was a single tour de force by the models like the original counterexample by Rybin; it was a long journey with a lot of human involvement, but the key ideas were provided by the LLMs. I have personally verified and edited this work in its entirety, and all errors are mine.

Verification

Reproduced by this site on 13 August 2026 from a clean clone, in two parts. First the repository's own suite: all fourteen verifiers in verify/run_all.sh pass, exit 0. Those cover Parts I and II only, so the headline planar record was rebuilt here independently. Reading only the raw arc list, a depth-first search rediscovers exactly two source-to-terminal paths for each of the six terminals; the fractional arc loads recompute exactly on all 21 arcs; all 64 routing overloads recompute exactly in rational arithmetic; the cost rule fits all 64 of the certificate's own cost deltas; 42 routings come out cost-preserving as claimed; and the minimum overload over those 42 is $58676765987259/50000000000000$ , exactly the record. Planarity was checked independently too, by Euler ( $V=16$ , $E=21$ , $F=7$ ) and by networkx. The envelope constant was derived symbolically from the stated quartic rather than read off: $t^*=(7-\sqrt{41})/4$ is the unique critical point in $(0,2-\sqrt3)$ , giving $E(4)=(299-41\sqrt{41})/32$ . The 2,015-cell closure ledger is internally complete: five forms of 403, family counts summing to 2,015, every cell on one of nine solver-free lemmas. Not checked: the mixture characterization, the network-matrix total-unimodularity theorem and the tree-path four-colouring theorem, conventional proofs in an unreviewed preprint with no independent expert review. The tier records this site's reproduction of the certificates; the structural theory remains unreviewed.

Sources

PaperZenodo preprint
CodeUnsplittable flows repository

Related entries

ContinuesCommon-Point Interval Systems for SSUF

Submitted by BraveDingo215 on 13 Aug 2026