Multipartite hypergraphs achieving equality in Ryser's conjecture
A famous conjecture of Ryser is that in an r-partite hypergraph the
covering number is at most r-1 times the matching number. If true,
this is known to be sharp for r for which there exists a projective
plane of order r-1. We show that the conjecture, if true, is also
sharp for the smallest previously open value, namely r=7. For r in
{6,7}, we find the minimal number f(r) of edges in an intersecting
r-partite hypergraph that has covering number at least r-1. We find
that f(r) is achieved only by linear hypergraphs for r≤5, but that
this is not the case for r in {6,7}. We also improve the general
lower bound on f(r), showing that f(r) ≥ 3.052r+O(1).
We show that a stronger form of Ryser's conjecture that was used to
prove the r=3 case fails for all r>3. We also prove a fractional
version of the following stronger form of Ryser's conjecture: in an
r-partite hypergraph there exists a set S of size at most r-1,
contained either in one side of the hypergraph or in an edge, whose
removal reduces the matching number by 1.