In graph theory, Ryser's conjecture is a conjecture relating the maximum matching size and the minimum transversal size in hypergraphs.
This conjecture first appeared in 1971 in the Ph.D. thesis of J. R. Henderson, whose advisor was Herbert John Ryser.
[1] A matching in a hypergraph is a set of hyperedges such that each vertex appears in at most one of them.
The largest size of a matching in a hypergraph H is denoted by
A transversal (or vertex cover) in a hypergraph is a set of vertices such that each hyperedge contains at least one of them.
The smallest size of a transversal in a hypergraph H is denoted by
, since every cover must contain at least one point from each edge in any matching.
Ryser's conjecture is that, if H is not only r-uniform but also r-partite (i.e., its vertices can be partitioned into r sets so that every edge contains exactly one element of each set), then:
I.e., the multiplicative factor in the above inequality can be decreased by 1.
The existence of such hypergraphs show that the factor r-1 is the smallest possible.
An example of an extremal hypergraph is the truncated projective plane - the projective plane of order r-1 in which one vertex and all lines containing it is removed.
[3] It is known to exist whenever r-1 is the power of a prime integer.
[4] In the case r=2, the hypergraph becomes a bipartite graph, and the conjecture becomes
In the case r=3, the conjecture has been proved by Ron Aharoni.
[5] The proof uses the Aharoni-Haxell theorem for matching in hypergraphs.
In the cases r=4 and r=5, the following weaker version has been proved by Penny Haxell and Scott:[6] there exists some ε > 0 such that
.A fractional matching in a hypergraph is an assignment of a weight to each hyperedge such that the sum of weights near each vertex is at most one.
The largest size of a fractional matching in a hypergraph H is denoted by
A fractional transversal in a hypergraph is an assignment of a weight to each vertex such that the sum of weights in each hyperedge is at least one.
The smallest size of a fractional transversal in a hypergraph H is denoted by
Linear programming duality implies that
Furedi has proved the following fractional version of Ryser's conjecture: If H is r-partite and r-regular (each vertex appears in exactly r hyperedges), then[7]