# Refutation of Spectral Graph Theory Conjectures with Search Algorithms)

arXiv: https://arxiv.org/abs/2409.18626 · HTML: https://mlsanity.com/paper/2409.18626/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 4 of its 16 references that are in the map.
- First posted on arXiv 27 Sep 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 4 of 4)

- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Constructions in combinatorics via neural networks](https://mlsanity.com/paper/2104.14516/) (2021)
- [Refutation of Spectral Graph Theory Conjectures with Monte Carlo Search](https://mlsanity.com/paper/2207.03343/) (2022)
- [Solving the HP model with Nested Monte Carlo Search](https://mlsanity.com/paper/2301.09533/) (2023)

## Abstract (arXiv)

We are interested in the automatic refutation of spectral graph theory conjectures. Most existing works address this problem either with the exhaustive generation of graphs with a limited size or with deep reinforcement learning. Exhaustive generation is limited by the size of the generated graphs and deep reinforcement learning takes hours or days to refute a conjecture. We propose to use search algorithms to address these shortcomings to find potentially large counter-examples to spectral graph theory conjectures in seconds. We apply a wide range of search algorithms to a selection of conjectures from Graffiti. Out of 13 already refuted conjectures from Graffiti, our algorithms are able to refute 12 in seconds. We also refute conjecture 197 from Graffiti which was open until now.