March 21, 3:30pm, Wean 8220

Patrick Bennett, Western Michigan University

Large triangle packings and Tuza’s conjecture in random graphs

Patrick Bennett, Western Michigan University

Large triangle packings and Tuza’s conjecture in random graphs

Abstract:

The triangle packing number $\nu(G)$ of a graph $G$ is the maximum size of a set of edge-disjoint triangles in $G$. Tuza conjectured that in any graph $G$ there exists a set of at most $2\nu(G)$ edges intersecting every triangle in $G$. We show that Tuza's conjecture holds in the random graph $G=G(n,m)$, when $m \le 0.2403n^{3/2}$ or $m\ge 2.1243n^{3/2}$. This is done by analyzing a greedy algorithm for finding large triangle packings in random graphs. This talk is about joint work with Andrzej Dudek and Shira Zerbib.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.