2016/05/20 by Abu-Khazneh, Ahmad, Barát, János, Pokrovskiy, Alexey +1 · 1 citation
#05D15 #Combinatorics (math.CO) #FOS: Mathematics #G.2.1
paper · doi:10.48550/arxiv.1605.06361
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. We produce a new infinite family of r-uniform hypergraphs extremal to Ryser's Conjecture, which exists whenever a projective plane of order r-2 exists. Our construction is flexible enough to produce a large number of non-isomorphic extremal hypergraphs. In particular, we define what we call the \em Ryser poset of extremal intersecting r-partite r-uniform hypergraphs and show that the number of maximal and minimal elements is exponential in √(r). This provides further evidence for the difficulty of Ryser's Conjecture.