Covers in partitioned intersecting hypergraphs. (January 2016)

• Record Type: Journal Article
• Authors: Aharoni, Ron; Argue, C.J.
• Is Part Of: European journal of combinatorics. Volume 51(2016:Jan.)
• Page Start: 222
• Page End: 226
• Publication Date: 2016-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2015.05.005
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: Given an integer r and a vector a → = ( a 1, …, a p ) of positive numbers with ∑ i ⩽ p a i = r, an r -uniform hypergraph H is said to be a → - partitioned if V ( H ) = ⋃ i ⩽ p V i, where the sets V i are disjoint, and | e ∩ V i | = a i for all e ∈ H, i ⩽ p . A 1 → -partitioned hypergraph is said to be r - partite . Let t ( a → ) be the maximum, over all intersecting a → -partitioned hypergraphs H, of the minimal size of a cover of H . A famous conjecture of Ryser is that t ( 1 → ) ⩽ r − 1 . Tuza (1983) conjectured that if r > 2 then t ( a → ) = r for every two components vector a → = ( a, b ) . We prove this conjecture whenever a ≠ b, and also for a → = ( 2, 2 ) and a → = ( 4, 4 ) .