Generalized Tuza's conjecture for random hypergraphs

Abstract

A celebrated conjecture of Tuza states that in any finite graph the minimum size of a cover of triangles by edges is at most twice the maximum size of a set of edge-disjoint triangles. For an $r$-uniform hypergraph ($r$-graph) $G$, let $\ddot{I}„(G)$ be the minimum size of a cover of edges by $(r-1)$-sets of vertices, and let $\hat{I}½(G)$ be the maximum size of a set of edges pairwise intersecting in fewer than $r-1$ vertices. Aharoni and Zerbib proposed the following generalization of Tuza's conjecture: $$\text{For any r-graph G, I¨„(G)/I^½(G)≤⌈(r+1)/2⌉.}$$ Let $H_r(n,p)$ be the uniformly random $r$-graph on $n$ vertices. We show that, for $r\in \{3,4,5\}$ and any $p=p(n)$, $H_r(n,p)$ satisfies the Aharoni-Zerbib conjecture with high probability (i.e., with probability approaching 1 as $n\to \infty$). We also show that there is a $C<1$ such that, for any $r\ge 6$ and any $p=p(n)$, $\ddot{I}„(H_r(n,p))/\hat{I}½(H_r(n,p))\le Cr$ with high probability. Furthermore, we may take $C<1/2+\epsilon$, for any $\epsilon >0$, by restricting to sufficiently large $r$ (depending on $\epsilon$).

32 pages including references and appendix; minor corrections throughout the article; accepted to SIAM J. Discrete Math