# RamseyGadgets: A Graph Construction Dataset for LLMs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 26 references that are in the map.
- First posted on arXiv 15 Aug 2026.

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

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Gemma 4 Technical Report](https://mlsanity.com/paper/2607.02770/) (2026)
- [Large Language Models on Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2312.02783/) (2023)
- [MathConstruct: Challenging LLM Reasoning with Constructive Proofs](https://mlsanity.com/paper/2502.10197/) (2025)
- [Evaluating the Systematic Reasoning Abilities of Large Language Models through Graph Coloring](https://mlsanity.com/paper/2502.07087/) (2025)
- [Reinforced Generation of Combinatorial Structures: Ramsey Numbers](https://mlsanity.com/paper/2603.09172/) (2026)
- [New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search](https://mlsanity.com/paper/2605.01120/) (2026)

## Abstract (arXiv)

Constructing special graphs is an important task within graph theory and computer science. Many popular graph constructions are the result of a comprehensive exploration of relevant graphs and human ingenuity. Given the rise of generative AI usage in mathematics, it is natural to test whether LLMs are able to construct graphs with specified properties using their reasoning capabilities. Unfortunately, many natural graph construction problems, such as finding extremal Ramsey-good graphs (i.e., avoiding specific monochromatic subgraphs), have been explored extensively in the literature, making it difficult to ascertain whether a construction is the product of an LLM's reasoning capabilities or its recollection from training data. In this work, we introduce RamseyGadgets, a novel dataset of 70 underexplored graph construction problems that require finding Ramsey-good graphs with special properties (e.g., containing an edge with a fixed color). These problems have reasonably sized solutions (at most 10 vertices) that can be verified by SAT solvers, making them suitable for automatic evaluation. Our dataset is easily expandable, as one can simply change the monochromatic subgraphs being avoided to obtain a new set of problems. We evaluate the performance of five open-source LLMs on our dataset and report the results. Our findings show that LLMs achieve only 37.70% accuracy on the hard-tier problems in our dataset, with Gemma-4-31B achieving the highest performance out of the five. We also showcase how our dataset allows us to ascertain what kind of hints help LLMs perform better at this task.