Improved bounds on a generalization of Tuza's conjecture

Abstract

For an $r$-uniform hypergraph $H$, let ${\nu }^{(m)}(H)$ denote the maximum size of a set~$M$ of edges in $H$ such that every two edges in $M$ intersect in less than $m$ vertices, and let ${\tau }^{(m)}(H)$ denote the minimum size of a collection $C$ of $m$-sets of vertices such that every edge in $H$ contains an element of $C$. The fractional analogues of these parameters are denoted by ${\nu }^{\ast (m)}(H)$ and ${\tau }^{\ast (m)}(H)$, respectively. Generalizing a famous conjecture of Tuza on covering triangles in a graph, Aharoni and Zerbib conjectured that for every $r$-uniform hypergraph $H$, ${\tau }^{(r-1)}(H)/{\nu }^{(r-1)}(H)\le \lceil \frac{r+1}{2}\rceil$. In this paper we prove bounds on the ratio between the parameters ${\tau }^{(m)}$ and ${\nu }^{(m)}$, and their fractional analogues. Our main result is that, for every $r$-uniform hypergraph~$H$, \[ τ^{*(r-1)}(H)/ν^{(r-1)}(H) \le \begin{cases} \frac{3}{4}r - \frac{r}{4(r+1)} &\text{for }r\text{ even,}\\ \frac{3}{4}r - \frac{r}{4(r+2)} &\text{for }r\text{ odd.} \\ \end{cases} \] This improves the known bound of $r-1$. We also prove that, for every $r$-uniform hypergraph $H$, ${\tau }^{(m)}(H)/{\nu }^{\ast (m)}(H)\le {\mathrm{ex}}_m(r,m+1)$, where the Turán number ${\mathrm{ex}}_r(n,k)$ is the maximum number of edges in an $r$-uniform hypergraph on $n$ vertices that does not contain a copy of the complete $r$-uniform hypergraph on $k$ vertices. Finally, we prove further bounds in the special cases $(r,m)=(4,2)$ and $(r,m)=(4,3)$.

23 pages; minor corrections throughout the article, updated references; accepted to the Electron. J. Combin