Reinforcement learning refutes several conjectures in extremal combinatorics
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.
- 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 and known objections
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 ↗
Disagree with these grades?
Bring a citation: a grade moves on evidence, not on argument.
Or on GitHub: submit a check challenge the grade send a correction or send a pull request
Flag this for triage
Signals order the review queue and nothing else. They are never published, and they never move a grade: that takes a citation.
Entry history (1 event)
- AddedEntered the registry graded Independently checked and Search scaffold.
Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.
Graded independently checked for verification and search scaffold for autonomy. What these mean.
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-combinatoricsBibTeX
@misc{whataifound-telavivuniversity-2021-combinatorics,
title = {Reinforcement learning refutes several conjectures in extremal combinatorics},
author = {{whataifound.org}},
year = {2021},
howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
note = {Result by Tel Aviv University. Verification: Independently checked. Autonomy: Search scaffold.},
url = {https://whataifound.org/finding/2021-04-29-wagner-combinatorics}
}