Adam Zsolt Wagner uses reinforcement learning to find counterexamples to open graph-theory conjectures
Result confirmed
The takeaway
Wagner’s ‘Constructions in combinatorics via neural networks’ (arXiv 2104.14516) used a simple cross-entropy RL method to find explicit counterexamples to several published conjectures in extremal combinatorics and spectral graph theory.
Status
- Claim
Result confirmed
- Our reporting
- High confidence
- Verification
- Preprint only
- Importance
- 2 of 5
- Last verified
- 29 September 2026
Your AI and this story
- GPT-6 AstraIn its training data
- Claude Opus 5.5In its training data
- Gemini 4 HydrogenIn its training data
- Grok 4.7In its training data
It happened before the cutoffs of all four assistants, so it can be in their training data.
Key facts
- arXiv 2104.14516 (29 Apr 2021)
- Refuted several conjectures about graph eigenvalues and a Brualdi–Cao question on permanents of pattern-avoiding matrices
- Small neural network plus deep cross-entropy method; no LLM
- Wagner later joined Google DeepMind and co-authored the 2025 AlphaEvolve maths paper with Tao
What happened
A lone mathematician showed that off-the-shelf RL could disprove conjectures by searching for graphs that violate them.
Why it matters
It was the template for the 2023–2026 wave of AI counterexample finding (FunSearch, AlphaEvolve, PatternBoost, LLM counterexamples).
Sources
2 sources from 1 site. Numbers match the chips in the text.
2 sources: 2 primary
Primary
- Constructions in combinatorics via neural networks (arXiv 2104.14516)arxiv.org, paper
- Reimplementation and extension (arXiv 2403.18429)arxiv.org, paper
Changes
- Filed