Non-intersecting Ryser hypergraphs

Abstract

A famous conjecture of Ryser states that every $r$-partite hypergraph has vertex cover number at most $r-1$ times the matching number. In recent years, hypergraphs meeting this conjectured bound, known as $r$-Ryser hypergraphs, have been studied extensively. It was recently proved by Haxell, Narins and Szabó that all $3$-Ryser hypergraphs with matching number $\nu >1$ are essentially obtained by taking $\nu$ disjoint copies of intersecting $3$-Ryser hypergraphs. Abu-Khazneh showed that such a characterisation is false for $r=4$ by giving a computer generated example of a $4$-Ryser hypergraph with $\nu =2$ whose vertex set cannot be partitioned into two sets such that we have an intersecting $4$-Ryser hypergraph on each of these parts. Here we construct new infinite families of $r$-Ryser hypergraphs, for any given matching number $\nu >1$, that do not contain two vertex disjoint intersecting $r$-Ryser subhypergraphs.

8 pages, some corrections in the proof of Lemma 3.6, added more explanation in the appendix, and other minor changes