Covers in Partitioned Intersecting Hypergraphs

Original · EN

Given an integer r and a vector a=(a₁,,aₚ) of positive numbers with ∑ᵢ ≤ ₚ aᵢ=r, an r-uniform hypergraph H is said to be a-partitioned if V(H)=ᵢ ≤ ₚVᵢ, where the sets Vᵢ are disjoint, and |e ∩ Vᵢ|=aᵢ 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 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).