Local flag algebras

Abstract

We introduce local flag algebras, a variant of Razborov's flag algebra framework in which densities are normalised by the maximum degree $\Delta (G)$ rather than the order $|G|$. The framework supports the same semidefinite-method machinery as the classical version, but is tailored to extremal problems that scale with the maximum degree. As an illustrative first application we bound the number of pentagons in a triangle-free graph $G$ as a function of $|G|$ and $\Delta (G)$.

30 pages, 1 figure