New bounds on a generalization of Tuza's conjecture

Abstract

For a $k$-uniform hypergraph $H$, let ${\nu }^{(m)}(H)$ denote the maximum size of a set $S$ of edges of $H$ whose pairwise intersection has size less than $m$. Let ${\tau }^{(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$, ${\tau }^{(k-1)}(H)/{\nu }^{(k-1)}(H)\le \lceil \frac{k+1}{2}\rceil$. In this paper, we show that this generalization of Tuza's conjecture holds when ${\nu }^{(k-1)}(H)\le 3$. As a corollary, we obtain a graph class which satisfies Tuza's conjecture. We also prove various bounds on ${\tau }^{(m)}(H)/{\nu }^{(m)}(H)$ for other values of $m$ as well as some bounds on the fractional analogues of these numbers.

arXiv comment16 pages, 2 figures