Intersecting hypergraphs and Ryser covering counterexamples

Source and verification

This article explains family 162 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Matching and covering in multipartite hypergraphs

A hypergraph has vertices and edges that are subsets of its vertex set. It is $r$-uniform if each edge has exactly $r$ vertices, and $r$-partite if the vertices are partitioned into $r$ parts with each edge meeting each part once. Its matching number $\nu$ is the maximum number of pairwise disjoint edges. Its covering number $\tau$ is the minimum number of vertices meeting every edge.

An intersecting hypergraph has $\nu =1$: every two edges meet. In that case any one edge is itself a cover, so $\tau \le r$. Ryser’s covering conjecture proposes the stronger inequality $\tau \le (r-1)\nu$, which would give $\tau \le r-1$ for intersecting $r$-partite hypergraphs.

This is the hypergraph covering conjecture; it is distinct from conjectures about transversals in Latin squares that also bear Ryser’s name.

Manuscript claims

For every sufficiently large prime $q$, there is an intersecting $(q+1)$-partite, $(q+1)$-uniform hypergraph with $\tau =q+1$ and exactly $q+1$ nonisolated vertices in each part. (OpenAI, 2026)

A companion construction gives counterexamples at ranks $q+1$ with $q=s^n$, where $s$ is any sufficiently large prime congruent to $2$ modulo $3$ and $n$ is any sufficiently large odd integer, with its threshold allowed to depend on $s$. Equal part sizes are not asserted for this construction. (OpenAI, 2026a)

Both conclusions attain the largest possible cover number for an intersecting uniform hypergraph. Neither supplies a numerical threshold in the statement used here.

🏷️ The affine-plane starting point

An affine plane over a field with $q$ elements has $q^2$ points and $q+1$ directions. In each direction, its $q$ parallel lines partition the points. Make one hypergraph part for each direction, one vertex for each line, and one hyperedge for each point, consisting of all lines through that point.

Every hyperedge has one vertex in every part. Two point-edges meet because two points lie on a common line. The hypergraph is therefore intersecting. Its cover number is exactly $q$: a parallel class covers every point, while $q-1$ lines cover at most $(q-1)q<q^2$ points.

This starting example reaches $r-1$ for $r=q+1$. A counterexample must increase the cover number by one while preserving the property that every pair of point-edges intersects.

🏷️ Merging and splitting line blocks

The balanced construction modifies the partitions of the point set. In each direction, it merges two line blocks, decreasing the number of blocks by one, and splits two other lines into two blocks each, increasing it by two. The net result is $q+1$ blocks in that direction, hence the desired balanced part size.

Splitting a line can destroy the common vertex that previously joined two point-edges. The construction chooses four marked points on each split line and arranges pairs of them across the two pieces. The pairs whose original intersection is lost are rescued by merged blocks in other directions. This local repair is what preserves the intersecting property.

The cover argument goes in the opposite direction. A hypothetical cover with only $q$ blocks would induce an almost-cover of the original affine plane by lines. A stability estimate forces such an almost-cover to resemble a pencil, a collection of lines through one point. Occupancy constraints then require too many nonsplit pencil lines, leaving an insufficient budget to cover the marked points created by the splitting gadgets.

The gadget choices are coupled. The paper uses a random independent transversal, meaning one compatible choice from each of several classes, and proves upper bounds on the probability of prescribed simultaneous choices. It does not assume those choices are independent. A very small tail probability for a failed cover, of scale $\exp (-\Omega (q\log q))$, is needed to absorb the number of potential covers and the cost of changing the sampling law.

🏷️ Odd extension degrees

The companion uses finite planes over $q=s^n$ but builds compatible gadgets from a smaller field. When $s\equiv 2(\mathrm{mod}3)$, cubing is a permutation of that smaller field, so the coordinate map $(x,y)\mapsto (x^3,y)$ provides nonlinear configurations with controlled incidences.

Oddness of $n$ has a separate role. A proper subfield of a field of order $s^n$ then has size at most $q^{1/3}$. This prevents a large proper subfield from carrying an uncontrolled concentration of the construction. Incidence bounds distinguish line-like and nonlinear configurations, while compatible translated gadgets are again selected through a transversal argument.

The deletion pool is fixed before the final selection. That order preserves the monotonicity needed when proving that selected gadgets cannot accidentally create a cheap cover. The extension-degree theorem is a separate construction, not an automatic replacement of a prime by an arbitrary prime power in the balanced theorem.

🏷️ A colored-tree consequence

There is a useful translation back to ordinary graphs. Make a complete graph whose vertices are the hyperedges. Color each pair by a part in which the corresponding hyperedges intersect, choosing one if several are available.

A connected monochromatic subgraph has a common hypergraph vertex. Indeed, along a path of edges colored by part $i$, consecutive hyperedges share their unique vertex in part $i$, so that vertex remains the same throughout the path. Covering the complete graph by $t$ monochromatic connected subgraphs would therefore give a hypergraph vertex cover of size at most $t$.

Thus the proposed examples require at least $r$ monochromatic connected pieces. The elementary upper bound is $r$ stars centered at a fixed graph vertex, one for each color. This concerns covers, where pieces may overlap, and should not be silently strengthened to a partition into disjoint trees.

