Reinforcement learning refutes several conjectures in extremal combinatorics
Reinforcement learning refutes several conjectures in extremal combinatorics is graded independently checked on whataifound.org, with the AI's role graded search scaffold.
A neural network building graphs edge by edge under a cross-entropy search produced explicit counterexamples to several published conjectures in graph theory and extremal combinatorics.
- Verification
- Independently checked
- Autonomy
- Search scaffold
- Lab
- Tel Aviv University
- Model
- Deep cross-entropy method (custom network)
- Field
- Mathematics
- Date
- 2021-04-29
- Human collaborators
- Adam Zsolt Wagner
What was found
Each conjecture was rewritten as a scoring function on graphs. A network proposes graphs one edge at a time, the top-scoring constructions are kept, and the network is retrained on them, so the search drifts toward whatever the conjecture says should be impossible. Among the conjectures refuted are a question of Brualdi and Cao on maximising permanents of pattern-avoiding matrices and several concerning adjacency and distance eigenvalues of graphs. The counterexamples are small finite graphs printed in the paper, so each can be checked by hand or by a few lines of code.
Novelty check
Computer search for combinatorial counterexamples predates this work — linear-programming and SAT-based refutations go back years, including Refuting conjectures in extremal combinatorics via linear programming (2019). What was new is the reinforcement-learning formulation and the specific conjectures, which were open at the time. The paper is widely treated as the origin of the "AI finds counterexamples" line of work.
Caveats
An arXiv preprint; no journal publication is listed on the arXiv record five years on. The refuted conjectures are individually modest — none is a named problem of the Erdős or Jacobian class — and several came from open-problem lists rather than headline literature. Autonomy is search-scaffold on the strictest reading: the human chose the conjectures, wrote the scoring function that encodes each one, and designed the search; the network only proposes graphs.
Independent checks
Roucairol & Cazenave, Monte Carlo search replication and extension: reproduced the refutations and found further counterexamples by different search · link ↗
Sources
How this is graded
whataifound.org grades every entry on two axes: verification (how solid the result is, from a machine-checked proof down to refuted) and autonomy (how much the AI did versus its human collaborators). This finding is independently checked and search scaffold. Full definitions are in the methodology.
Cite this entry
whataifound.org (2021). Reinforcement learning refutes several conjectures in extremal combinatorics. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2021-04-29-wagner-combinatorics