Adam Zsolt Wagner uses reinforcement learning to find counterexamples to open graph-theory conjectures
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.
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
Science result
- Field
- mathematics / extremal combinatorics / spectral graph theory
- Problem
- Several published conjectures on graph invariants
- Result
- Explicit counterexamples found by an RL agent that treats building a graph as a game, rewarded by how badly the conjecture fails.
- AI system
- deep cross-entropy RL
- Human role
- Human chose conjectures and reward functions; search autonomous; counterexamples trivially checkable
- Verification
- Counterexamples checkable by direct computation; reimplemented by others (arXiv 2403.18429)
- Status
- confirmed
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).
Changelog
- 2026-09-29: created
Related events
Sources (2)
- paperConstructions in combinatorics via neural networks (arXiv 2104.14516)
- paperReimplementation and extension (arXiv 2403.18429)
id: 2021-04-29-wagner-rl-counterexamples · updated 2026-09-29 · open in the interactive timeline