Flag algebras — Razborov's SDP-based calculus for extremal graph/hypergraph densities

Statement

Flag algebras (Razborov, *Flag algebras*, J. Symbolic Logic 72(4):1239–1282, 2007) are a formal algebraic/model-theoretic calculus that turns asymptotic extremal (hyper)graph problems — "what is the max/min limiting density of pattern $H$ subject to constraints?" — into semidefinite programming (SDP) feasibility questions that a computer can solve and whose output is a rigorous, mechanically verifiable proof certificate (en.wikipedia.org/wiki/Flag_algebra).

Core objects. - A type $\sigma$ of size $k$ is a $k$-vertex (hyper)graph with a fixed labeling $1,\dots,k$ of its vertices. - A $\sigma$-flag is a pair $(F,\theta)$ where $F$ is a member of the combinatorial class under study (e.g. all graphs, or all graphs avoiding some forbidden subgraph) and $\theta$ is an embedding of the labeled type $\sigma$ into $k$ of $F$'s vertices. - The density $p(F_1,\dots,F_t;G)$ is (informally) the probability that $t$ independently, uniformly chosen sub-flags of a large structure $G$, sharing the same labeled copy of $\sigma$, are simultaneously isomorphic to $F_1,\dots,F_t$ — the natural generalization of subgraph density to the labeled setting (en.wikipedia.org/wiki/Flag_algebra). - The flag algebra $\mathcal A^\sigma = \mathbb R\mathcal F^\sigma / K^\sigma$ is the vector space of formal $\mathbb R$-linear combinations of $\sigma$-flags, quotiented by the linear relations forced by a chain rule (an exact "average of finer counts equals coarser count" identity), and equipped with a multiplication $F\cdot F' = \sum_H p(F,F';H)\,H$ (sum over larger flags $H$) chosen so that every positive homomorphism $\phi:\mathcal A^\sigma\to\mathbb R$ (i.e. every limit of density functionals along a convergent sequence of structures, in the Lovász–Szegedy graph-limit sense) is automatically a ring homomorphism: $\phi(f\cdot g)=\phi(f)\phi(g)$ (en.wikipedia.org/wiki/Flag_algebra; arxiv.org/abs/1607.04741). - The downward/averaging operator $[\![\cdot]\!]_\sigma:\mathcal A^\sigma\to\mathcal A^\emptyset$ forgets the type-$\sigma$ labels, converting a labeled-flag identity back into an unlabeled statement about ordinary (hyper)graph densities, weighted by $q_\sigma(F)$ = the probability a random labeling of (a copy of) $\sigma$ inside $F$ succeeds (en.wikipedia.org/wiki/Flag_algebra).

The semidefinite method (the actual proof engine). For any type $\sigma$ and any $n$, list all $\sigma$-flags of a fixed larger size as a vector $v_{\sigma,n}$. For any positive semidefinite matrix $Q\succeq 0$, the quadratic form $v_{\sigma,n}^{\mathsf T} Q\, v_{\sigma,n}$, after applying $[\![\cdot]\!]_\sigma$, is a valid, provably nonnegative element of the *semantic cone* $S^\emptyset$ — i.e. a true, universally-valid density inequality — because it is (an average of) a sum of squares, and squares of real quantities (here: $[\![f\cdot f]\!]_\sigma$ for $f\in\mathcal A^\sigma$, generalized to matrices via Cauchy–Schwarz-type arguments) are $\ge 0$ under *every* positive homomorphism (en.wikipedia.org/wiki/Flag_algebra). Conversely, to *prove* a target inequality $\sum c_i \,\mathrm{density}(H_i) \ge 0$ (or find the best constant $c$ such that $\mathrm{density}(H)\le c$), one searches — via an SDP solver — for a decomposition of the (negated) target as such a nonnegative sum-of-squares-of-flags combination plus a small residual; feasibility of the SDP (i.e. existence of a suitable $Q\succeq0$) *is* the proof, and $Q$'s entries (often rounded to exact rationals and re-verified by hand via Gaussian elimination / positivity of principal minors) constitute a checkable certificate (en.wikipedia.org/wiki/Flag_algebra; matches the general description in problems/500.md's provenance, citing the Keevash survey's remark that flag-algebra SDP outputs are "in principle exact/rational verifiable").

Facts

- Origin and motivating example. Razborov's 2007 JSL paper credits J. A. Bondy's graph-homomorphism-flavored proof of Mantel's theorem (triangle-free $\Rightarrow \le n^2/4$ edges) as the conceptual seed, and the paper's own first worked application is a new, short proof of Fisher's theorem on the minimum triangle density forced by a given edge density (en.wikipedia.org/wiki/Flag_algebra; WebSearch corroboration of the JSL abstract). - Scope beyond graphs. The same formalism applies to any class of finite relational/model-theoretic structures closed under the relevant operations: ordinary graphs, 3-uniform and general $r$-uniform hypergraphs (the natural home for Turán-density questions), digraphs/oriented graphs, permutations, point configurations, edge-colored graphs, hypercubes, and phylogenetic trees (WebSearch summary corroborated across multiple secondary sources; arxiv.org/abs/1607.04741). - Landmark results proved with flag algebras (the "derivation fuel" list — each is a concrete instance of the SDP recipe below): - $\pi(K_4^{(3)}) \le 0.561666$ (Razborov 2010, confirmed independently by Baber–Talbot's "Hypergraphs do jump" paper, arXiv:1110.1623) — best known upper bound on the tetrahedron Turán density, see Erdős #500 — Turán density of the tetrahedron $K_4^{3}$. - $\pi(K_5^{(3)}) \le 0.769533$ (Baber–Talbot, arXiv:1110.1623) — see Erdős #712 — Turán density of complete $r$-uniform hypergraphs $K_k^r$. - Pentagon theorem (Erdős 1984 conjecture): every $n$-vertex triangle-free graph has at most $(n/5)^5$ copies of $C_5$, tight when $5\mid n$ (balanced blow-up of $C_5$) — proved independently by Grzesik (JCTB 2012) and by Hatami–Hladký–Kráľ–Norine–Razborov (JCTA 120(3):722–732, 2013, arXiv:1102.1634), both via flag algebras. - Caccetta–Häggkvist conjecture, $r=n/3$ special case: Hladký, Kráľ' and Norin (Combinatorica, arXiv:0908.2791) proved every digraph with min out-degree $\ge 0.3465n$ contains a directed triangle, improving Hamburger–Haxell–Kostochka's $0.3532n$; "the main new tool ... is the theory of flag algebras" (paper's own framing, per WebSearch). - Uniform Turán density of the broken tetrahedron $\pi_u(K_4^{(3)-}) = 1/4$: Glebov–Král'–Volec (Israel J. Math. 2016, arXiv:1303.7372) via flag algebras, matched independently by Reiher–Rödl–Schacht via hypergraph regularity — see problems/broken-tetrahedron-uniform-density.md. - Hypercube Turán densities: Balogh–Hu–Lidický–Liu (arXiv:1201.0209) and Rahil Baber (arXiv:1201.3587) get the current-best $C_4$-free and $C_6$-free hypercube-subgraph density bounds by "modify[ing] slightly Razborov's flag algebra machinery to be suitable for the hypercube" — see Erdős #86 — C4-free subgraphs of the hypercube density. - Ramsey-multiplicity and small-Ramsey-number computations, double-star Ramsey numbers, and packing densities of permutations are further documented application areas (WebSearch, multiple corroborating survey/paper hits: arxiv.org/abs/2407.07285, arxiv.org/abs/1704.02959). - Software. Flagmatic (Emil R. Vaughan, with Victor Falgas-Ravry) is the standard implementation for 3-graph Turán-density flag-algebra SDPs, used e.g. in Baber–Talbot's tetrahedron/K5 bounds (lidicky.name/flagmatic; arXiv:1110.1623). Newer/actively-developed tooling includes a SageMath-based FlagAlgebraToolbox (arxiv.org/html/2601.06590) and the Zuse-Institute "Scaling Up Flag Algebras" project targeting larger SDP orders (iol.zib.de/project/flagscale.html). - Fundamental limitation — undecidability, not just hardness. Hatami & Norine, "Undecidability of linear inequalities in graph homomorphism densities" (J. Amer. Math. Soc. 24(2):547–565, 2011, arXiv:1005.2382), prove that determining the validity of an arbitrary polynomial inequality in homomorphism densities is undecidable, and — directly relevant to flag algebras' own proof mechanism — they answer a question of Lovász and of Razborov in the negative by exhibiting explicit *valid* (true) quantum-graph inequalities that are not expressible as a sum of squares of (averaged) flags. Consequence: there is no algorithmic guarantee that a true density inequality has *any* flag-algebra/SDP proof at a bounded type-size, let alone that increasing the SDP order will find one — a stalled numerical bound (e.g. $\pi(K_4^{(3)})$ stuck at $0.5611666$ since 2010–2011, see Erdős #500 — Turán density of the tetrahedron $K_4^{3}$) may reflect this structural ceiling rather than insufficient computation. - Lack of stability/instability signals a second, practical limitation. Flag-algebra SDP bounds are strongest (and most likely to be *tight*, closing a problem exactly) when the extremal configuration is essentially unique up to $o(n^2)$/$o(n^3)$ perturbations ("stability"); when a problem instead has exponentially many pairwise non-isomorphic near-extremal constructions (as with $K_4^{(3)}$: Brown, Kostochka, Fon-der-Flaass, Frohmader constructions, per problems/500.md), flag algebras tend to stall short of the true value, and the standard rescue is to *restrict to an induced sub-family that kills the instability* (Razborov's own trick, reused by Baber–Talbot for $K_5^{(3)}$) — see Technique below. - Connection to graph limits. The theory is formally underpinned by the Lovász–Szegedy theory of graphon/hypergraphon limits: a "positive homomorphism" $\mathcal A^\sigma\to\mathbb R$ corresponds exactly to evaluating densities in a limit object, so flag-algebra inequalities are simultaneously statements about all sufficiently large finite structures and about the limit objects (en.wikipedia.org/wiki/Flag_algebra; arxiv.org/abs/1607.04741).

