Doubly Saturated Ramsey Graphs: A Case Study in Computer-Assisted Mathematical Discovery
Ramsey-good graphs are graphs that contain neither a clique of size $s$ nor an independent set of size $t$. We study doubly saturated Ramsey-good graphs, defined as Ramsey-good graphs in which the addition or removal of any edge necessarily creates an $s$-clique or a $t$-independent set. We present a method combining SAT solving with bespoke LLM-generated code to discover infinite families of such graphs, answering a question of Grinstead and Roberts from 1982. In addition, we use LLMs to generate and formalize correctness proofs in Lean. This case study highlights the potential of integrating automated reasoning, large language models, and formal verification to accelerate mathematical discovery. We argue that such tool-driven workflows will play an increasingly central role in experimental mathematics.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Novel Paradigm for Calculating Ramsey Number via Artificial Bee Colony Algorithm
The Ramsey number is of vital importance in Ramsey's theorem. This paper proposed a novel methodology for constructing Ramsey graphs about R(3,10), which uses Artificial Bee Colony optimization(ABC) to raise the lower bo…
Exploring the Use of Shatter for AllSAT Through Ramsey-Type Problems
In the context of SAT solvers, Shatter is a popular tool for symmetry breaking on CNF formulas. Nevertheless, little has been said about its use in the context of AllSAT problems: problems where we are interested in list…
Vocal Bursts Type PredictionRamseyRL: A Framework for Intelligent Ramsey Number Counterexample Searching
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…
Reinforcement Learning (RL)Reinforced Generation of Combinatorial Structures: Ramsey Numbers
We present improved lower bounds for nine classical Ramsey numbers: $\mathbf{R}(3, 13)$ is increased from $60$ to $61$, $\mathbf{R}(3, 18)$ from $99$ to $100$, $\mathbf{R}(4, 13)$ from $138$ to $139$, $\mathbf{R}(4, 14)$…
Sustainability in the Stochastic Ramsey Model
In this paper we provide a self-contained exposition of the problem of sustaining a constant consumption level in a Ramsey model. Our focus is on the case in which the output capital-ratio is random. After a brief review…
model