---
id: "2021-04-29-wagner-rl-counterexamples"
url: "https://postcutoff.com/e/2021-04-29-wagner-rl-counterexamples/"
as_of: "2026-11-13T13:49:00+01:00"
date: "2021-04-29"
date_precision: day
category: science
importance: 2
confidence: high
status: [Result confirmed]
verification: Preprint only
sources: 2
editor: human editor
human_review: null
version: "2026-10-04"
---

As of: 2026-11-13 13:49 CET.
Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/
Canonical page: https://postcutoff.com/e/2021-04-29-wagner-rl-counterexamples/

# Adam Zsolt Wagner uses reinforcement learning to find counterexamples to open graph-theory conjectures

Wagner's 'Constructions in combinatorics via neural networks' (arXiv 2104.14516) used a simple cross-entropy RL method to find explicit counterexamples to several published conjectures in extremal combinatorics and spectral graph theory.

## Key facts
- arXiv 2104.14516 (29 Apr 2021)
- Refuted several conjectures about graph eigenvalues and a Brualdi–Cao question on permanents of pattern-avoiding matrices
- Small neural network plus deep cross-entropy method; no LLM
- Wagner later joined Google DeepMind and co-authored the 2025 AlphaEvolve maths paper with Tao

## What happened

A lone mathematician showed that off-the-shelf RL could disprove conjectures by searching for graphs that violate them.

## Why it matters

It was the template for the 2023–2026 wave of AI counterexample finding (FunSearch, AlphaEvolve, PatternBoost, LLM counterexamples).

## Your AI and this story

- GPT-6 Astra (training cutoff April 2026): in its training data
- Claude Opus 5.5 (training cutoff June 2026): in its training data
- Gemini 4 Hydrogen (training cutoff March 2026): in its training data
- Grok 4.7 (training cutoff May 2026): in its training data

## Sources

1. [Constructions in combinatorics via neural networks (arXiv 2104.14516)](https://arxiv.org/abs/2104.14516) (arxiv.org, paper)
2. [Reimplementation and extension (arXiv 2403.18429)](https://arxiv.org/abs/2403.18429) (arxiv.org, paper)

## Changes

- 2026-09-29 (filed): Created

## Related

- 2025-11-05: [Tao, Gómez-Serrano, Georgiev and Wagner test AlphaEvolve on 67 maths problems](https://postcutoff.com/e/2025-11-05-alphaevolve-tao-67-problems/index.md)