A famous conjecture of Tuza is that the minimal number of edges needed to cover all triangles in a graph is at most twice the maximal size of a set of edge-disjoint triangles. We show that Tuza's conjecture holds in the random graph \(G = G(n, m)\), when \(m \leqslant 0.24n^{3/2}\) or \(m \geqslant 2.13n^{3/2}\). This is done by analyzing a greedy algorithm for finding large triangle packings in random graphs. We also propose a wider setting for Tuza's conjecture for \(k\)-uniform hypergraphs, and show that most known bounds in Tuza's conjecture carry over to this general setting. Finally, we consider the fractional and \(k\)-partite version of our conjecture.
Joint works with Ron Aharoni, Patrick Bennett, and Andrzej Dudek.
Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.
The ACO Seminar (2019–2020)