2022/04/09 by Basit, Abdul, Galvin, David
#05D15 #05D40 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2204.04568
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 τ(G) be the minimum size of a cover of edges by (r-1)-sets of vertices, and let ν(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: For any r-graph G, τ(G)/ν(G) ≤ \lceil(r+1)/2\rceil. Let Hr(n,p) be the uniformly random r-graph on n vertices. We show that, for r ∈ \3, 4, 5\ and any p = p(n), Hr(n,p) satisfies the Aharoni-Zerbib conjecture with high probability (i.e., with probability approaching 1 as n → ∞). We also show that there is a C < 1 such that, for any r ≥ 6 and any p = p(n), τ(Hr(n, p))/ν(Hr(n, p)) ≤ C r with high probability. Furthermore, we may take C < 1/2 + ε, for any ε > 0, by restricting to sufficiently large r (depending on ε).