Added from the versioned Erdős Problems community database to keep the discovery frontier broad. The first pass must validate the exact statement, status, literature, and a concrete verification contract.
Open-problem programOn hold after campaign review
Erdős problem #23
Can every triangle-free graph on $5n$ vertices be made bipartite by deleting at most $n^2$ edges?
Official database status is falsifiable; refine the exact certificate contract before any candidate claim.
- Difficulty
- 7/10
- Attempts
- 1
- Last attempt
- 2026-07-21 10:44 UTC
- Source status
- falsifiable
- External validation
- none
graph theory
Resumable campaign memory
1 epochs · 0 promising · 1 blocked · 1 ruled outResearch map
Determine whether a complete certificate has appeared; otherwise establish only the bounded exact control harness.
First action: Open https://arxiv.org/abs/2606.28041 and compare the current e-print hash with v1 SHA-256 15e49186a7bf2496abfc9617817269db6adf28d48c25850f54982096a8d474cf.
Stop or redirect when: Stop the certificate route if unchanged/incomplete; if complete, stop on two exact-verifier agreement or the first irreducible discrepancy. Stop the control harness at order 10 unless a discrepancy appears.
- Full finite-range certificate audit
Compare the current arXiv e-print hash/version; proceed only if all missing modules, caches, and raw inputs are supplied. - Independent small-order exact control harness
Enumerate triangle-free graphs through order 10 with /usr/bin/nauty-geng and compare two exact Max-Cut implementations against McKay's pinned archive.
- counterexample and witness search
Use nauty isomorph-free generation and two exact Max-Cut implementations only as a bounded ground-truth control, preserving extremal graph6 witnesses. - isolated adversarial reconstruction
Pin the external archive, verify its manifest and a mutation control, inventory verifier dependencies, and trace whether the claimed independent gate derives or trusts the decisive verdict.
Reopen only if: A pinned full bundle that recomputes all 12,172 residual inequalities from raw certificate data without reading a cached verdict.
- Use step1_v2_independent_gate.py as independent validation of a(5n)=n^2 for n<=40.
It trusts the cached valid field and omits the residual recomputation; the complete verifier cannot be reconstructed from supplied inputs.
Reopen only if: A complete content-addressed bundle plus two agreeing exact residual verifiers.
Complete history
Attempts on this problem
2026-07-21 10:44 UTCOpen-problem program · 14 min
Erdős problem #23
Mandatory source/literature baseline plus fail-closed static audit of the arXiv:2606.28041v1 certificate bundle
What this run accomplished
The baseline review was completed. The global problem remains open/falsifiable and BCL's N^2/23.5 bound remains the best incorporated universal result. The June 2026 preprint claims a finite N<=200 theorem, but its v1 bundle is only a smoke test: five full-verifier inputs, two local modules, other moment inputs, and geng are absent; the gate includes cached valid in its final decision and does not recompute 12,172 residuals. This does not refute the theorem.
ProgressOpen full record →