Intersecting hypergraphs that need one more covering vertex

← All digests

Family 162 · Combinatorics
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Suppose every pair of teams shares a member. How many people must one select to meet every team? Pairwise overlap does not imply that one person belongs to all teams, but additional organization may constrain the size of a covering set.

Ryser’s covering conjecture concerns teams with one member from each of $r$ disjoint groups. It predicts a relation between the smallest set meeting all teams and the largest collection of mutually disjoint teams. In the pairwise-intersecting case, it predicts that $r-1$ people suffice.

The two manuscripts in family 162 claim examples requiring $r$, the largest possible covering number in this intersecting setting. One construction has exactly $r$ nonisolated vertices in every part. Both also yield edge-colored complete graphs requiring $r$ monochromatic trees to cover their vertices, contradicting the associated $r-1$ tree-cover prediction.

2. Background and essential definitions

A hypergraph consists of vertices and edges, where an edge is a set of vertices of any permitted size. It is $r$-uniform if every edge has exactly $r$ vertices. It is $r$-partite here if the vertices are split into $r$ disjoint parts and every edge takes exactly one vertex from each part.

A matching is a collection of pairwise disjoint edges; its maximum size is $\nu(H)$. A vertex cover meets every edge; its minimum size is $\tau(H)$. Ryser’s proposed inequality is

$$\tau(H)\le(r-1)\nu(H).$$

A nonempty hypergraph is intersecting if every two edges meet. Then $\nu(H)=1$. Any one edge is itself a cover, since it intersects every other edge, so the automatic bound is $\tau(H)\le r$. The conjecture asks to save one vertex.

A cover may draw vertices from several parts. Making every part large therefore does not establish a lower bound: there might still be a small mixed cover. Excluding all such mixed choices is the core difficulty.

The finite-plane example

Let $\mathbb F_q$ be a finite field with $q$ elements. Its affine plane has $q^2$ points and $q+1$ directions. For each direction, the $q$ parallel lines partition the plane.

Make a hypergraph part for each direction, with its lines as vertices. Every affine point gives a hyperedge consisting of the $q+1$ lines through it. Two points lie on a common line, so their hyperedges intersect. A parallel class covers all point-edges using $q$ labels. Fewer than $q$ lines cannot cover $q^2$ points, because each line has only $q$ points.

Thus this construction has $r=q+1$ and $\tau=q=r-1$: it reaches the proposed bound exactly. The new manuscripts modify this geometry to raise the cover number while keeping the same number of parts.

3. Development history and previous partial results

At $r=2$, Ryser’s inequality is Kőnig’s theorem equating matching and covering numbers in bipartite graphs. Aharoni proved the full tripartite case in 2001. Positive results for the intersecting case cover further small ranks, including rank five, and additional assumptions such as linearity—every pair of edges meeting in exactly one vertex—permit stronger ranges.

The attribution of the general conjecture has some historical subtleties. Best and Wanless document its relation to Ryser and Henderson and distinguish it from Ryser’s separate conjecture on Latin-square transversals. The covering statement here is specifically the inequality involving $\tau$ and $\nu$.

Finite projective and affine planes supplied the classical equality examples. Later constructions, including work of Abu-Khazneh, Barát, Pokrovskiy and Szabó, modified such planes to obtain further examples meeting the conjectured bound. Haxell and Scott developed both bounds for the general covering problem and large-cover intersecting constructions; see On Ryser’s conjecture.

A stronger conjecture of Lovász proposed a particular way to reduce the matching number by deleting $r-1$ vertices. Recent counterexamples to that statement do not by themselves refute Ryser’s covering inequality. The manuscripts explicitly separate those prior negative results from their claimed violation of the covering bound itself.

The graph-coloring connection was recorded by Erdős, Gyárfás and Pyber in their work on vertex coverings by monochromatic cycles and trees. It makes the intersecting hypergraph case relevant to a second familiar combinatorial problem.

4. What the new manuscripts claim

M1: balanced examples at prime orders

For every sufficiently large prime $q$, M1 claims an intersecting $(q+1)$-partite, $(q+1)$-uniform hypergraph with

$$\tau(H)=q+1, \qquad |V_1|=\cdots=|V_{q+1}|=q+1.$$

Every vertex belongs to an edge. These equal part sizes are minimal for a counterexample with covering number $r=q+1$, because each entire part is a cover. The threshold on the prime is not given numerically.

M2: examples over extension fields

M2 fixes a sufficiently large prime $s\equiv2\pmod3$. For every sufficiently large odd integer $n$, with the threshold depending on $s$, it takes $q=s^n$ and claims an intersecting hypergraph of rank $q+1$ with $\tau=q+1$.

This construction does not assert the balance property of M1. The two theorems apply to different field orders and use different geometric modifications. M2 imports three elementary estimates from M1’s appendix, rather than deriving its counterexamples from M1’s prime-order theorem.

