Department of

May 2019 June 2019 July 2019 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 1 1 2 3 4 5 6 5 6 7 8 9 10 11 2 3 4 5 6 7 8 7 8 9 10 11 12 13 12 13 14 15 16 17 18 9 10 11 12 13 14 15 14 15 16 17 18 19 20 19 20 21 22 23 24 25 16 17 18 19 20 21 22 21 22 23 24 25 26 27 26 27 28 29 30 31 23 24 25 26 27 28 29 28 29 30 31 30

Friday, June 14, 2019

**Abstract:** We prove the following 30-year old conjecture of Gyori and Tuza: the edges of every $n$-vertex graph $G$ can be decomposed into complete graphs $C_1,\ldots,C_\ell$ of orders two and three such that $|C_1|+\cdots+|C_\ell|\le (1/2+o(1))n^2$. This result implies the asymptotic version of the old result of Erdos, Goodman and Posa that asserts the existence of such a decomposition with $\ell\le n^2/4$. We also discuss removing $o(1)$ term sharpening the result and possible extensions. The talk is based on joint works with Blumenthal, Kral, Martins, Pehova, Pikhurko, Pfender, Vole.