Closing the Random Graph Gap in Tuza's Conjecture Through the Online Triangle Packing Process

Abstract

A long-standing conjecture of Zsolt Tuza asserts that the triangle covering number $\tau (G)$ is at most twice the triangle packing number $\nu (G)$, where the triangle packing number $\nu (G)$ is the maximum size of a set of edge-disjoint triangles in $G$ and the triangle covering number $\tau (G)$ is the minimal size of a set of edges intersecting all triangles. In this paper, we prove that Tuza's conjecture holds in the Erdős-Rényi random graph $G(n,m)$ for all range of $m$, closing the gap in what was previously known. (Recently, this result was also independently proved by Jeff Kahn and Jinyoung Park.) We employ a random greedy process called the online triangle packing process to produce a triangle packing in $G(n,m)$ and analyze this process by using the differential equations method.