Strong Forms of Stability from Flag Algebra Calculations

Abstract

Given a hereditary family $\mathcal{G}$ of admissible graphs and a function $\lambda (G)$ that linearly depends on the statistics of order-$\kappa$ subgraphs in a graph $G$, we consider the extremal problem of determining $\lambda (n,\mathcal{G})$, the maximum of $\lambda (G)$ over all admissible graphs $G$ of order $n$. We call the problem perfectly $B$-stable for a graph $B$ if there is a constant $C$ such that every admissible graph $G$ of order $n\ge C$ can be made into a blow-up of $B$ by changing at most $C(\lambda (n,\mathcal{G})-\lambda (G))\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ adjacencies. As special cases, this property describes all almost extremal graphs of order $n$ within $o(n^2)$ edges and shows that every extremal graph of order $n\ge n_0$ is a blow-up of $B$. We develop general methods for establishing stability-type results from flag algebra computations and apply them to concrete examples. In fact, one of our sufficient conditions for perfect stability is stated in a way that allows automatic verification by a computer. This gives a unifying way to obtain computer-assisted proofs of many new results.

44 pages; incorporates reviewers' suggestions