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.
2020
Blocking sets; Extremal combinatorics; Ryser's conjecture
01 Pubblicazione su rivista::01a Articolo in rivista
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]
File allegati a questo prodotto
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1414015
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact