2024/06/10 by Alex Parker, Parker, Alex
Mathematics · #Mathematical Inequalities and Applications #Advanced Mathematical Theories #Advanced Mathematical Identities
paper · pdf · doi:10.48550/arxiv.2406.06501
For a k-uniform hypergraph H, let ν(m)(H) denote the maximum size of a set S of edges of H whose pairwise intersection has size less than m. Let τ(m)(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) ≤ \lceil (k + 1)/(2) \rceil. 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 τ(m)(H)/ν(m)(H) for other values of m as well as some bounds on the fractional analogues of these numbers.