Ten-vertex patterns close a route to an Erdős counterexample
For every connected triangle-free graph H on 8, 9 or 10 vertices, the ASYMPTOTIC half-density of large balanced blowups of H — the limit of min-over-half-subsets(edges)/n² as the blowup grows, equal to the exact minimum of xᵀA(H)x/2 over {0 ≤ xᵢ ≤ 1/h, Σxᵢ = 1/2} — is at most 1/50. Exact maxima 1/64 (h=8), 1/81 (h=9), 1/50 (h=10), the last attained by exactly two patterns: the doubled C₅ and the Petersen graph.
Erdős 128 ($250) asks whether a triangle-free graph can have every half-subgraph denser than n²/50; the C₅ blowup approaches exactly n²/50 from below (verified here: 1/75, 2/125, 3/175, 4/225 at t=3,5,7,9) and is conjectured optimal. This claim censuses the natural counterexample route — blowups of small patterns — computing for each connected triangle-free pattern on 8, 9 or 10 vertices the exact asymptotic half-density of its large balanced blowups, in exact rational arithmetic via complete KKT active-set enumeration. All 11,479 patterns; completeness of the pattern list proven by Euler-transforming the generator's connected counts against OEIS A006785 (1, 1, 1, 3, 6, 19, 59, 267, 1380, 9832 → 410 / 1897 / 12172). Nothing exceeds 1/50; exactly two patterns attain it, and an isomorphism test identifies them as C₅[2] and Petersen — the classical extremals, rediscovered blind. The claim was CORRECTED on 2026-08-10 after an adversarial audit found its stated consequence overreached (see status) and one of its own controls could not fail. Both are fixed; the mathematics is unchanged.
▶ Run this script in your browser — no account, nothing uploaded, 8.2s when the author ran itFalsify-box — how to kill this claim
Verification record — every quoted number, re-run 2026-08-09
| quantity | measured | verdict |
|---|---|---|
| patterns certified | 1,647 | |
| max f(H), n=8 | 1/64 | |
| max f(H), n=9 | 1/81 |
Provenance
script status: DETERMINISTIC
datasets:
re-run: 2026-08-09
Edges
Status, honestly
CORRECTED 2026-08-10 after an adversarial audit. The numbers were reproduced with zero disagreements by four independent methods and stand. TWO THINGS WERE WRONG AND ARE NOW FIXED. (1) SCOPE OVERREACH: the claim previously concluded that 'the balanced-blowup route to a counterexample is closed through 10-vertex patterns'. The quantity computed is a minimum over a CONTINUOUS polytope, which contains every realisable half-subset profile — so it is a lower bound on any FIXED blowup's half-density, and only equals the density in the LIMIT. Verified directly: pattern h=9 idx=1092 has asymptotic density 1/81 but at t=1 its 5-subsets carry 2/81 > 1/50; the discrete value descends to 1/81 by t=2 and stays. So the result governs large blowups, not small ones, and the old wording used a bound in the wrong direction — the same defect class as the α-routine retracted in MS-2026-007. (2) A CONTROL THAT COULD NOT FAIL: the completeness check added earlier compared two module-level literal dicts and would print ALL CHECKS PASS with the graph generator sabotaged to emit nothing. Rebuilt to recompute connected counts from the generator and Euler-transform them against OEIS A006785. NOT ESTABLISHED and never was: weighted blowups, non-blowup constructions, and finite-size behaviour.. This status was assigned by hand from the public re-run audit above — it is a judgement made from that evidence, not a number this site computed for itself. What cannot move it is authority: no vote, endorsement, or say-so, from anyone including the maintainer. Independent reproduction would move it; nothing else will.
What this claim's own script draws. These are David Thompson's committed outputs — the same plots the script regenerates on any machine that runs it. You can redraw them yourself below.
Two runs of the same script — mine, and one you can start right now. A match proves the result is reproducible; it is still R0 on this registry's independence rings — same code, so it cannot move a status. Only an outside run does that.
USR-2026-0075 — Erdős 128 balanced-blowup census: exact verification
====================================================================
C_5 (extremal control) f = 1/50 expected 1/50 OK
Petersen (extremal control) f = 1/50 expected 1/50 OK
--------------------------------------------------------------------
census champion n=8 # 243: f = 1/64 (< 1/50: True) OK
census champion n=8 # 245: f = 1/64 (< 1/50: True) OK
census champion n=8 # 252: f = 1/64 (< 1/50: True) OK
census champion n=9 #1086: f = 1/81 (< 1/50: True) OK
census champion n=9 #1091: f = 1/81 (< 1/50: True) OK
census champion n=9 #1092: f = 1/81 (< 1/50: True) OK
census champion n=9 #1099: f = 1/81 (< 1/50: True) OK
census champion n=9 #1100: f = 1/81 (< 1/50: True) OK
census champion n=9 #1270: f = 1/81 (< 1/50: True) OK
census champion n=9 #1281: f = 1/81 (< 1/50: True) OK
====================================================================
ALL CHECKS PASS: controls exact at 1/50; every champion strictly
below the bar with its published exact value reproduced.
Full 1,647-pattern census: rerun with --full (~40 CPU-minutes).
Press Run it to execute this script in your own browser — real CPython, numpy and matplotlib compiled to WebAssembly. Nothing is sent to us; it runs on your CPU. First run downloads the runtime (~10 MB), then takes a few seconds. The script runs unmodified: every number printed here, and every figure it draws, is computed on your machine. The figures appear below.