Counterexamples to Ryser’s covering conjecture

1 · The essentials

Imagine a collection of groups of objects in which any two groups share at least one object. A cover is a selection of objects that meets every group. The question is how many objects such a selection must contain when the objects are divided into separate classes and each group takes exactly one object from each class. In this setting, Ryser’s covering conjecture predicts that one fewer than the number of classes should suffice. The main manuscript presents examples where that prediction fails: with $q + 1$ classes, the smallest cover needs $q + 1$ objects, for every sufficiently large prime $q$ . These examples also have exactly the same number of participating objects in each class. A companion manuscript has a Lean formalization of counterexamples under a different set of numerical conditions.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine committees that each contain one person from every department, with any two committees sharing someone. Selecting people so that every committee has a selected member resembles finding a cover; the reported examples require as many selected people as there are departments, despite all the pairwise overlap.

Why it matters

The results contradict the predicted covering bound even when every pair of edges intersects. The main manuscript adds that equal-sized participating parts do not restore the bound. The Lean-formalized companion provides formal verification for a specified family of counterexamples, not automatically for every construction described in the source.

2 · Going further

A hypergraph consists of vertices and edges, where an edge is a set of vertices. Here the hypergraphs are intersecting, meaning any two edges share a vertex, and are $r$ -partite and $r$ -uniform: the vertices are divided into $r$ parts, and every edge contains exactly one vertex from each part. The covering number $τ (H)$ is the smallest number of vertices meeting every edge. In this intersecting setting, the conjectured bound is $τ (H) \leq r - 1$ .

The main manuscript shows that, for every sufficiently large prime $q$ , there is a finite hypergraph of this kind with $r = q + 1$ and $τ (H) = q + 1$ . It also specifies exactly $q + 1$ nonisolated vertices in each part, so the vertices that actually occur in edges are equally distributed across the parts. The argument is constructive according to the abstract, but the supplied text gives neither the construction’s ingredients nor the steps establishing its covering number.

The Lean-formalized companion treats a different parameter family. For every sufficiently large prime $s \equiv 2 (mod 3)$ and every sufficiently large odd integer $n$ , with the threshold for $n$ depending on $s$ , it constructs an intersecting $(s^{n} + 1)$ -partite, $(s^{n} + 1)$ -uniform hypergraph with covering number $s^{n} + 1$ . Thus both manuscripts contradict the same intersecting-case bound, while their stated parameter ranges and balance guarantees differ. The repository summary also reports a separate extension-field construction contradicting Gyárfás’s monochromatic tree-cover conjecture, but supplies no abstract or construction details for that claim.

Useful notions

Sets and their intersections
Prime numbers and congruences
Hypergraphs and vertex partitions
Minimum-size covers

What was known before / what is new

Before

The source identifies Ryser’s covering conjecture as predicting a cover of size at most $q$ for the intersecting $(q + 1)$ -partite, $(q + 1)$ -uniform setting under discussion. It provides no account of earlier partial results or the historical development of that conjecture.

New

The main manuscript shows counterexamples for every sufficiently large prime $q$ , with covering number $q + 1$ and exactly $q + 1$ nonisolated vertices per part. The Lean-formalized companion supplies counterexamples with $s^{n} + 1$ parts under its stated congruence and size conditions. The repository summary separately reports counterexamples to Gyárfás’s monochromatic tree-cover conjecture via an extension-field construction.

Limits and assumptions

The prime-order result requires sufficiently large primes; no explicit threshold is supplied. The Lean-formalized companion requires sufficiently large primes $s \equiv 2 (mod 3)$ and sufficiently large odd $n$ , with an $s$ -dependent threshold. The supplied verification designation applies to that companion’s counterexample result, not to the main manuscript’s balanced prime-order claim or the separate tree-cover claim. The abstracts do not give construction details, and they do not state what happens for excluded or smaller parameters or identify further open questions.

Mini glossary

Hypergraph: A collection of vertices together with edges, each of which is a set of vertices.
Intersecting: A hypergraph is intersecting when every pair of edges shares at least one vertex.
$r$ -partite and $r$ -uniform: The vertices are divided into $r$ parts, and each edge contains exactly one vertex from each part.
Covering number: The smallest size of a set of vertices that meets every edge.
Nonisolated vertex: A vertex that belongs to at least one edge.

Keywords : Ryser’s covering conjecture · Intersecting hypergraphs · Covering number

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

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.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/162.md

Manuscripts in this family

★

Balanced counterexamples to Ryser's conjecture at prime orders

27/09/2026

To be verified

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.

PDF GitHub folder

A counterexample to Ryser's covering conjecture

23/09/2026

Verified by Lean

For every sufficiently large prime $s \equiv 2 (mod 3)$ 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.

PDF GitHub folder Lean formalization