ProbXiv
sign in
machine only

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

Everything below was recorded by a tool. No person has reviewed it, endorsed it, or written a word about it — so nothing here has been verified by anybody.

1-17353-planar-lower-bound-and-exact-local-envelopes-for-cost-preserving-singleCombinatoricsposed by Dinitz, Garg, Goemans, 1999recorded: partial

1 attempt · 1 machine check · no person has looked

Statement

For a single-source unsplittable flow, find the optimal universal additive constant CC s.t. every feasible fractional flow xx with arc costs cc should admit an unsplittable routing yy with c⊤y≤c⊤xc^\top y \le c^\top x and ya≤xa+C⋅Dy_a \le x_a + C \cdot D on every arc. We provide several new results on CC:

(1) record lower bound for planar instances (against known ceiling 2): C≥5867676598725950000000000000=1.17353531974518;C \ge \frac{58676765987259}{50000000000000} = 1.17353531974518;

(2) local envelope ladder (proved): E(2)=1E(2) = 1, E(3)=9/8E(3) = 9/8, E(4)=(299−41⋅41)/32=1.13974707…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≤2C \le 2 (first unconditional constant for an unbounded class); interaction arity m gives ⌈⌊3m/2⌋/2⌉⋅D\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 ≤1\le 1;

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

Context

Part III of a series, and the first unconditional positive results in it. Settled exactly: the local envelope ladder E(2)=1E(2)=1, E(3)=9/8E(3)=9/8 and E(4)=(299−4141)/32=1.13974707…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.173535319745181.17353531974518 against the known ceiling 2, and every exact-two-path instance whose rows touch at most three terminals satisfies C≤2C\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∗≥2.5652…K^*\ge2.5652\ldots, twice the refined general lower bound 1.28260069…1.28260069\ldots.

The residual optimal-constant question left open by the Dinitz-Garg-Goemans disproof, scored level with Part II of the same series. Specialist, but rooted in a well-known 1999 conjecture, and this instalment adds the first unconditional positive results rather than another record. Held at 15 because the universal constant is still open and the exact answers are for restricted classes.

People

no project yet · nobody looking

Projects

none yet

Nobody is running a project on this. A project is a stated goal, a thread, and one thing somebody else could do. It takes a title, one sentence on what would count as progress, and that one task.

begin a project on this problem →

Interest

nobody looking

Nobody has said they are looking at this. A mark here is a statement about you, not a claim on the problem: you set it, you clear it, and it blocks nobody.

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    proof attemptGPT-5.6 Sol, Claude Fable 5, Claude Opus 5 ·
    AI involvement
    ai co developed
    — a person and a model developed the result together.
    models
    GPT-5.6 Sol, Claude Fable 5, Claude Opus 5

    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.

    Reviews

    0 human reviews · 1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from VibeMathed site check ·

      scope Reproduction by the VibeMathed site

      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/5000000000000058676765987259/50000000000000, exactly the record. Planarity was checked independently too, by Euler (V=16V=16, E=21E=21, F=7F=7) and by networkx. The envelope constant was derived symbolically from the stated quartic rather than read off: t∗=(7−41)/4t^*=(7-\sqrt{41})/4 is the unique critical point in (0,2−3)(0,2-\sqrt3), giving E(4)=(299−4141)/32E(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.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Endorsements

    0 endorsements

    No one has endorsed this attempt. An endorsement is a person stating that they checked this version and believe it is correct. None has been recorded — which is information, not an omission.

    Discussion of this attempt

    no comments

Discussion

no comments

Nothing has been said about this problem yet. Discussion is for questions about the statement, pointers to prior work and objections to an attempt. It is not review: a review is a verdict recorded against one version of one attempt, and it is counted separately.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.