# RamseyRL: A Framework for Intelligent Ramsey Number Counterexample Searching

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 22 references that are in the map.
- First posted on arXiv 23 Aug 2023.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Constructions in combinatorics via neural networks](https://mlsanity.com/paper/2104.14516/) (2021)

## Abstract (arXiv)

The Ramsey number is the minimum number of nodes, n = R(s, t), such that all undirected simple graphs of order n, contain a clique of order s, or an independent set of order t. This paper explores the application of a best first search algorithm and reinforcement learning (RL) techniques to find counterexamples to specific Ramsey numbers. We incrementally improve over prior search methods such as random search by introducing a graph vectorization and deep neural network (DNN)-based heuristic, which gauge the likelihood of a graph being a counterexample. The paper also proposes algorithmic optimizations to confine a polynomial search runtime. This paper does not aim to present new counterexamples but rather introduces and evaluates a framework supporting Ramsey counterexample exploration using other heuristics. Code and methods are made available through a PyPI package and GitHub repository.