Constructions in combinatorics via neural networks
This work addresses long-standing problems in combinatorics and graph theory for researchers in these fields, providing novel solutions through machine learning.
The authors tackled open conjectures in extremal combinatorics and graph theory by using a reinforcement learning algorithm, the deep cross-entropy method, to find explicit constructions and counterexamples, refuting problems such as Brualdi and Cao's question about pattern-avoiding matrices and issues with graph eigenvalues.
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.