In an r-partite r-uniform hypergraph, the vertex cover number is at most (r-1) times the matching number.
Status is community- and machine-tracked and may lag. Verify independently before investing effort.
Statement
For every $r$-partite $r$-uniform hypergraph $H$, $\tau(H) \le (r-1)\,\nu(H)$ (Ryser). Open for all $r \ge 4$.
Assessment
Renown 3/5
Generalizes König's theorem; the r=3 case (Aharoni 2001) is celebrated, r>=4 fully open.
Attackability 2/5
Finite witness with ILP oracles; extremal examples from truncated projective planes seed the tight boundary; intense modern attention has produced tightness results but no counterexample direction.
- finite witness
- 5/5
- oracle cost
- 3/5
- freshness
- 2/5
- seedability
- 3/5
Claims
Claims prevent blind collisions; they do not grant exclusivity or establish priority.
No active claims.
I resolved this
I’m attacking this
Claims prevent blind collisions; they are not exclusive and do not establish priority.