Neuen-Grohe Problem: Isomorphism of Tournaments with Bounded VC Dimension
Among classes of tournaments for which neither hardness nor polynomial-time solvability of isomorphism was known, bounded VC dimension stood out as an open problem of Neuen and Grohe. Resolved: isomorphism of tournaments of VC dimension is decidable in time , so automorphism groups of bounded-VC tournaments are computable in polynomial time; isomorphism of tournaments of bounded chromatic number is also polynomial-time decidable.
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Graph isomorphism
- Posed by
- Daniel Neuen, Martin Grohe
- Year posed
- —
- Years open
- —
- Solved
- 2026-08-14
- Model
- Claude Sonnet 5
- Vendor
- Anthropic
- Collaborators
- Simon Rassmann, Pascal Schweitzer
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 12 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The statement of AI use names two specific steps: the proof of one preliminary lemma (the tournament VC-dimension lemma) was provided by Claude Sonnet 5, and the proof of a second bound was simplified by it. Named model-contributed lemmas inside a human-led argument.
Verification
Checked by this site on 17 August 2026 against the paper's LaTeX (arXiv:2608.14486, Rassmann-Schweitzer): the statement of AI use is verbatim, with the two lemmas identified by reference, and the abstract states the Neuen-Grohe attribution. The algorithm was not checked here. Days-old preprint, no independent review.