Minimizing the number of 5-cycles in graphs with given edge-density

Abstract

Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle $C_5$. We show that every graph of order $n$ and size $\left(1-\frac{1}{k}\right)\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, where $k\ge 3$ is an integer, contains at least \[ \left( \frac{1}{10} -\frac{1}{2k} + \frac{1}{k^2} - \frac{1}{k^3} + \frac{2}{5 k^4} \right)n^5 +o(n^5) \] copies of $C_5$. This bound is optimal, since a matching upper bound is given by the balanced complete $k$-partite graph. The proof is based on the flag algebras framework. We also provide a stability result. An SDP solver is not necessary to verify our proofs.

This is a revised version