{"id":"arxiv/2606.28041","url":"https://arxiv.org/abs/2606.28041","tags":["math.CO"],"score":0,"title":"The Erdos n^2/25 max-cut conjecture for small multiples of five, via a per-root-MaxCut envelope and blow-up integrality","domain":"math.CO","source":"arxiv","authors":["Alper Ferudun"],"reviews":0,"subject":"math.CO","summary":"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 $β(G)$ for the minimum number of edges whose deletion makes $G$ bipartite and $a(N) = \\max\\{β(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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-26","reactions":{}}