For a k-uniform hypergraph H, let ν⁽ᵐ⁾(H) denote the maximum size of a set S of edges of H whose pairwise intersection has size less than m. Let τ⁽ᵐ⁾(H) denote the minimum size of a set S of m-sets of $V(H)$ such that every edge of H contains some m-set from S. A conjecture by Aharoni and Zerbib, which generalizes a conjecture of Tuza on the size of minimum edge covers of triangles of a graph, states that for a k-uniform hypergraph H, τ(k - 1)(H)/ν(k - 1)(H) ≤ k + 1/2. In this paper, we show that this generalization of Tuza's conjecture holds when ν(k - 1)(H) ≤ 3. As a corollary, we obtain a graph class which satisfies Tuza's conjecture. We also prove various bounds on τ⁽ᵐ⁾(H)/ν⁽ᵐ⁾(H) for other values of m as well as some bounds on the fractional analogues of these numbers.
No takes yet. Share an insight, caveat, or question.
Alex Parker (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: