Turán graphs, C₅ blow-ups, and the finite-order threshold for average quantum transport on triangle-free graphs
Abstract
For a graph G of order n with adjacency matrix A let F_G(t) be the average of |(e^(-i tA))ᵥᵤ|² over ordered pairs of distinct vertices. Song recently determined the maximum of the dense-scaling limit of n²F_G(τ/n) over triangle-free graphons: the balanced complete bipartite graphon is the unique maximizer exactly on 0<τ ≤ τ_(c), where τ_(c)=4sin(τ_(c)/2) ≈ 3.79099, and he asked whether the Turán graph T₂(n) is the unique maximizer of F_G(τ/n) among triangle-free graphs of order n for all large n. No finite-order data was available. We settle the finite question exactly, in integer arithmetic, at pinned rational τ: T₂(n) is the unique maximizer for n=5,6,7 at τ=1/2,1,2,3,frac(15)4,frac(19)5, for n=6 also at τ=9/2, and for n=8 at τ=1/2. Since frac(19)5>τ_(c), the finite-order transition lies strictly above the graphon threshold at every order tested. Above that transition the maximizer is identified and not merely beaten: at (n,τ)=(5,9/2),(5,5),(6,5),(7,9/2) the maximum over all triangle-free graphs on n vertices is attained, to within 1.1 × 10⁻⁷, by a blow-up of C₅ — Song's own nonbipartite competitor, which he introduces at the graphon level but never exhibits at finite order. The cell (7,9/2) lies inside the window in which his second-phase conjecture predicts a bipartite graphon optimum. We also prove a statement strictly stronger than the original question on the range tested: for n=5,6,7 and τ ∈ {1/2,frac(19)5} every triangle-free graph below the Mantel bound is strictly beaten by one with exactly one more edge, so the maximum of the transport value over the graphs with exactly k edges is strictly increasing in k. Every search is a complete exhaustion over all 2^(binom n2) graphs on a labelled vertex set, and every comparison is an exact integer comparison of a truncated closed-walk series against a pinned margin that exceeds twice the largest possible truncation error by a factor of at least 10³ — except in three places, flagged where they occur, in which a truncated value is compared exactly and with no margin instead. The searches are machine-checked in Lean 4.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 1 · current (opens in a new tab)
Source snapshot 2026-08-30 15:34 UTC
File fingerprint
7f505e008d6d75fe74824783c1f92483a95caddf4c476fd06a28a7886c410b1e
Claim ledger
Stated results
TF1candidate2026-08-29
T₂(n) is the unique maximizer of F_G(tau/n) over all labelled triangle-free graphs on n = 5,6,7,8 vertices, exactly, at pinned rational tau
TF2candidate2026-08-29
The finite-order threshold sits strictly above the graphon threshold: T₂(n) is still the unique maximizer at tau = 19/5 > tau_c = 3.790989 for n = 5,6,7, and at tau = 9/2 for n = 6
TF3candidate2026-08-29
Above the finite threshold the maximizer is a C₅ blow-up: explicit witnesses beat T₂(n) at tau = 9/2 (n = 5,7) and tau = 5 (n = 5,6)
TF4candidate2026-08-29
Edge-count monotonicity, strictly stronger than the source's Problem: every triangle-free graph on [0,n) below the Mantel bound is strictly beaten, in the exact order-K truncation F^(K) of the transport value, by one with exactly one more edge (n = 5,6,7; tau = 1/2 and 19/5). The sweep pins no margin, so the reading at the level of F itself costs an additive 2 eta <= 7.1e-8
TF10routine2026-08-29
Beyond every exhaustion: at tau = 5 the balanced C₅ blow-up strictly beats T₂(n) for every 5 <= n <= 18, and at tau = 9/2 for n = 5, 7 and every 9 <= n <= 18 – each with a pinned margin, hence at the level of F itself – with n = 6, 8 explicit exceptions; the n = 6 exception carries a margin too, but the n = 8 one is a margin-free comparison of the order-24 truncations F²⁴
TF11candidate2026-08-29
Identification of the finite maximizer above the threshold: at (n,tau) = (5,9/2), (5,5), (6,5) and (7,9/2) the maximum over ALL triangle-free graphs on [0,n) of the exact order-K truncation F^(K) of the transport value is attained by a C₅ blow-up. The sweep pins no margin, so at the level of F itself this says only that the blow-up comes within 2 eta <= 1.1e-7 of the maximum
TF12known2026-08-29
The source's six-vertex flag-algebra inequality 881 - 2400 t(K₂) + 2856 t(C₄) - 1216 t(C₆) >= 0, kernel-checked at every triangle-free graph on at most 7 labelled vertices, with equality at T₂(n) for even n
TF5known2026-08-29
Mantel's theorem with its equality case, by the same exhaustion, for n <= 7
TF6known data2026-08-29
The number of labelled triangle-free graphs on [0,n): 1, 2, 7, 41, 388, 5789, 133501 for n = 1..7
TF7routine2026-08-29
Instrument controls: coefficient table against its specification, recogniser non-vacuity, constancy of the score on the T₂ isomorphism class, margin not slack by two orders, and refutation of the too-large 'for every tau > 0' claim
TF8routine2026-08-29
Explicit rate for the source's own prop:fixed-n: epsₙ >= 2.97 n^(-5/2), i.e. T₂(n) is the unique maximizer of F_G(tau/n) for all 0 < tau < 2.97 n^(-3/2), where the source proves only that some epsₙ > 0 exists
This ledger entry is reported in prose and is not bound to a Lean theorem.TF9measurement2026-08-29
Cost of the labelled route, and where it dies: n <= 8 landed, n >= 9 needs isomorphism reduction
This ledger entry is reported in prose and is not bound to a Lean theorem.TF13routine2026-08-30
Closure of the coefficient-table control: coefOK verified at all 51 parameter sets (K,p,q,n) the development evaluates — the 28 sets the 23-set coefₜablesₒk missed (n = 4, the n = 8 exhaustion, and every witness sweep) included — and over the whole box K ≤ 30, p ≤ 40, q ≤ 8, n ≤ 40 (468,999 sets), with the used list proved to lie inside the box
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Source. arXiv:2608.27235v1, Xingkun Song, *An Extremal Spectral Problem for Triangle-Free Graphs Arising from Quantum Transport* (announced 2026-08-27). Corpus mirror: /backup/arxiv-src/incremental/2608c/payloads/2608/2608.27235.gz (toplevel shortₜime_quantumₜransportₜriangle_free_V15.tex, plus a supplementaryₘaterial/ directory carrying an exact rational flag-algebra certificate and its Python verifier).
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7