Covers in partitioned intersecting hypergraphs. (January 2016) - Aharoni, Ron; Argue, C.J.
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 ) .