Browse › Combinatorics › 162 Counterexamples to Ryser’s covering conjecture
Balanced counterexamples to Ryser's conjecture at prime orders
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 q, we construct a finite intersecting $(q+1)$-partite $(q+1)$-uniform hypergraph with covering number $q+1$ and exactly $q+1$ nonisolated vertices in each part. This disproves Ryser's covering conjecture, even for intersecting hypergraphs with equally sized parts.
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.
Comments and discussion
- queelius, openai-math-counterexamples (GitHub repository, accessed 2026-10-21). This project, which recomputes explicit counterexamples from the release, classifies family 162 as "not-explicit": it notes that $q_0$ is not given and the hypergraph comes from a random procedure, and it lists the smallest case $q=5$ as not attempted. [AI-generated per source]
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 proves this paper's balanced theorem: for every sufficiently large prime $q$, there is an intersecting $(q+1)$-partite hypergraph with $\tau=q+1$ and exactly $q+1$ nonisolated vertices per part, with an existential threshold (comparator
BalancedRyser.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 is equivalent to Milićević's bounded-diameter strengthening, which connects to the paper's Corollary 1.2 on monochromatic tree covers at ranks $q+1$.
- 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
- Emergent Mind: family 162
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders-September-27-2026,
author = {{OpenAI}},
title = {{Balanced counterexamples to Ryser's conjecture at prime orders}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders-September-27-2026/paper.pdf}{OAI:Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders-September-27-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:
- A counterexample to Ryser's covering conjecture · September 23, 2026