AlphaZero finds improved finite extremal-graph bounds
A neural network-guided AlphaZero search with a curriculum generated triangle- and 4-cycle-free graphs that improve known lower bounds for the extremal function ex(n,{C3,C4}) over finite sizes; the proceedings report AlphaZero improvements for n=64–136 and release the graph constructions. The paper also finds improvements using a separate tabu-search method, which often matches or outperforms AlphaZero. This does not solve the asymptotic Erdős conjecture. The result was present in the arXiv v1 posted 2023-11-06; the 2024 IJCAI proceedings paper is a later version.
Technology: AlphaZero reinforcement learning with neural Pairformer representation and curriculum
Publication: Preprint · Test context: direct test. Catalog categories, not an evidence grade.
Result, AI contribution and limits
Evidence context (descriptions follow the cited sources; test type is a catalog classification):
- Publication status: Preprint
- Test type: direct test
- Tested: The paper reports released graphs with improved lower bounds for ex(n,{C3,C4}) for node counts 64–134. Incremental AlphaZero (neural network-guided Monte Carlo tree search) is explicitly reported to improve bounds for sizes 64–136 in the proceedings version; incremental tabu search also improves bounds and the authors report it can match or exceed AlphaZero. This is a finite-graph construction result, not a proof of the asymptotic Erdős conjecture.
- Still unknown: The result consists of explicit finite constructions/lower bounds; the asymptotic conjecture remains open. The work does not establish that learned search outperforms strong local search.
- AI role: AlphaZero with a neural Pairformer representation and a curriculum generated extremal graphs improving the established lower bounds for n=64–136; tabu search is a separate, non-neural method and its results are not attributed to AI.
Evidence sources: https://arxiv.org/html/2311.03583v1 · https://ijcai.org/proceedings/2024/0772 · https://ijcai.org/proceedings/2024/0772.pdf
Source checked · editorial details
The source page was checked against this entry. Independent confirmation is not assessed by this label.
Source type: paper. Paper: linked separately.
Review date: 17 Nov 2026. Review scope: Primary arXiv v1 full text and metadata plus IJCAI 2024 proceedings page/PDF for AlphaZero versus tabu-search graph construction results, theorem limits and author affiliations..
Editorial assessment: Impact 2/5 · Validation 3/5 · Novelty 3/5. Impact and novelty are editorial judgments; validation follows the annotated test type where one exists. Not an evidence grade. Scoring criteria.
Follow-up and relationships
No follow-up recorded; this is not a claim that no follow-up exists.
Follow-up review scope and date are not recorded.
No source-supported relationships recorded.