Ryser's conjecture

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 ${\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 ${\displaystyle \tau (H)}$.

For every 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 ${\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.

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:

${\displaystyle \tau (H)\leq (r-1)\cdot \nu (H)}$

I.e., the multiplicative factor in the above inequality can be decreased by 1.[2]

An extremal hypergraph to Ryser's conjecture is a hypergraph in which the conjecture holds with equality, i.e., ${\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.[3] It is known to exist whenever r-1 is the power of a prime integer.

There are other families of such extremal hypergraphs.[4]

In the case r=2, the hypergraph becomes a bipartite graph, and the conjecture becomes ${\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.[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

${\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 ${\displaystyle \nu (H)=1}$, i.e.:

${\displaystyle \nu (H)=1\implies \tau (H)\leq r-1}$.

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 ${\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 ${\displaystyle \tau ^{*}(H)}$. Linear programming duality implies that ${\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[7]

${\displaystyle \tau ^{*}(H)\leq (r-1)\cdot \nu (H)}$.

Lovasz has shown that[8]

${\displaystyle \tau (H)\leq {\frac {r}{2}}\cdot \nu ^{*}(H)}$.