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.

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

 tau(H)<=6.

White (2026) reports that GPT-5.6 Sol found the projection lemma used in the proof, while Claude helped build the computational checker. The author verified the model-produced structural claims. 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