Exact SSUF scenario-count ladder on the four-terminal planar gadget

For the released four-terminal planar acyclic single-source unsplittable-flow gadget, require one unsplittable routing to be no more expensive than a prescribed fractional routing under each of $m$ strictly positive full-demand route-cost-difference scenarios. What is the worst-case normalized additive upper-arc deviation? The v0.3.0 fixed-gadget scenario-count ladder proves
$\beta_G^{(m,+)}= \begin{cases} \dfrac{299-41\sqrt{41}}{32},&m=1,\\ \dfrac{17}{8},&m=2,\\ 3,&m=3,\\ 4,&m\ge4. \end{cases}$
The $m\ge2$ values are non-attained suprema; no attainment or non-attainment assertion is made for $m=1$ . The one-scenario value also holds for legally realizable signed and zero route-cost differences; no such multi-scenario extension is claimed.

Result: Proved(see note)
Status: Variant only
AI contribution: AI co-developed
Method: Argument
Field: Combinatorial optimization; unsplittable flow
Posed by: Matthew Protti
Year posed: 2026
Years open: 0y
Solved: 2026-08-04
Model: GPT-5.6 Pro; Codex
Vendor: OpenAI
Collaborators: Matthew Protti
Verification: Unreviewed
Publication: Preprint
Significance: 4 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Fixed four-terminal planar DAG; positive route-cost differences for m≥2, with non-attained suprema; signed/zero only for m=1, whose attainment is unstated. No topology-wide/unrestricted-planar claim.

What the AI did

GPT-5.6 Pro generated and developed substantial portions of the construction and parameter searches, symbolic derivations, analytic proofs, exact verifiers, adversarial analyses, and manuscript drafts. Codex sessions implemented or reconstructed code paths, performed repository-level checks, and attacked proposed claims. Matthew Protti selected and framed the targets, required exact arithmetic, exhaustive finite checks, mutation tests and hostile review, identified and forced correction of material errors and overclaims, chose the final theorem scope and public wording, reviewed the work, and authorized the release. Role-separated model review reduced some shared-context risk but was not independent human verification.

Verification

The unrefereed v0.3.0 release contains complete analytic proof sources, exact certificates, deterministic replay, claim ledgers, and review evidence for the fixed-gadget ladder. The $m=2$ rung was first released on 28 July 2026 in immutable v0.2.1; Matthew Protti's no-error review covered that corpus only. v0.3.0 adds the exact $m=1$ , $m=3$ , and $m\ge4$ branches while preserving the earlier source. Exact-arithmetic checks, exhaustive finite enumeration, mutation tests, claim-scoped role-separated AI reviews, a blind independent reconstruction of the fixed finite atlas, and one scope-limited human-directed AI-assisted adversarial report are included. The latter did not inspect every theorem component. No Lean proof, full independent expert verification, or journal peer review is documented, so the catalog status remains Unreviewed. The analytic proofs are authoritative; computation is corroborative.

Sources

Related entries

RelatedDinitz-Garg-Goemans

Submitted by Matthew Protti on 31 Jul 2026