HackerPapers

arXiv:2104.14516math.CO

Constructions in combinatorics via neural networks

Adam Zsolt Wagner

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 comments
23 pages, 13 figures
Journal reference
DOI
Subjects
math.COCombinatorics cs.LGMachine Learning

On Hacker News

Linked by 3 identifiable commenters in 3 comments across 3 threads, from Jun 2021 to Mar 2022. Found in 3 HN submissions from May 2021 to Jul 2021. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments3 threads

  1. An AI has solved several open problems in combinatorics and graph theory 1 comment

    • The author does mention problems where LP solvers can be used to solve the problems instead of the neural network approach used for the others. See section 3 in https://arxiv.org/pdf/2104.14516.pdf.

      porcodaView on HNParent context

  2. How Big Data Carried Graph Theory into New Dimensions 1 comment

    • Thought that the article would be abou the quest for a better random graph model. It's weird that Quanta didn't talk about this yet. For the other direction (ML helping graph theory and not vice versa), see Constructions in Combinatorics via Neural Networks [0] by Wagner (2021).…

      dpalekaView on HNParent context

  3. AI Disproving Mathematical Conjectures 1 comment

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.