Counterexamples to Ryser’s covering conjecture

The explanation

Draw a 3-by-3 grid of 9 dots that wraps around at its edges, like a clock with 3 hours. Lines run in 4 directions: across, down, and two diagonals. Each direction has 3 parallel lines, so there are 12 lines in all. Now turn each dot into a list of 4 lines: the line through it in each direction. Any two dots lie on a common line. So any two lists share an entry.

Now ask a covering question. What is the smallest set of lines that touches every list? The 3 across lines do it, because every dot sits on one of them. No 2 lines are enough. Each line holds only 3 dots, so 2 lines reach at most 6 of the 9. So the answer is 3, one less than the 4 directions.

Mathematicians call this kind of object a hypergraph. Its vertices here are the 12 lines, sorted into 4 groups called parts. Its edges are the 9 lists, and each edge takes exactly one vertex from every part. The hypergraph is intersecting: every two edges share a vertex. Its covering number is the size of the smallest vertex set that meets every edge.

Ryser's covering conjecture makes a prediction about such objects. For an intersecting hypergraph with r parts, it says the covering number is at most r − 1. The grid meets that bound exactly: 4 parts, covering number 3. The bound cannot fail by much. Any single edge meets every other edge, so it is itself a cover. The covering number therefore never exceeds r. A counterexample has to reach exactly r, the largest value possible.

Much was known before. With two parts, the bound is König's matching theorem. Henderson's 1971 thesis contains an equivalent form of the general conjecture. Aharoni proved the three-part case in 2001. In the intersecting case, Gyárfás proved it up to four parts and Tuza for five. In 2017, Francetić, Herke, McKay and Wanless reached nine parts for linear hypergraphs. Linear means any two distinct edges share exactly one vertex. Haxell and Scott built intersecting examples with covering number at least r − 4 for every large r.

The single obstacle is that a cover may mix vertices from different partsSource 1. Growing every part bigger does not stop a small mixed coverSource 2. A counterexample must defeat every mixed choice at once.

Two papers in this family build such examples, and each starts from a grid like the one above. The September 23 paper uses a grid with q = sⁿ dots per sideSource 3. Here s is a large prime leaving remainder 2 when divided by 3. The power n is a large odd number. It adds extra edges whose labels are changed in some directionsSource 4. The September 27 paper uses a grid whose side q is any large primeSource 5. In each direction it merges two parallel lines into one block and splits two others into two blocksSource 6. The count per direction becomes (q − 4) + 1 + 4 = q + 1. That is the fewest vertices per part a counterexample can haveSource 7.

Both papers end with q + 1 parts and covering number q + 1Source 5. In the small grid, 3 lines from one direction always sufficed. In these hypergraphs, no choice of q vertices covers every edge. Every cover needs as many vertices as a whole edge holds. The result holds for every q beyond some threshold, but neither paper gives a number for itSource 8,Source 9. Both papers also turn the result into coloured complete graphsSource 10. That refutes Gyárfás's tree-cover conjecture at these sizesSource 11.

How sure is this? A computer proof checker called Lean has checked formal versions of the main results. They cover the equal-part examples for every large prime q, and the examples with r = sⁿ + 1 parts. The extension-field statements do not assert equal parts, and none gives a numerical threshold. The tree-cover consequence is not in the Lean scope note. No specialist review of either paper has been published.

What it doesn't show. This does not give an explicit size at which the first counterexample appears, nor settle smaller cases.