AI Science Tracker

AlphaZero finds improved finite extremal-graph bounds

Google DeepMind; Imperial College London; Yonsei University; University of Bonn; Worcester Polytechnic Institute · 6 Nov 2023 · mathematics

Discovery

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.

Open in the full catalog for filters, charts and related discoveries.