# Constructions in combinatorics via neural networks

arXiv: https://arxiv.org/abs/2104.14516 · HTML: https://mlsanity.com/paper/2104.14516/

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 54 references that are in the map.
- First posted on arXiv 29 Apr 2021.

## Builds on (most cited first, 8 of 8)

- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [MolGAN: An implicit generative model for small molecular graphs](https://mlsanity.com/paper/1805.11973/) (2018)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [NetGAN: Generating Graphs via Random Walks](https://mlsanity.com/paper/1803.00816/) (2018)
- [Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking](https://mlsanity.com/paper/2005.11081/) (2020)

## Built on by (most cited first, 30 of 48)

- [Formal Mathematical Reasoning: A New Frontier in AI](https://mlsanity.com/paper/2412.16075/) (2024)
- [On scientific understanding with artificial intelligence](https://mlsanity.com/paper/2204.01467/) (2022)
- [ThetaEvolve: Test-time Learning on Open Problems](https://mlsanity.com/paper/2511.23473/) (2025)
- [PatternBoost: Constructions in Mathematics with a Little Help from AI](https://mlsanity.com/paper/2411.00566/) (2024)
- [Global Lyapunov functions: a long-standing open problem in mathematics, with symbolic transformers](https://mlsanity.com/paper/2410.08304/) (2024)
- [Is deep learning a useful tool for the pure mathematician?](https://mlsanity.com/paper/2304.12602/) (2023)
- [Learn from Failure: Fine-Tuning LLMs with Trial-and-Error Data for Intuitionistic Propositional Logic Proving](https://mlsanity.com/paper/2404.07382/) (2024)
- [Data for Mathematical Copilots: Better Ways of Presenting Proofs for Machine Learning](https://mlsanity.com/paper/2412.15184/) (2024)
- [Machine learning detects terminal singularities](https://mlsanity.com/paper/2310.20458/) (2023)
- [Reinforced Generation of Combinatorial Structures: Ramsey Numbers](https://mlsanity.com/paper/2603.09172/) (2026)
- [Autonomous Research Agents: A Survey of AI Scientists and the Verification Gap](https://mlsanity.com/paper/2608.05179/) (2026)
- [Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search](https://mlsanity.com/paper/2311.03583/) (2023)
- [Can Transformers Do Enumerative Geometry?](https://mlsanity.com/paper/2408.14915/) (2024)
- [Machine learning the dimension of a Fano variety](https://mlsanity.com/paper/2309.05473/) (2023)
- [GraphXForm: Graph transformer for computer-aided molecular design](https://mlsanity.com/paper/2411.01667/) (2024)
- [Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematics](https://mlsanity.com/paper/2503.06366/) (2025)
- [Learning to Disprove: Formal Counterexample Generation with Large Language Models](https://mlsanity.com/paper/2603.19514/) (2026)
- [Refutation of Spectral Graph Theory Conjectures with Monte Carlo Search](https://mlsanity.com/paper/2207.03343/) (2022)
- [Neural Discovery in Mathematics: Do Machines Dream of Colored Planes?](https://mlsanity.com/paper/2501.18527/) (2025)
- [Artificial Intelligence and the Structure of Mathematics](https://mlsanity.com/paper/2604.06107/) (2026)
- [Using Reasoning Models to Generate Search Heuristics that Solve Open Instances of Combinatorial Design Problems](https://mlsanity.com/paper/2505.23881/) (2025)
- [Flow-based Extremal Mathematical Structure Discovery](https://mlsanity.com/paper/2601.18005/) (2026)
- [Can Neural Networks Learn Small Algebraic Worlds? An Investigation Into the Group-theoretic Structures Learned By Narrow Models Trained To Predict Group Operations](https://mlsanity.com/paper/2601.21150/) (2026)
- [Learning proofs for the classification of nilpotent semigroups](https://mlsanity.com/paper/2106.03015/) (2021)
- [Machine-Learning Kronecker Coefficients](https://mlsanity.com/paper/2306.04734/) (2023)
- [Adaptive Monte Carlo Search for Conjecture Refutation in Graph Theory](https://mlsanity.com/paper/2306.07956/) (2023)
- [Applying language models to algebraic topology: generating simplicial cycles using multi-labeling in Wu's formula](https://mlsanity.com/paper/2306.16951/) (2023)
- [Classification-based detection and quantification of cross-domain data bias in materials discovery](https://mlsanity.com/paper/2311.09891/) (2023)
- [A Systematization of the Wagner Framework: Graph Theory Conjectures and Reinforcement Learning](https://mlsanity.com/paper/2406.12667/) (2024)
- [Aligning AI-driven discovery with human intuition](https://mlsanity.com/paper/2410.07397/) (2024)

## Abstract (arXiv)

We demonstrate how by using a reinforcement learning algorithm, the deep cross-entropy method, one can find explicit constructions and counterexamples to several open conjectures in extremal combinatorics and graph theory. Amongst the conjectures we refute are a question of Brualdi and Cao about maximizing permanents of pattern avoiding matrices, and several problems related to the adjacency and distance eigenvalues of graphs.