∑math20

Combinatorics · Result 162

Counterexamples to Ryser’s covering conjecture

2 papersLean

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.

Watch

▶Introduction: the problem and why it mattersin preparation
▶The presented solutionin preparation

Papers 2

First page of Balanced counterexamples to Ryser's conjecture at prime orders

Balanced counterexamples to Ryser's conjecture at prime orders

OpenAI · 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.

Read PDF Download Source

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}
}
First page of A counterexample to Ryser's covering conjecture

A counterexample to Ryser's covering conjecture

OpenAI · 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.

Read PDF Download Source

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}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

Scope

Ryser's covering conjecture predicts that an intersecting \(r\)-partite hypergraph has a vertex cover of size at most \(r-1\). The formalization proves that every sufficiently large prime \(q\) has a finite intersecting \((q+1)\)-partite, \((q+1)\)-uniform hypergraph with covering number \(q+1\) and exactly \(q+1\) nonisolated vertices in each part. Thus the conjecture fails even with equal part sizes. The prime threshold is existential.

Ryser's covering conjecture predicts \(\tau\le(r-1)\nu\) for an \(r\)-partite hypergraph, where \(\tau\) and \(\nu\) are its covering and matching numbers. The formalized constructions give finite intersecting \(r\)-partite \(r\)-uniform hypergraphs with \(\nu=1\) and \(\tau=r\), contradicting the bound. The ranks have the form \(r=p^n+1\): one fixed prime \(p\equiv2\pmod3\) works for all sufficiently large prime degrees \(n\), and a second result covers every sufficiently large such prime \(p\) and every sufficiently large odd \(n\), with the degree threshold allowed to depend on \(p\). Infinitely many ranks occur. Equal part sizes and numerical thresholds are not asserted.

Comparator links

ResultComparator statement
Balanced Ryser counterexamples at prime ordersBalancedRyser.lean
Fixed-prime Ryser counterexamplesRyserCovering.lean
Counterexamples in odd extension degreesRyserOddExtensions.lean

Scope note on GitHub →