The Erdős n 2 / 25 n^{2}/25 max-cut conjecture for small multiples of five, via a per-root-MaxCut envelope and blow-up integrality
Alper Ferudun · 2026
Read The Erdős n 2 / 25 n^{2}/25 max-cut conjecture for small multiples of five, via a per-root-MaxCut envelope and blow-up integrality by Alper Ferudun (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-28041.txt.
Description
Erdős conjectured that any triangle-free graph can be made bipartite by deleting few edges. The bound is the number of vertices squared, divided by twenty-five. Alper Ferudun presents a computer-assisted proof in 2026 for small multiples of five. The result covers vertex counts from five up to two hundred, in steps of five. For those sizes, the worst case exactly meets the conjectured bound. The extremal example is the balanced blow-up of a five-cycle.
Three ingredients combine. A per-root-MaxCut envelope bounds the deletion number using 107 triangle-free root types on seven vertices. An order-ten flag-algebra certificate controls the medium-density band, where earlier work left the conjecture open. A blow-up identity plus integrality then converts the bound into the exact result. Prior progress had settled only the density tails, plus a weaker global bound.
Catalog record
| CREATOR | Alper Ferudun |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 26 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.28041