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.
Preliminaries 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 ν ( H ) {\displaystyle \nu (H)} . 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 τ ( H ) {\displaystyle \tau (H)} . For every H, ν ( H ) ≤ τ ( H ) {\displaystyle \nu (H)\leq \tau (H)} , since every cover must contain at least one point from each edge in any matching. If H is r-uniform (each hyperedge has exactly r vertices), then τ ( H ) ≤ r ⋅ ν ( H ) {\displaystyle \tau (H)\leq r\cdot \nu (H)} , since the union of the edges from any maximal matching is a set of at most rv vertices that meets every edge.
The conjecture 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: τ ( H ) ≤ ( r − 1 ) ⋅ ν ( H ) {\displaystyle \tau (H)\leq (r-1)\cdot \nu (H)} I.e., the multiplicative factor in the above inequality can be decreased by 1.
Extremal hypergraphs An extremal hypergraph to Ryser's conjecture is a hypergraph in which the conjecture holds with equality, i.e., τ ( H ) = ( r − 1 ) ⋅ ν ( H ) {\displaystyle \tau (H)=(r-1)\cdot \nu (H)} . 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. It is known to exist whenever r-1 is the power of a prime integer. There are other families of such extremal hypergraphs.
Special cases In the case r=2, the hypergraph becomes a bipartite graph, and the conjecture becomes τ ( H ) ≤ ν ( H ) {\displaystyle \tau (H)\leq \nu (H)} . This is known to be true by Kőnig's theorem. In the case r=3, the conjecture has been proved by Ron Aharoni. 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: there exists some ε > 0 such that τ ( H ) ≤ ( r − ε ) ⋅ ν ( H ) {\displaystyle \tau (H)\leq (r-\varepsilon )\cdot \nu (H)} .Moreover, in the cases r=4 and r=5, Ryser's conjecture has been proved by Tuza (1978) in the special case ν ( H ) = 1 {\displaystyle \nu (H)=1} , i.e.: ν ( H ) = 1 ⟹ τ ( H ) ≤ r − 1 {\displaystyle \nu (H)=1\implies \tau (H)\leq r-1} .
Fractional variants 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 ν ∗ ( H ) {\displaystyle \nu ^{*}(H)} . 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 τ ∗ ( H ) {\displaystyle \tau ^{*}(H)} . Linear programming duality implies that ν ∗ ( H ) = τ ∗ ( H ) {\displaystyle \nu ^{*}(H)=\tau ^{*}(H)} .
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 τ ∗ ( H ) ≤ ( r − 1 ) ⋅ ν ( H ) {\displaystyle \tau ^{*}(H)\leq (r-1)\cdot \nu (H)} .Lovasz has shown that τ ( H ) ≤ r 2 ⋅ ν ∗ ( H ) {\displaystyle \tau (H)\leq {\frac {r}{2}}\cdot \nu ^{*}(H)} .
References
