A family of extremal hypergraphs for Ryser's conjecture

摘要

Ryser's Conjecture states that for any r-partite r-uniform hypergraph, the vertex cover number is at most r-1 times the matching number. This conjecture is only known to be true for r = 3 in general and for r = 5 if the hypergraph is intersecting. There has also been considerable effort made for finding hypergraphs that are extremal for Ryser's Conjecture, i.e. r-partite hypergraphs whose cover number is r-1 times its matching number. Aside from a few sporadic examples, the set of uniformities r for which Ryser's Conjecture is known to be tight is limited to those integers for which a projective plane of order r-1 exists.