Constructions in combinatorics via neural networks

2021/04/29 by Adam Zsolt Wagner, Wagner, Adam Zsolt · 4 voices · 7 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.48550/arxiv.2104.14516

Abstract

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.

Citations

• A proof of the Kepler conjecture
• Dueling Network Architectures for Deep Reinforcement Learning

Cited by

• Reinforced Generation of Combinatorial Structures: Ramsey Numbers
• Three methods, one problem: Classical and AI approaches to no-three-in-line
• ThetaEvolve: Test-time Learning on Open Problems
• Learning proofs for the classification of nilpotent semigroups
• GraphXForm: graph transformer for computer-aided molecular design
• Reinforcement learning for graph theory, Parallelizing Wagner's approach
• Computer-assisted graph theory: a survey

Discussions

• Constructions in Combinatorics via Neural Networks [hn, 22 points, 1 comments]
• Using Neural Networks to Refute Conjectures in Combinatorics [hn, 19 points, 0 comments]
• Constructions in Combinatorics via Neural Networks [hn, 3 points, 1 comments]
• Un récapitulatif non, mais il y a eu ce travail d'Adam Zsolt Wagner dans lequel il utilise des réseaux neuronaux pour trouver des contre-exemples en combinatoire extrémale (arxiv.org/pdf/2104.14516) [bsky, 0 points, 1 comments]

Related

• Reinforcement learning for graph theory, Parallelizing Wagner's approach
• Reinforcement learning for graph theory, I. Reimplementation of Wagner's approach
• Short proofs of some extremal results
• What makes math problems hard for reinforcement learning: a case study
• Refuting conjectures in extremal combinatorics via linear programming