Nonintersecting ryser hypergraphs

01 Pubblicazione su rivista
Bishnoi A., Pepe V.
ISSN: 0895-4801

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 proved by Haxell, Narins, and Szabó that all 3-Ryser hypergraphs with matching number v > 1 are essentially obtained by taking v disjoint copies of intersecting 3-Ryser hypergraphs. Abu-Khazneh showed that such a characterization is false for r = 4 by giving a computer generated example of a 4-Ryser hypergraph with v = 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 first infinite families of r-Ryser hypergraphs, for any fixed matching number v > 1, that are truly nonintersecting in the sense that they do not contain two vertex disjoint intersecting r-Ryser subhypergraphs.

© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma