Tuza's conjecture for random graphs. Issue 2 (13th November 2021) - Kahn, Jeff; Park, Jinyoung
Abstract: A celebrated conjecture of Tuza says 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. Resolving a recent question of Bennett, Dudek, and Zerbib, we show that this is true for random graphs; more precisely: for any p = p ( n ), ℙ ( G n, p satisfies Tuza's conjecture ) → 1 ( as n → ∞ ) .