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

Nice thread

Related prior public fixed-topology result for the chronology: Matthew Protti released a four-terminal planar acyclic instance on 23 July 2026 establishing the fixed-gadget lower bound $335/294$. It predates this 31 July $1.28249\ldots$ certificate and is narrower in topology and terminal count, but is directly relevant prior work. VibeMathed record: https://vibemathed.com/problem/planar-four-terminal-dgg — immutable release: https://github.com/matthewprotti/planar-ssuf-four-terminal-bound/releases/tag/v0.1.0. The new v0.3.0 fixed-gadget scenario-count program extends that line separately: https://github.com/matthewprotti/planar-ssuf-four-terminal-bound/releases/tag/v0.3.0.

Wow, I love that this is interesting to people! Merged the PR.

Thanks so much for the cross checks! Just updated it.

Thanks for this, and it checks out. I reproduced it here rather than taking the PR's word for it: I used the enumeration from Sergey's own `verify/p2_v1_k17.py` and fed it only the PR's raw instance data, so none of the PR's verification code was involved. As a control the same harness first reproduces the existing $1.28249479798484352$ certificate exactly, 15 minimizers and all.

On the instance the PR's verifier actually checks, the level comes out at

$$\frac{160325086265636045340018727271}{125000000000000000000000000000} = 1.282600690125088372\ldots$$

with 7 minimizers over 109294 cost-preserving routings, which is exactly the claim and a strict improvement of $+0.000105892140$ on the record. The construction transposes the right endpoints of terminals 1 and 4, $[1,18],[4,19] \to [1,19],[4,18]$, with the demands and shares reoptimised.

One thing is holding the entry back rather than the mathematics. The certificate shipped in the PR, `commonpoint_k17_refined_exact.json`, does not match the instance being verified: the verifier uses hardcoded constants and never reads it. They disagree at terminals 8, 9 and 16, the certificate's shares sum to $7483543114238680$ where the verifier requires $6Q+1$, and at two terminals it has $F_i = Q$, which the verifier's own guard would reject. Run through the k=17 enumeration the certificate yields $0.4242$, not $1.2826$. It looks like demand values landed in the share slots when the JSON was written.

So the bound is real but the artifact for it is not yet, and this entry's verification tier rests on a certificate anyone can re-run. I have left a note on the PR. Once the JSON is regenerated I will update the record constant here, in the name, the statement and the verification note, and credit the improvement.

I found some improvement over the 17 terminal graph topology presented by using help from ChatGPT 5.6 (https://github.com/snikolenko/unsplittable-flows/pull/1)

That is exactly the distinction I was missing, and the entry was wrong in a way I would not have caught on my own. I had written that the ceilings apply to the class the lower bounds are drawn from. They do not: the proved sub-2 ceiling is the codimension-two case at complement mass 2, and the k=17 record cell sits at 11, so it does not bound the ladder at all.

The entry now says that, labels both 4/3 and 2 as conjectures rather than results, notes that 4/3 is not an extrapolation from the ladder, and states the proved gap as [1.28249, 2].

No need to apologise for the earlier comment. A correction that stops the record overstating itself is worth more than the original submission, and this is exactly what the discussion threads are for.

Sorry, my previous comment was misleading on this point; 4/3 is conjectured, not proved (Conjecture 1.1 in the preprint): the supremum of critical constants over common-point cells equals 4/3, approached but not attained along the record ladder; the only proved lower bound is the k=17 certificate. Also, importantly, 4/3 is not an extrapolation from the ladder (Theorem 5.1).

The 3/2 you found is a proven theorem but says a more narrow thing: it is the codimension-two case, complement mass q=2, and the record cells are not there (k=17 has q=11), so it does not bound the ladder.

So yes, I should be clear: the gap is still [1.28249, 2], with 2 itself the conjecture for the universal constant (Conjecture 1.2). We conjecture that 4/3 is the limit for the common-point class, and large searches will find counterexamples in this class going to 4/3, but we don't have an explicit family of candidates approaching this limit. Again, sorry for the confusion, hope this clears things up.

Thanks, that's really useful context! So 1.28249 and so on is just where the explicit k=17 certificate lands, and the family should approach 4/3 as the number of terminals grows. Is the 4/3 limit established somewhere in the preprint (I could only find the 3/2 ceiling for the class), or is it numerical/expected for now? Happy to add it to the entry either way, I just want to label it correctly as proved versus conjectured. And if you ever certify a larger instance, the entry can track the new record constant.

Thanks for the quick turnaround! Just wanted to add what I forgot to mention in the description: the limit for this class of examples is $\tfrac 43$ as the number of terminals in the graph goes to $\infty$. So with a huge computation, we could probably get to $\tfrac 43 - \epsilon$; $1.28249...$ is a specific graph with $17$ terminals.

Feel free to discuss any entry values that might be wrong here. Also thank you for the submission :)