Constructions in combinatorics via neural networks
2021-04-29Code Available1· sign in to hype
Adam Zsolt Wagner
Code Available — Be the first to reproduce this paper.
ReproduceCode
- github.com/zawagner22/cross-entropy-for-combinatoricsOfficialIn papertf★ 57
- github.com/dpaleka/cross-entropy-for-combinatoricspytorch★ 19
- github.com/ponyfat/graph-conjectures-counterexaplespytorch★ 2
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.