run 036Settled
../lab/runs/036-expansion-profile-coset-graph.mdPredictionρ_Φ ∈ [0.50, 0.95] — sets of one eighth of the graph still expand at more than half the random rate; the loss of expansion is gradual and the Sipser–Spielman guarantee survives at this scale with a constant-factor loss
Falsifierρ_Φ ≤ 0.30 — expansion has already collapsed at one eighth of the graph; the combinatorial code guarantees give nothing here and the intermediate cell's code ceiling is not reachable by Tanner constructions
VerdictCONFIRMED — ρ_Φ = 104/134 = 0.776. The coset graph's profile is identical to the random 4-regular graph's for sets up to 16 vertices (|∂S| = 14, 24 at s = 8, 16: locally tree-like, as the cogrowth data said), then falls behind gradually: ratio 0.91 at s = 32, 0.82 at 64, 0.78 at 128, 0.68 at 256, 0.63 at 512 (176 against 278 at the bisection, the METIS optimum recovered). The 32×32 torus at the same N runs at √s: 12, 16, 24, 32, 46, 66, 64. The scale at which the ratio halves is beyond N/2 at N = 1024, so at this size the Sipser–Spielman guarantee loses only a constant factor; whether α(N) = s*(N)/N falls like 1/log N is the level-5 question. The full Cayley graph's anneals at N = 4096 are unreliable at large s (368 at the bisection against ≤ 180 known) — the K₄-blow-up traps the quench, the same glassiness as run 030 — so the coset graph is the instrument, with |∂|_full(4s) = |∂|_coset(s) for coset-unions.
Sealed before any anneal was run (2026-09-27, codifier). Between 0.30 and 0.50 is unanticipated.
Reported, not scored. The full profiles Φ(s) for s = N/128 … N/2 on the coset graph, the random 4-regular graph and the 32×32 torus at N = 1024; the same at N = 32; and the full Cayley graph Cay(G/St(4)) against a random 4-regular graph and the 64×64 torus at N = 4096. The scale s* at which Φ_coset/Φ_random first drops below 1/2, per N, is the number the level-5 run (Claude Code) will extend: the Sipser–Spielman distance bound is α·N with α = s*/N, and "graceful" means α(N) falls no faster than 1/log N.
Why edge expansion first. The code theorems want vertex (unique-neighbour) expansion of the Tanner graph; for a 4-regular host the vertex expansion of a small set is at least a quarter of its edge expansion, and the edge profile is what the fixed-M Ising quench measures exactly. The vertex profile is the level-5 run's job, with the code itself.
---
Minimum edge boundary |∂S| over sets of size s (best of 20 anneals):
| s | 8 | 16 | 32 | 64 | 128 | 256 | 512 |
|---|---|---|---|---|---|---|---|
| coset graph, level 4 (N = 1024) | 14 | 24 | 40 | 64 | 104 | 144 | 176 |
| random 4-regular (N = 1024) | 14 | 24 | 44 | 78 | 134 | 212 | 278 |
| ratio | 1.00 | 1.00 | 0.91 | 0.82 | 0.78 | 0.68 | 0.63 |
| 32×32 torus (N = 1024) | 12 | 16 | 24 | 32 | 46 | 66 | 64 |
At N = 32: coset graph 6, 8, 12, 16; random 6, 8, 10, 12; 4×8 torus 6, 8, 8, 8 (s = 2, 4, 8, 16) — the level-3 coset graph expands better than the random graph at its bisection. Full Cayley graph at N = 4096 (s = 32 … 2048): 24, 46, 74, 130, 210, 310, 368 against random 52, 98, 174, 318, 548, 856, 1118 and torus 24, 34, 48, 66, 94, 134, 154 — quench-limited above s ≈ 128, see verdict.
Reading for the code. Locally the host is a random graph; the expansion deficit grows with the set's size like a slow power, |∂S| ≈ s^{0.72} against the random graph's ≈ s^{0.78} and the torus's s^{0.5} over this range. A Tanner code on the coset graph would inherit small-set expansion good enough for the Sipser–Spielman argument up to sets of a constant fraction of N at this N, with the constant shrinking with N at a rate this run cannot see and the level-5 graph can. The construction itself is to be sealed as its own run before it is built (the design goes to Claude Code): a Tanner code on the coset graph with a higher-degree generating set (words of length ≤ 3, degree ≈ 23) so the inner code has room, distance estimated against the same code on a random regular graph of the same degree and size.
generated 2026-10-25the lab index