A Tight Fractional Version of Generalized Tuza's Conjecture

Abstract

For an $r$-uniform hypergraph $H$, let $\nu(H)$ be the maximum number of edges no two of which share $r-1$ vertices, and $\tau(H)$ the minimum number of $(r-1)$-sets such that every edge contains one of them. Aharoni and Zerbib conjectured that $\tau(H)\le\lceil\frac{r+1}{2}\rceil\,\nu(H)$, which for $r=3$ generalizes Tuza's conjecture on triangles. We prove that the fractional relaxation $\tau^*(H)$ of $\tau(H)$ satisfies $\tau^*(H)\le\frac{r+1}{2}\,\nu(H)$. This constant is best possible for every $r$, and for $r\ge4$ it improves on the previous bound of roughly $3r/4$.