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.
Nonintersecting ryser hypergraphs / Bishnoi, A.; Pepe, V.. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - 34:1(2020), pp. 230-240. [10.1137/19M1241556]
Nonintersecting ryser hypergraphs
Pepe V.
2020
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 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.File | Dimensione | Formato | |
---|---|---|---|
Bishnoi_Nonintersectingryser_2020.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
316.03 kB
Formato
Adobe PDF
|
316.03 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.