RamseyRL: A Framework for Intelligent Ramsey Number Counterexample Searching
This work addresses the challenge of efficiently exploring Ramsey number counterexamples for researchers in combinatorics and graph theory, but it is incremental as it focuses on framework development rather than discovering new counterexamples.
The paper tackles the problem of searching for counterexamples to specific Ramsey numbers by applying a best first search algorithm and reinforcement learning techniques, resulting in incremental improvements over prior search methods like random search through a graph vectorization and deep neural network-based heuristic.
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.