The Erdos n^2/25 max-cut conjecture for small multiples of five, via a per-root-MaxCut envelope and blow-up integrality

Abstract

Erdős conjectured that every triangle-free graph on $N$ vertices can be made bipartite by deleting at most $N^2/25$ edges; the bound would be sharp, attained by the balanced blow-up $C_5[N/5]$. Writing $\beta (G)$ for the minimum number of edges whose deletion makes $G$ bipartite and $a(N)=\max \{\beta (G):G$ triangle-free on $N$ vertices$\}$, the conjecture is $a(N)\le N^2/25$, and for $N=5n$ it reads $a(5n)\le n^2$. Balogh, Clemen and Lidícký proved it for large $N$ in the two density tails (edge density at most $0.2486$ or at least $0.3197$) and proved the global bound $a(N)\le N^2/23.5$; the medium-density band remains open. We prove \[ a(5n) = n^2 \qquad \text{for every } 1 \le n \le 40, \quad \text{i.e. } N \in \{5,10,\dots,200\}. \] The proof is computer-assisted and combines three ingredients. (i) A \emph{per-root-MaxCut envelope}: for the $107$ triangle-free $7$-root types, the mean over types of the best per-type cut is an upper bound $d_{\mathrm{mono}}(W)\le U_7(W)$ that is \emph{tight} at the $C_5$-blow-up. (ii) An order-$10$ flag-algebra certificate -- the per-root-MaxCut rows at $7$ and $8$ roots together with rooted-Horn cuts and a manifestly-PSD moment block -- bounds the envelope on the medium band, $U_7(W)\le \frac{2}{25}+\delta$ with an explicit rational $\delta \approx 4.8558\times 10^{-5}$, for every triangle-free graphon $W$ of edge density in $[0.2486,0.3197]$. (iii) The blow-up identity $\beta (G[t])=t^2\beta (G)$ plus integrality of $\beta$ turns this into $\beta (G)\le n^2+\frac{25}{2}{n}^2\delta$ for any $5n$-vertex band-density $G$, and $\frac{25}{2}{n}^2\delta <1$ for $n\le 40$; the two density tails are handled by the Balogh-Clemen-Lidícký bounds, transferred to finite $N$ by the same blow-up. The envelope bound $d_{\mathrm{mono}}\le U_7$ is a genuine graphon upper bound (each per-root rule is one global $2$-colouring), the certificate is verified in exact rational arithmetic, the moment positivity is Razborov's flag-algebra theorem exhibited as an exact Gram factorization, and the bound is cross-checked against brute-force max-cut on all triangle-free graphs of order at most $12$. The same envelope at orders $9$ and $10$ provably does not reach the constant needed for larger $n$; we explain why, and locate the all-$n$ conjecture at a single self-tight obstruction.

9 pages. Computer-assisted. Ancillary files: order-10 per-root-MaxCut + rooted-Horn flag-algebra certificate with an independent exact-arithmetic verifier, a self-contained brute-force max-cut ground-truth checker, and the manifestly-PSD moment Gram certificate