Ryser’s hypergraph conjecture

Choose triples, each containing one item from each of three groups A, B and C. Consider A1–B1–C1, A1–B2–C2, A2–B1–C2 and A2–B2–C1. Every two share an item, but no item belongs to all four. Only one triple can be chosen without overlaps; two items, A1 and A2, meet them all. For any number r of groups, at least two, can all allowed choices be met by at most r−1 times as many items as can be chosen without sharing any item?[1]

How does separating vertices into groups constrain the difference between independent choices and a set meeting every choice? Take three parts $\{a_1,a_2\}$, $\{b_1,b_2\}$, $\{c_1,c_2\}$, with edges $a_1b_1c_1$, $a_1b_2c_2$, $a_2b_1c_2$, $a_2b_2c_1$. Every pair intersects, so the matching number is one; no vertex meets every edge, but $\{a_1,a_2\}$ does, so the cover number is two.

For any finite r-partite r-uniform hypergraph $H$, each edge contains one vertex from each of $r\geq2$ parts. Let $\nu(H)$ be the maximum number of vertex-disjoint edges and $\tau(H)$ the minimum size of a vertex cover, a set of vertices meeting all edges. Is $\tau(H)\leq(r-1)\nu(H)$?[1] [2]

With two groups, the maximum number of disjoint pairs equals the minimum number of items meeting all pairs. The three-group bound is also established. The 2026 preprint reports a four-group case with matching size two; arbitrary larger numbers of groups and arbitrary matching sizes remain outside these results.[1] [2]

For two parts, König’s matching–cover theorem gives equality; the three-part bound is known. The September preprint reports the restricted pair r=4 and ν=2. The target still allows every number of parts and every matching size, so that result cannot be substituted for the full inequality.[1] [2]

For pairs between two groups, independent choices and the smallest set of blockers have equal size. With triples, different choices can overlap in different places, as the four-triple example shows. The problem studies how grouping the items still controls the gap between making independent multiway choices and blocking every choice.[1]

Matching–cover equality for bipartite graphs is a min–max principle: one kind of independent selection exactly measures the smallest obstruction to all selections. Multiway edges can meet one another at different coordinates and lose that equality. Ryser’s conjecture seeks the remaining control supplied by the partition into parts. This is an extension of a structural duality, rather than an assumption that each extra group behaves like another ordinary graph.[1] [2]