Constructions in combinatorics via neural networks
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.
arXiv comment23 pages, 13 figures
References in corpus (7)
- Dueling Network Architectures for Deep Reinforcement Learning
- Graph Neural Networks: A Review of Methods and Applications
- MolGAN: An implicit generative model for small molecular graphs
- NetGAN: Generating Graphs via Random Walks
- Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
- Pattern-Avoiding (0,1)-Matrices
- Exact hyperplane covers for subsets of the hypercube
Cited by in corpus (5)
- GraphXForm: Graph transformer for computer-aided molecular design
- Exact hyperplane covers for subsets of the hypercube
- Learning proofs for the classification of nilpotent semigroups
- Measuring global properties of neural generative model outputs via generating mathematical objects
- Finding counterexamples for a conjecture of Akbari, Alazemi and Andjelić