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. (Lean)

Manuscripts (2)

Balanced counterexamples to Ryser's conjecture at prime orders

September 27, 2026 · source · cite as \cite{OAI:Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders-September-27-2026}

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.

A counterexample to Ryser's covering conjecture

September 23, 2026 · source · Lean formalization available · cite as \cite{OAI:A-Counterexample-to-Rysers-Covering-Conjecture-September-23-2026}

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.

Result 162 · Combinatorics. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.