Ryser's conjecture

Nonintersecting ryser hypergraphs

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.

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