Technique

WHEN it applies. Whenever a problem asks for the exact or asymptotic extremal density (edge density, subgraph density, induced-subgraph density, or a linear/simple combination thereof) of a pattern $H$ over a class of large (hyper)graphs/structures satisfying some hereditary constraint (e.g. "$H_0$-free"), in the limit $n\to\infty$ — i.e. classical Turán-density-type questions, Ramsey-multiplicity questions, inducibility questions, and their analogues for digraphs, permutations, and edge-colorings. It is essentially never useful for *exact finite-$n$* extremal numbers or for *non-density* (structural/existential) questions.

WHY it works (the mechanism). 1. Reformulate as polynomial optimization over an infinite-dimensional but well-behaved cone. Densities of subpatterns in a convergent sequence of structures behave, in the limit, exactly like evaluations of a positive homomorphism on the flag algebra — so "is inequality $X$ true for all large structures in the class" becomes "does $X$, viewed as an element of $\mathcal A^\emptyset$, lie in the semantic cone $S^\emptyset$." 2. Relax "lies in the cone" to "is a sum of squares of averaged flags," which is SDP-checkable. Any nonnegative combination $[\![Q\text{-weighted flag products}]\!]_\sigma$ with $Q\succeq0$ is automatically in $S^\emptyset$ (since $\phi$ is a ring homomorphism, squares map to squares $\ge 0$). This converts "find a proof of the target inequality" into "does there exist $Q\succeq 0$ making the target minus this SO-form equal to $0$ (or as small as possible)" — a linear/semidefinite feasibility problem, solvable by off-the-shelf SDP solvers (CSDP, SDPA, etc.), because the coefficients (densities $p(F,F';H)$) are purely combinatorial and computable in advance. 3. Larger type size $\Rightarrow$ tighter (never worse) bound, at exponential computational cost. Increasing $|\sigma|$ and the flag sizes considered enlarges the space of available square-certificates monotonically, so the sequence of SDP-optimal bounds is non-increasing (for an upper-bound problem) and, by a general density argument, the whole hierarchy is complete *in principle* for inequalities that do admit an SDP-of-this-form proof at all — but by Hatami–Norine, not every true inequality does, and even when one exists the required type size can be unbounded, so there is no a priori stopping rule (see Facts).

Recombination recipe — how a solver actually uses flag algebras to attack a new problem: 1. Encode the extremal question as a Turán/homomorphism-density statement: identify the forbidden/target pattern(s), the ambient class (all graphs / all $r$-uniform hypergraphs / all digraphs / …), and write the quantity to be bounded as a linear combination of densities of small patterns. 2. Choose the type(s) $\sigma$ — usually a small labeled sub-structure (e.g. a single labeled vertex, a labeled edge, a labeled triangle) whose neighborhood/link structure is expected to carry the relevant local information; this choice is the main "art" of the method and directly controls the size (hence tractability) of the resulting SDP. 3. Generate all flags up to the target size (mechanical, exponential in size — this is exactly what Flagmatic / FlagAlgebraToolbox automate) and compute the density-multiplication table $p(F,F';H)$ between them. 4. Run the SDP: maximize/minimize the target linear functional subject to the semidefiniteness constraints from step 3 plus any known equalities (from the chain rule) — this both *searches for the best possible bound the method can give at this type size* and, on success, outputs the certificate $Q$. 5. If the SDP bound is not tight (no matching construction), try: (a) a larger type / higher SDP order (more computation, monotonically better or equal bound); (b) restrict to an induced sub-family that removes instability (Razborov's move for $K_4^{(3)}$, replicated by Baber–Talbot for $K_5^{(3)}$ — see problems/500.md) — this can make an otherwise-unstable problem tight; (c) if a matching lower-bound construction exists and the flag-algebra bound still doesn't meet it, suspect either an undecidability-type obstruction (Hatami–Norine) or that a fundamentally different, non-SDP technique (hypergraph regularity, algebraic/norm-graph constructions, dependent random choice) is needed instead — see Kővári–Sós–Turán theorem: the double-counting bound ex(n,K_{s,t}) = O(n^{2-1/s}), Hypergraph regularity / Gowers uniformity norms and density-increment arguments: quasirandom decomposition + counting/removal lemmas, and the iterative-density-increase route to Szemerédi-type theorems for the classical alternatives that sometimes succeed where flag algebras stall. 6. Certificate verification is mechanical once found: check $Q\succeq 0$ by verifying all principal minors are nonnegative (exact/rational arithmetic), then the inequality is a *fully rigorous, human-checkable* proof despite having been discovered by computer.

Related

- Erdős #500 — Turán density of the tetrahedron $K_4^{3}$ — Turán density of the tetrahedron $K_4^{(3)}$: the canonical flag-algebra success-then-stall story (Razborov 2010 bound $\le0.5611666$, unimproved since; blocked by provable lack of stability, exactly the scenario this page's Technique section addresses). - Erdős #712 — Turán density of complete $r$-uniform hypergraphs $K_k^r$ — general Turán density $\pi(K_k^r)$ for $k>r>2$; flag-algebra bounds exist only for small $r=3$ cases ($K_4^{(3)}$, $K_5^{(3)}$) because SDP size explodes with $r$. - Erdős #86 — C4-free subgraphs of the hypercube density — $C_4$-free hypercube subgraph density; current record bounds are from a hypercube-adapted flag-algebra computation (Balogh–Hu–Lidický–Liu; Baber). - problems/broken-tetrahedron-uniform-density.md (solved/broken-tetrahedron-uniform-density) — worked example where a flag-algebra proof (Glebov–Král'–Volec) and an independent hypergraph-regularity proof (Reiher–Rödl–Schacht) reach the *same* exact constant $1/4$ by two structurally different routes; illustrates flag algebras' typical role as the faster, more mechanical "discovery engine" route. - Hypergraph regularity / Gowers uniformity norms and density-increment arguments: quasirandom decomposition + counting/removal lemmas, and the iterative-density-increase route to Szemerédi-type theorems — the classical, non-computer-assisted alternative toolkit for the same density-type extremal questions; often the fallback (or independent cross-check) when flag algebras stall or when a human-readable proof is wanted. - Kővári–Sós–Turán theorem: the double-counting bound ex(n,K_{s,t}) = O(n^{2-1/s}) — classical double-counting/convexity technique for the simplest (bipartite, $\chi=2$) degenerate Turán regime; flag algebras are the natural escalation when the pattern is non-bipartite or the double-counting bound is not tight. - Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) — a different SDP-free "replace counting by an inequality calculus" technique (subadditivity of Shannon entropy rather than positive-semidefiniteness); occasionally competes with or complements flag algebras on the same class of counting/Kruskal–Katona-type problems.