Monochromatic tree covers

Both constructions give complete graphs with $r=q+1$ edge colors whose vertices require exactly $r$ monochromatic trees to cover. Trees may overlap, and single-vertex trees are allowed. The same lower bound holds for covers by connected monochromatic subgraphs.

This is a covering statement. Requiring the pieces to be vertex-disjoint would be a separate partition problem. The conclusion already fails with the more permissive overlapping covers.

5. Why the advance matters

Importance: 5/5. Ryser’s conjecture is a central proposed extension of bipartite matching-cover duality to hypergraphs. Failure even in the intersecting case would show that the simple relationship breaks at its most tightly constrained matching value, $\nu=1$.

The examples miss the prediction by just one vertex, but that one vertex is decisive. In this setting $r$ is the automatic upper bound, so the conjecture’s entire improvement disappears. The balanced construction additionally prevents an explanation based merely on oversized or unused parts.

The tree-cover consequence connects the obstruction to colored complete graphs. A single hypergraph construction would therefore alter two major covering problems linked by an explicit translation.

6. The main idea

Perturb the equality example carefully

Start with the affine-plane construction, where a parallel class gives an efficient cover of size $q$. To obtain a counterexample, the source must spoil every such cover without destroying the property that every pair of hyperedges intersects.

M1 modifies the line partitions in each direction. It merges two parallel lines into one block and splits two other lines into two blocks each. The net number of blocks rises from $q$ to $q+1$. On a split line, four designated points are divided into opposite pairs.

Splitting can separate points that formerly shared a line label. To compensate, merged blocks in other directions reconnect the relevant pairs. Carefully compatible choices ensure that all retained point-edges still intersect.

Force every small cover into a rigid shape

The source removes selected lines temporarily to obtain a large core. On that core, covering labels behave like ordinary lines. Its counting and stability arguments show that any attempted cover using at most $q$ labels must largely belong to one pencil.

A pencil consists of lines through a common point; parallel lines are included by treating their common point as lying at infinity in the projective completion. This rigidity drastically reduces the possibilities for a mixed cover.

Enough points remain on each relevant line to force the cover to spend most of its labels on that pencil. The special split configurations then require more additional labels than the remaining budget allows. Probabilistic selection constructs the geometric data while preserving intersection and the needed occupancy estimates. Prime-field stability is the reason M1’s statement restricts $q$ to primes.

M2 instead inserts configurations from a smaller prime field into an extension field. A nonlinear coordinate change, schematically $(x,y)\mapsto(x^3,y)$, preserves certain directional relations while disrupting others. The condition $s\equiv2\pmod3$ makes cubing a bijection on the smaller field. Incidence estimates and carefully selected placements again force small covers into pencils and make their remaining resources insufficient.

Translate a cover into a tree cover

Use the hyperedges as vertices of a complete graph. Two hyperedges intersect in at least one part; color their joining edge by one such part index. Along any path of one color, the corresponding hypergraph vertex remains the same.

Consequently each connected monochromatic subgraph identifies a vertex meeting all hyperedges represented there. A cover by $t$ monochromatic trees would produce a hypergraph cover of size at most $t$, forcing $t\ge r$. Conversely, the $r$ monochromatic stars centered at one graph vertex cover the whole complete graph, giving equality.

7. Scope, limitations, and open questions

Neither theorem gives counterexamples at every rank. M1 covers sufficiently large prime orders, while M2 covers specified sufficiently large odd prime-power orders with an ordered choice of thresholds. No smallest counterexample rank is claimed.

The statements do not contradict the established small-rank positive cases or settle additional restricted classes such as all linear intersecting hypergraphs. The new examples must be understood with their actual incidence structure.

The quantitative thresholds are nonnumerical, and the construction is not presented as a compact explicit example suitable for immediate enumeration. Finding small examples and determining which structural restrictions restore the $r-1$ bound remain natural questions.

The exact equality $\tau=r$ belongs to the intersecting examples. It does not by itself determine the optimal general replacement for Ryser’s inequality when the matching number is larger than one.

8. Sources and further reading

Theorem 1.1 of each manuscript states its field-order range and covering conclusion; Corollary 1.2 of each gives the tree-cover consequence. M1’s Sections 2–7 develop modified line partitions and prime-plane stability. M2 uses the separate small-field configuration and extension-field construction described in its introduction.

The primary historical references linked above explain attribution, partial covering results and the tree-cover connection. Wikipedia’s hypergraph and finite geometry pages provide optional background.

Source manuscripts

• M1. OpenAI, Balanced counterexamples to Ryser’s conjecture at prime orders (September 27, 2026).
• M2. OpenAI, A counterexample to Ryser’s covering conjecture (September 23, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.