🏷️ Key steps and proof outlines

Encode covers as selections from balanced partitions

The prime-order construction starts with the affine plane of order $q$, whose $q+1$ directions each partition the plane into $q$ parallel lines. In every direction, two lines are merged into one block and two other lines are split into two blocks each. Each split line retains four designated points, divided into the opposite pairs of a four-cycle. The number of resulting blocks is

$$(q-4)+1+4=q+1.$$

Let $X$ be the retained point set. Give each block its own vertex label, with separate label sets for separate directions. A point $x\in X$ defines a hyperedge containing the unique block label containing it in every direction. Every edge consequently has one vertex in each of $q+1$ parts, and every part has $q+1$ vertices. The source’s occupancy conditions ensure no block is empty. (OpenAI, 2026b)

Why the edges intersect. Two points lie on a unique joining line. Unless that line was split, they share its ordinary or merged label. On a split line, they either belong to the same opposite pair or are consecutive in the designated four-cycle. In the latter case the construction provides another direction whose merged block contains both. Thus the split operation’s lost intersections are explicitly repaired.

A vertex cover of the hypergraph is exactly a collection of blocks covering $X$. Selecting a whole part gives a cover of size $q+1$; the substantive task is to exclude $q$ blocks.

First force a hypothetical small cover near one pencil

The source uses two retained core sets, $R_0\subseteq R\subseteq X$. Split blocks miss $R_0$. A merged block restricted to $R_0$ agrees with one designated constituent line, because its other constituent was removed from that core. Replace each selected nonsplit block by this representative line.

The core-cover concentration statement says that any such collection of at most $q$ lines covering $R_0$ has at least $(1-\rho /4)q$ representatives through one projective point $P$. Here $\rho >0$ is the occupancy parameter. Thus at most

$$t\le \rho q/4$$

selected labels lie outside that pencil, counting split labels among the exceptions. A projective point at infinity means a parallel pencil; an affine point means concurrent lines. This structural input is furnished by the manuscript’s selection and deletion arguments.

Occupancy turns approximate concentration into forced labels

If $P$ is at infinity, every one of the $q-3$ available parallel representative lines must be selected. Otherwise the omitted line contains at least $\rho q$ points of $R_0$, while all exceptional representatives together cover at most $t<\rho q$ of them. The forced $q-3$ blocks miss the eight designated points on the two split lines of that direction. Compatibility ensures that any further block covers at most two of those eight points. Only three labels remain, so they cannot finish the cover.

For an affine center $p$, the same argument forces the block corresponding to every nonsplit line through $p$. For an ordinary representative line, the other pencil lines cover at most $p$ itself and the exceptional lines at most $t$ further points, contradicting $\rho q>1+t$ if its label is absent.

A removed constituent requires the larger core $R$. Let $B$ bound how many merged constituents can pass through one point. If its merged label is absent, pencil blocks cover at most $1+B$ points on the omitted line: one common center plus one point from each possible partner line. Exceptional blocks cover at most $2t$ further points. The source chooses parameters so that

$$\rho q\le |\ell \cap R|\le 1+B+2t\le 1+B+\rho q/2<\rho q,$$

again a contradiction. This is why a single core set is insufficient: representative-line concentration and partner-line occupancy solve distinct problems.

Spend the remaining budget on designated points

Let $b$ be the number of split lines through $p$. The nonsplit directions force $q+1-b$ labels, leaving only $b-1$ additional labels. If $b=0$, the budget is already exceeded. If $b=1$, no label remains, and the four-cycle compatibility leaves a designated point uncovered.

For $b\ge 2$, the $b$ split lines have disjoint designated sets containing $4b$ points in total. The already forced merged blocks cover at most one designated point per split line, hence at most $b$ altogether. When $b=2$, the single remaining block covers at most four more points, and $2+4<8$. For $b\ge 3$, the manuscript’s local exclusion condition rules out covering the designated points by the forced partner contributions plus any $b-1$ allowed extra blocks. The selection theorem is designed to establish precisely this finite obstruction, rather than merely generic position.

The companion manuscript uses related split-and-merge geometry at suitable prime-power orders, with an auxiliary subfield supplying its structured configuration. That arithmetic mechanism differs from the prime-order selection and deletion argument above. Both feed the same partition-to-hypergraph conversion and exact cover-budget contradiction. (OpenAI, 2026a)

See Also

• Sidorenko counterexamples uses an incidence graph to transform a triple system into a graph-density obstruction.
• Off-diagonal Ramsey numbers uses finite geometric incidences for a different purpose: constructing clique-free graphs with small independent sets.

🏷️ Manuscripts and verification scope

• Balanced counterexamples to Ryser’s conjecture at prime orders — pinned manuscript and companion source.
• A counterexample to Ryser’s covering conjecture — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page distinguishes balanced prime-order examples from fixed-prime and odd-extension examples. Only the first selection asserts equal part sizes. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. A counterexample to Ryser’s covering conjecture.

🐻  OpenAI 2026b. Balanced counterexamples to Ryser’s conjecture at prime orders.