VibeMathedMath problems solved with AI
Sign in

Ryser's conjecture for four-partite hypergraphs with matching number two

Ryser's conjecture states that every rr-partite rr-uniform hypergraph HH satisfies τ(H)≤(r−1)ν(H)\tau(H) \le (r-1)\nu(H), where τ\tau is the vertex-cover number and ν\nu the matching number. It is known for r≤3r \le 3 (Aharoni) and open in general. Tuza claimed the case r=4r=4, ν=2\nu=2, giving τ≤6\tau \le 6, in an unpublished 1979 manuscript but never published a proof; the best bound in print was τ≤7\tau \le 7. Does τ≤6\tau \le 6 hold for four-partite four-uniform hypergraphs with matching number two?

Result
Proved(see note)
Status
Partial result
AI contribution
AI co-developed
Method
Argument
Field
Hypergraph covering
Posed by
Herbert J. Ryser (conjecture, via Henderson's 1971 thesis); the case $(4,2)$ was claimed without proof by Zsolt Tuza in an unpublished 1979 manuscript
Year posed
1971
Years open
55y
Solved
2026-09-13
Model
GPT-5.6 Sol; Claude Sonnet 4
Vendor
OpenAI; Anthropic
Collaborators
Patrick White
Verification
Unreviewed
Publication
Preprint
Significance
20 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Yes, τ≤6\tau \le 6, closing the case (r,ν)=(4,2)(r,\nu) = (4,2) and putting a proof behind a claim cited from Tuza's unpublished 1979 manuscript for forty-seven years. Ryser's conjecture itself remains open for r≥4r \ge 4 in general.

What the AI did

From the paper's methods section: the proof was found through four rounds of structured reasoning with GPT-5.6 Sol (model gpt-5.6-sol-pro), each round building on verified output of the previous one, with wrong turns recorded; Claude (claude-sonnet-4) served throughout in a framing and checking role.

Verification

Checked here on 22 September 2026 against arXiv:2609.14281: the abstract states τ(H)≤6\tau(H) \le 6 for four-partite four-uniform HH with ν(H)=2\nu(H)=2, confirming Tuza's 1979 claim and improving on τ≤7\tau \le 7, an integrality consequence of Haxell and Scott (2012); the ingredients named are Gyárfás's intersecting-case theorem, a projection lemma and Kőnig's matching theorem. The reference list confirms Tuza's unpublished 1979 manuscript and his 1983 Ars Combinatoria paper. Entered as Partial: one case of Ryser's conjecture, which stays open. The mathematics was not checked here; nine days old, no referee.

Source

Changelog1 change

Discussion