On Ryser's conjecture for linear intersecting multipartite hypergraphs

Abstract

Ryser conjectured that tau <= (r - 1)nu for r-partite hypergraphs, where r is the covering number and v is the matching number. We prove this conjecture for r <= 9 in the special case of linear intersecting hypergraphs, in other words where every pair of lines meets in exactly one vertex. Aharoni formulated a stronger version of Ryser's conjecture which specified that each r -partite hypergraph should have a"cover of size (r - 1)nu of a particular form. We provide a counterexample to Aharoni's conjecture with r = 13 and nu = 1. We also report a number of computational results. For r = 7, we find that there is no linear intersecting hypergraph that achieves the equality tau = r - 1 in Ryser's conjecture, although non-linear examples are known. We exhibit intersecting non-linear examples achieving equality for r is an element of {9, 13, 17). Also, we find that r = 8 is the smallest value of r for which there exists a linear intersecting r-partite hypergraph that achieves tau = r - 1 and is not"isomorphic to a subhypergraph of a projective plane. Show more