Tuza's conjecture for random graphs. Issue 2 (13th November 2021)

• Record Type: Journal Article
• Authors: Kahn, Jeff; Park, Jinyoung
• Is Part Of: Random structures & algorithms. Volume 61:Issue 2(2022)
• Page Start: 235
• Page End: 249
• Publication Date: 2021-11-13
• Subjects: branching process -- coupling -- random graph -- random greedy matching -- Tuza's conjecture; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21057
• Languages: English
• ISSNs: 1042-9832

Abstract

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 → ∞ ) .