Ryser's conjecture, in graph theory, relates the maximum matching size and the minimum transversal size in hypergraphs. It first appeared in 1971 in the doctoral thesis of J. R. Henderson, whose advisor was Herbert John Ryser.
Facts
Proposed Year Progress Toward ResolutionProved for 3-partite hypergraphs (r=3) by Ron Aharoni using the Aharoni-Haxell theorem; the case r=2 is Konig's theorem; open for r of 4 or more in general. 1 Classification
Resolution Status Prize Status
Prize Status (category) Connections
In Branch
Source Ryser's Conjecture (Wikipedia)
Sources
1. Ryser's Conjecture (Wikipedia)
Lead section
first appeared in 1971 in the Ph.D. thesis of J. R. Henderson, whose advisor was Herbert John Ryser.
Special cases
The conjecture has been proved by Ron Aharoni.
In Branch: Graph Theory, Lead sentence
In graph theory, Ryser's conjecture is a conjecture relating the maximum matching size and the minimum transversal size in hypergr
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.