Constructions in combinatorics via neural networks

Adam Zsolt Wagner
4/29/2021
math.COcs.LG

Official code: zawagner22/cross-entropy-for-combinatorics (60 stars).

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.

View on arXivView PDF

Code Implementations(1)

zawagner22/cross-entropy-for-combinatoricsOfficial100%

Code accompanying the manuscript "Constructions in combinatorics via neural networks and LP solvers".

6019

Cite this paper

@article{wagner2021constructions,
  title  = {Constructions in combinatorics via neural networks},
  author = {Adam Zsolt Wagner},
  year   = {2021},
  eprint = {2104.14516},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/2104.14516}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2104.14516.svg)](https://codeofpaper.com/paper/2104.14516)

Discussion