TOPICS
Search

Ryser's Conjecture

Ryser's conjecture (Tuza 1983) states that every r-partite r-uniform hypergraph H satisfies

tau(H)<=(r-1)nu(H),

where tau(H) is the vertex cover number and nu(H) is the matching number of the hypergraph. The bound is known for r<=3, but the conjecture remains open in general for r>=4.

White (2026) proved the previously open case r=4 and nu(H)=2, namely

tau(H)<=6.

White (2026) reports that the proof was co-developed through four rounds with GPT-5.6 Sol and checked with Claude, while he supplied the exact computations and final verification. As of Sep. 22, 2026, independent specialist review had not been reported.

See also

Hypergraph, Matching Number, Vertex Cover Number

Explore with Wolfram|Alpha

References

Aharoni, R. "Ryser's Conjecture for Tripartite Hypergraphs." Combinatorica 21, 1-4, 2001. https://doi.org/10.1007/s004930170001.Tuza, Z. "Ryser's Conjecture on Transversals of r-Partite Hypergraphs." Ars Combin. 16B, 201-209, 1983.White, P. "Tuza's Ryser-Conjecture Claim for Four-Partite Hypergraphs with Matching Number Two." 13 Sep 2026. https://arxiv.org/abs/2609.14281.

Cite this as:

Weisstein, Eric W. "Ryser's Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RysersConjecture.html

Subject classifications