Ryser's covering conjecture
From OpenAI Aftermath
Ryser's covering conjecture predicts that every r-partite r-uniform hypergraph satisfies τ ≤ (r − 1)ν, where τ is the covering number and ν the matching number; for intersecting hypergraphs this says that r − 1 vertices always suffice to meet every edge. Two manuscripts dated 23 and 27 September 2026 in OpenAI's public mathematics collection (github.com/openai/math) claim counterexamples for infinitely many ranks, together with counterexamples to Gyárfás's monochromatic tree-cover conjecture. This page summarizes the published claims and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.
Background
- As recounted in the introduction of the balanced manuscript:
- For r = 2 the inequality is Kőnig's matching theorem. Henderson's 1971 thesis contains an equivalent formulation of the general conjecture, and Best and Wanless discuss its attribution to Ryser. Aharoni proved the tripartite case.
- In the intersecting case, Gyárfás proved the conjecture through rank four and Tuza proved rank five. For linear intersecting hypergraphs, Francetić, Herke, McKay and Wanless established it through rank nine. Haxell and Scott proved a bound τ ≤ (r − ε)ν for r = 4 and 5, and White proved τ ≤ 6 for four-partite hypergraphs with ν = 2.
- Truncated projective planes give intersecting examples with covering number r − 1, which is why the bound is natural; Abu-Khazneh, Barát, Pokrovskiy and Szabó, and Haxell and Scott, built further intersecting examples close to the bound.
- Erdős, Gyárfás and Pyber record that Gyárfás's conjecture, that the vertices of every r-edge-coloured complete graph can be covered by r − 1 monochromatic trees, is equivalent to the intersecting case of Ryser's conjecture.
The original results
- Balanced counterexamples (27 September 2026). Theorem 1.1 of Balanced counterexamples to Ryser's conjecture at prime orders states that for every sufficiently large prime q there is a finite intersecting (q + 1)-partite (q + 1)-uniform hypergraph with exactly q + 1 nonisolated vertices in each part and covering number q + 1. A corollary gives (q + 1)-edge-coloured complete graphs whose vertices require q + 1 monochromatic trees. The manuscript states that its threshold for q is not numerical.
- Method, as described: the affine-plane example is modified in every direction by merging two parallel lines and splitting two others; a probabilistic selection produces a finite configuration, and a deterministic reduction derives the hypergraph and its covering number from properties of that configuration.
- Counterexamples over extension fields (23 September 2026). A counterexample to Ryser's covering conjecture states that for every sufficiently large prime s ≡ 2 mod 3 and every sufficiently large odd n, with the threshold depending on s, there is an intersecting (sn + 1)-partite (sn + 1)-uniform hypergraph with covering number sn + 1, again with a tree-cover corollary. The balanced manuscript notes that this theorem does not assert equal part sizes.
- Sources. At commit
1581d4c: Balanced counterexamples to Ryser's conjecture at prime orders and A counterexample to Ryser's covering conjecture. - Formalization, as described by the repository. The scope note lean/docs/162.md states that the Lean formalization proves the balanced statement for every sufficiently large prime, and the extension-field statements for ranks pn + 1, that the prime threshold is existential, and that equal part sizes and numerical thresholds are not asserted for the extension-field constructions. The Comparator challenges are
BalancedRyser,RyserCoveringandRyserOddExtensions.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 23 October 2026) |
|---|---|---|---|---|
2026-10-07 (commit db0b1c7) |
mxym/math, research/ryser-rank-six (GitHub) | Reading; related work on rank six | A programme on the smallest open rank of the intersecting case, pinned to the balanced manuscript. It states a proof that every intersecting 6-partite 6-uniform hypergraph with at most 18 edges has a cover of at most 5 vertices, with exact checkers and partial Lean certificates. It notes that the manuscript's template of two split lines with four designated points per direction needs q ≥ 9 by counting affine points, and q ≥ 24 under the pairwise condition used in its selection step, so it cannot be copied at rank six. Bounded SAT searches at rank six found no counterexample. | GitHub repository. It states that no Ryser counterexample or unrestricted nonexistence theorem is claimed, and that no human peer review is claimed. |
| 2026-10-08 | MathVet (GitHub; review of openai/math, tables at repository commit bb5fdb6, 18 October 2026) |
Review (fidelity of the formal statements) | Rates this family "partial" and records sandboxed Comparator passes for BalancedRyser, RyserCovering and RyserOddExtensions. Its notes state that the balanced challenge matches the first claim verbatim, and that no challenge mentions edge-colourings or monochromatic tree covers, so the tree-cover consequence is not among the formal statements. |
MathVet states that it does not claim any theorem false and reports what was machine-checked as stated. |
| 2026-10-10 | cert-machine, openai/math lane K: runs 38017370880 for BalancedRyser and 38019899278 for RyserCovering and RyserOddExtensions | Verification (two kernels) | Records that Lean's default kernel and the nanoda kernel accept all three solutions, in 1,580 s, 213 s and 183 s. | Repository. |
| 2026-10-16 | J. Jardine, Lattice24, referee review rank_110 of the balanced manuscript in JJardine919/openai-math-audit (archived at Zenodo 10.5281/zenodo.23422995) | Review (AI-assisted audit) | Reports no gap after reading all sections. Its one minor note concerns the concentration-of-core-covers step, which rests on a stability theorem for point sets in planes of prime order quoted from Szőnyi–Weiner and Heger–Nagy; the review checked the constants but did not compare that theorem's hypotheses with the original source. | Review record. |
Notes
- The earlier results are due to the authors named in the Background section, as recounted by the manuscripts.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
