Article ID Journal Published Year Pages File Type
6424054 European Journal of Combinatorics 2016 5 Pages PDF
Abstract

Given an integer r and a vector a→=(a1,…,ap) of positive numbers with ∑i⩽pai=r, an r-uniform hypergraph H is said to be a→-partitioned if V(H)=⋃i⩽pVi, where the sets Vi are disjoint, and |e∩Vi|=ai 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).

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,