The ACO Seminar (2019–2020)

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.