Two related papers will be discussed:
1. In 1966, Erdős, Goodman, and Pósa showed that if $G$ is an $n$-vertex graph, then at most $\lfloor n^2/4 \rfloor$ cliques of $G$ are needed to cover the edges of $G$, and the bound is best possible as witnessed by the balanced complete bipartite graph. This was generalized independently by Győri–Kostochka, Kahn, and Chung, who showed that every $n$-vertex graph admits an edge-decomposition into cliques of total `cost’ at most $2 \lfloor n^2/4 \rfloor$, where an $i$-vertex clique has cost $i$. Erdős suggested the following strengthening: every $n$-vertex graph admits an edge-decomposition into cliques of total cost at most $\lfloor n^2/4 \rfloor$, where now an $i$-vertex clique has cost $i-1$. We prove fractional relaxations and asymptotically optimal versions of both this conjecture and a conjecture of Dau, Milenkovic, and Puleo on covering the $t$-vertex cliques of a graph instead of the edges. Our proofs introduce a general framework for these problems using Zykov symmetrization, the Frankl–Rödl nibble method, and the Szemerédi Regularity Lemma. It is joint work with Jialin He, Robert Krueger, The Nguyen, and Michael Wigal.
2. Let $r \ge 3$ be fixed and $G$ be an $n$-vertex graph. A long-standing conjecture of Győri states that if $e(G) = t_{r-1}(n) + k$, where $t_{r-1}(n)$ denotes the number of edges of the Turán graph on $n$ vertices and $r – 1$ parts, then $G$ has at least $(2 – o(1))k/r$ edge-disjoint $r$-cliques. We prove this conjecture. It is joint work with Michael Wigal.