Multipartite Hypergraphs Achieving Equality in Ryser’s Conjecture

• Published in: Graphs and combinatorics 2016, Vol.32 (1), p.1-15
• Main Authors: Aharoni, Ron, Barát, János, Wanless, Ian M.
• Format: Article
• Language: English
• Subjects: Combinatorial analysis; Combinatorics; Engineering Design; Graph theory; Graphs; Lower bounds; Matching; Mathematics; Mathematics and Statistics; Original Paper; Planes; Texts
• ISSN: 0911-0119; 1435-5914
• DOI: 10.1007/s00373-015-1575-9

A famous conjecture of Ryser ( 1967 ) is that in an r -partite hypergraph the covering number is at most r - 1 times the matching number. If true, this is known to be sharp for r for which there exists a projective plane of order r - 1 . We show that the conjecture, if true, is also sharp for the smallest previously open value, namely r = 7 . For r ∈ { 6 , 7 } , we find the minimal number f ( r ) of edges in an intersecting r -partite hypergraph that has covering number at least r - 1 . We find that f ( r ) is achieved only by linear hypergraphs for r ≤ 5 , but that this is not the case for r ∈ { 6 , 7 } . We also improve the general lower bound on f ( r ) , showing that f ( r ) ≥ 3.052 r + O ( 1 ) . We show that a stronger form of Ryser’s conjecture that was used to prove the r = 3 case fails for all r > 3 . We also prove a fractional version of the following stronger form of Ryser’s conjecture: in an r -partite hypergraph there exists a set S of size at most r - 1 , contained either in one side of the hypergraph or in an edge, whose removal reduces the matching number by 1.