Browse › Combinatorics › 162 Counterexamples to Ryser’s covering conjecture
A counterexample to Ryser's covering conjecture
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
For every sufficiently large prime $s\equiv2\pmod3$ and every sufficiently large odd integer n, with the threshold depending on s, we construct an intersecting $(s^n+1)$-partite $(s^n+1)$-uniform hypergraph with covering number $s^n+1$. This disproves Ryser's covering conjecture in its intersecting case.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI math release, Counterexamples to Ryser's covering conjecture: Lean formalization scope (lean/docs/162.md, 6 October 2026). The release's scope note states that the formalization covers ranks $r=p^n+1$, including every sufficiently large prime $p\equiv2\pmod3$ with every sufficiently large odd $n$ (comparator
RyserOddExtensions.lean), and a fixed-prime variant with prime degrees $n$ (comparatorRyserCovering.lean). [family-level] - Kenta Kitamura (KitaKen1), Formalize Ryser's conjecture and mark r = 4, ν ≤ 3 as solved (google-deepmind/formal-conjectures PR #6812, opened 2026-10-03). This open PR states Ryser's conjecture in Lean and marks the general statement as
research open; it predates the release and does not refer to these counterexamples. [family-level]
Possibly relevant literature (found by the agent, not checked)
- Alexey Pokrovskiy, Bounded diameter monochromatic component covers (arXiv:2507.05842, v2 2026-01-06). The abstract says that Gyárfás's tree-cover conjecture and Milićević's bounded-diameter strengthening are equivalent, which bears on the paper's statement that Corollary 1.2 also refutes Milićević's Conjecture 6.
- Matija Bucić, Dániel Korándi, Benny Sudakov, Covering graphs by monochromatic trees and Helly-type results for hypergraphs (arXiv:1902.05055, 2019). This paper studies monochromatic tree covers of $r$-edge-coloured graphs through hypergraph covering questions, the same correspondence that the paper's tree-cover corollary uses.
Digests and expositions
- Latent Seminar, Intersecting hypergraphs and Ryser covering counterexamples (7 October 2026). Explains both affine-plane constructions, the obstruction to small covers and the monochromatic-tree consequence; the page states that it reviews statements and selected proof mechanisms rather than complete proofs. [family-level]
- AI Proved What?, Ryser disproved? Counterexamples to Ryser’s covering conjecture and Gyárfás’s tree-cover conjecture (episode 162, October 2026). An animated exposition with transcript distinguishing the two constructions, their asymptotic existence claims and tree-cover consequences, and describing the formalization scope without rebuilding the Lean development. [AI-generated per source] [family-level]
News and blogs
- Gil Kalai, Updates: Sharing AI progress on mathematics (amazing!); and my lecture plans (Combinatorics and more, 2026-10-07). Item 11 of the post describes the new counterexamples as intersecting $r$-partite $r$-uniform hypergraphs "requiring r vertices to meet every edge" and refers to Kalai's earlier post on Aharoni's tripartite proof. [family-level]
Elsewhere
- VibeMathed: Problem record
- VibeMathed: Problem record
- Emergent Mind: family 162
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:A-Counterexample-to-Rysers-Covering-Conjecture-September-23-2026,
author = {{OpenAI}},
title = {{A counterexample to Ryser's covering conjecture}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-Counterexample-to-Rysers-Covering-Conjecture-September-23-2026/paper.pdf}{OAI:A-Counterexample-to-Rysers-Covering-Conjecture-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/162.md. The Lean statements have not been checked by people against the paper's claims.
Family 162: Counterexamples to Ryser’s covering conjecture
Disproves Ryser's covering conjecture by constructing intersecting $(q+1)$-partite, $(q+1)$-uniform hypergraphs with covering number $q+1$, rather than the predicted bound q, for every sufficiently large prime q. A separate construction over extension fields also disproves Gyárfás's monochromatic tree-cover conjecture.
Other papers in this family:
- Balanced counterexamples to Ryser's conjecture at prime orders · September 27, 2026