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 $\hat{I}”(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 $\hat{I}”(G)$.

30 pages, 1 figure

Topics & keywords