Improved bounds on a generalization of Tuza's conjecture

Abdul Basit ; Daniel McGinnis¹ ; Henry Simmons¹ ; Matt Sinnwell¹ ; Shira Zerbib¹

¹Iowa State University

The electronic journal of combinatorics, Tome 29 (2022) no. 4

Résumé

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^{*(m)}(H)$ and $\tau^{*(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) \leq \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$,\[ \tau^{*(r-1)}(H)/\nu^{(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^{*(m)}(H) \le \operatorname{ex}_m(r, m+1)$, where the Turán number $\operatorname{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)$.

Détail

DOI : 10.37236/10829

Classification : 05C70, 05C65, 05D15
Mots-clés : covering number, \(r\)-uniform hypergraphs