Math Conjectures

Ryser's Conjecture for rr-Partite Hypergraphs

OPENMajorConjectureProposed c. 1971 · Standard version

Canonical statement

If HH is an rr-uniform rr-partite hypergraph (its vertices split into rr classes and every edge contains exactly one vertex from each class), let ν(H)\nu(H) be the largest size of a family of pairwise disjoint edges and let τ(H)\tau(H) be the smallest size of a vertex set meeting every edge. Then
τ(H)≤(r−1)ν(H). \tau(H)\leq(r-1)\nu(H).
View source LaTeX
If \(H\) is an \(r\)-uniform \(r\)-partite hypergraph
(its vertices split into \(r\) classes and every edge contains exactly one
vertex from each class), let \(\nu(H)\) be the largest size of a family
of pairwise disjoint edges and let \(\tau(H)\) be the smallest size of a
vertex set meeting every edge. Then
\[
  \tau(H)\leq(r-1)\nu(H).
\]
COMB-010:[Aharoni2001Ryser][HaxellScott2021Ryser]
Combinatorics

Notes

Let HH be an rr-uniform rr-partite hypergraph, with matching number ν(H)\nu(H) (the largest number of pairwise disjoint edges) and cover number τ(H)\tau(H) (the smallest number of vertices meeting every edge). Trivially τ≤rν\tau\le r\nu, since the vertex set of a maximum matching is a cover; Ryser's conjecture, which took shape around 1971, asserts the stronger bound τ(H)≤(r−1)ν(H)\tau(H)\le(r-1)\nu(H).

For r=2r=2 the statement is König's classical theorem on bipartite graphs, and the case r=3r=3 was proved by Aharoni using topological methods [Aharoni2001Ryser]. The bound, if true, is sharp: truncated projective planes yield rr-partite hypergraphs with τ=(r−1)ν\tau=(r-1)\nu whenever a projective plane of order r−1r-1 exists. Beyond this, the conjecture has been confirmed in important special classes, and further partial results are known [HaxellScott2021Ryser].

Strikingly, even the intersecting case ν(H)=1\nu(H)=1, where an intersecting family must be covered by r−1r-1 vertices, is unresolved for all large rr, and a proof seems to require ideas beyond the topological arguments that settled r=3r=3. For every r≥4r\ge4 the conjecture remains open in general.

References (2)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.