ACO The ACO Seminar (2019–2020)

November 21, 3:30pm, Wean 8220
Shira Zerbib, Iowa State University
Tuza's conjecture: a generalization and the random case

Abstract:

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.


Back to the ACO home page Back to the ACO Seminar schedule