mlsanityData to 7 Oct 2026

Constructions in combinatorics via neural networks

arXiv 2104.14516 ↗First posted 29 Apr 2021math.CO cs.LGcited by 46

Not on the map. Why?

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.

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

Builds on

8 of 54 references.

References · 8

  1. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,704
  2. 2015Dueling Network Architectures for Deep Reinforcement Learningcited by 769
  3. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  4. 2018MolGAN: An implicit generative model for small molecular graphscited by 392
  5. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  6. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 235
  7. 2018NetGAN: Generating Graphs via Random Walkscited by 129
  8. 2020Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networkingcited by 70

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 2; 2023: 9; 2024: 11; 2025: 6; 2026: 16.

46 papers.

Sort:

By area:

  1. 2024Formal Mathematical Reasoning: A New Frontier in AIcited by 80
  2. 2022On scientific understanding with artificial intelligencecited by 68
  3. 2025ThetaEvolve: Test-time Learning on Open Problemscited by 52
  4. 2024PatternBoost: Constructions in Mathematics with a Little Help from AIcited by 32
  5. 2024Global Lyapunov functions: a long-standing open problem in mathematics, with symbolic transformerscited by 29
  6. 2023Is deep learning a useful tool for the pure mathematician?cited by 14
  7. 2024Learn from Failure: Fine-Tuning LLMs with Trial-and-Error Data for Intuitionistic Propositional Logic Provingcited by 11
  8. 2024Data for Mathematical Copilots: Better Ways of Presenting Proofs for Machine Learningcited by 11
  9. 2023Machine learning detects terminal singularitiescited by 9
  10. 2023Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Searchcited by 8
  11. 2024Can Transformers Do Enumerative Geometry?cited by 8
  12. 2026Reinforced Generation of Combinatorial Structures: Ramsey Numberscited by 8
34 more
  1. 2023Machine learning the dimension of a Fano varietycited by 7
  2. 2024GraphXForm: Graph transformer for computer-aided molecular designcited by 6
  3. 2026Autonomous Research Agents: A Survey of AI Scientists and the Verification Gapcited by 6
  4. 2025Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematicscited by 5
  5. 2022Refutation of Spectral Graph Theory Conjectures with Monte Carlo Searchcited by 4
  6. 2025Neural Discovery in Mathematics: Do Machines Dream of Colored Planes?cited by 4
  7. 2026Learning to Disprove: Formal Counterexample Generation with Large Language Modelscited by 4
  8. 2025Using Reasoning Models to Generate Search Heuristics that Solve Open Instances of Combinatorial Design Problemscited by 3
  9. 2026Flow-based Extremal Mathematical Structure Discoverycited by 3
  10. 2026Can Neural Networks Learn Small Algebraic Worlds? An Investigation Into the Group-theoretic Structures Learned By Narrow Models Trained To Predict Group Operationscited by 2
  11. 2026Artificial Intelligence and the Structure of Mathematicscited by 2
  12. 2021Learning proofs for the classification of nilpotent semigroupscited by 1
  13. 2023Machine-Learning Kronecker Coefficientscited by 1
  14. 2023Adaptive Monte Carlo Search for Conjecture Refutation in Graph Theorycited by 1
  15. 2023Applying language models to algebraic topology: generating simplicial cycles using multi-labeling in Wu's formulacited by 1
  16. 2023Classification-based detection and quantification of cross-domain data bias in materials discoverycited by 1
  17. 2024A Systematization of the Wagner Framework: Graph Theory Conjectures and Reinforcement Learningcited by 1
  18. 2024Aligning AI-driven discovery with human intuitioncited by 1
  19. 2025Three methods, one problem: Classical and AI approaches to no-three-in-linecited by 1
  20. 2026RLGT: A reinforcement learning framework for extremal graph theorycited by 1
  21. 2026Discovering a Zeta Map Algorithm on Dyck Paths via Mechanistic Interpretabilitycited by 1
  22. 2026LLM Framework for Discovering Major Mathematical Conjectures: AI's Quest for the Next Riemann Hypothesiscited by 1
  23. 2021Measuring global properties of neural generative model outputs via generating mathematical objectscited by 0
  24. 2023RamseyRL: A Framework for Intelligent Ramsey Number Counterexample Searchingcited by 0
  25. 2024Refutation of Spectral Graph Theory Conjectures with Search Algorithms)cited by 0
  26. 2024Reinforcement Learning the Chromatic Symmetric Functioncited by 0
  27. 2025Reinforcement learning for graph theory, Parallelizing Wagner's approachcited by 0
  28. 2026The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristicscited by 0
  29. 2026k-server-bench: Automating Potential Discovery for the k-Server Conjecturecited by 0
  30. 2026Mapping Uncharted Symmetries: Machine Discovery in Combinatoricscited by 0
  31. 2026Stable Menus of Public Goods: AI-Enabled Progresscited by 0
  32. 2026Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometrycited by 0
  33. 2026Generating Special Triangulations with Transformerscited by 0
  34. 2026Evolving Towards Better Codes: LLM-Guided Search for High-Distance Binary Linear Codescited by 0