Reinforcement learning for extremal combinatorics and graph theory

Constructions in combinatorics via neural networks

In this paper, we show how by using a reinforcement learning algorithm, the deepcross-entropy method, one can find explicit constructions and counterexamplesto 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.