Yani Pehova

Decomposing graphs into edges and triangles

In a paper from 1966 Erdős, Goodman and Pósa showed that for every graph G of order n there exists a decomposition of the edges of G into at most n^2/4 complete graphs. In fact, it is enough to consider only edges and triangles for this decomposition. This is best possible, as witnessed by the complete balanced bipartite graph. It was shown by Győri and Kostochka in 1980, and independently by Chung in 1981, that if one seeks to minimise not the number, but the sum of the sizes of cliques in a decomposition, the corresponding minimum is n^2/2. It was conjectured by Győri and Tuza that edges and triangles suffice here too. We apply the flag algebra method to a fractional relaxation of this problem to prove an asymptotic version of this conjecture, that is, that every graph G of order n can be decomposed into cliques C_1,...,C_k of orders two and three, so that |C_1|+...+|C_k|< (1/2+o(1))n^2, and employ some stability arguments to obtain the sharp bound of n^2/2+1. This is joint work with (various subsets of) Adam Blumenthal, Dan Král', Taísa Martins, Bernard Lidický, Florian Pfender, Oleg Pikhurko and Jan Volec.