An Introduction to Razborov’s Flag Algebra as a Proof System for Extremal Graph Theory

Gyeongwon Jeong, Seonghun Park, Hongseok Yang · 2026

Read An Introduction to Razborov’s Flag Algebra as a Proof System for Extremal Graph Theory by Gyeongwon Jeong, Seonghun Park, Hongseok Yang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-12741.txt.

Introduction

Gyeongwon Jeong, Seonghun Park, and Hongseok Yang introduce flag algebra to computer scientists. Flag algebra is a framework by Razborov for extremal graph theory. It derives asymptotic inequalities between densities of induced subgraphs. Many advances in the field rest on this method, yet it stays unfamiliar outside its home area.

The survey presents flag algebra as a proof system. That framing speaks to readers in logic, programming languages, and formal methods. Automated verification researchers may see tools they can borrow or formalize. A bridge of this kind can move proof ideas between fields. It may also spur machine checked versions of flag algebra arguments.

Catalog record

CREATORGyeongwon Jeong, Seonghun Park, Hongseok Yang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE389 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-12741

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Introduction to Razborov’s Flag Algebra as a Proof System for Extremal Graph Theory Gyeongwon Jeong, Seonghun Park, Hongseok Yang Abstract Razborov’s flag algebra forms a powerful framework for deriving asymptotic inequalities between induced subgraph densities, underpinning many advances in extremal graph theory. This survey introduces flag algebra to computer scientists working in logic, programming languages, automated verification, and formal methods. We take a logical perspective on flag algebra and present it in terms of syntax, semantics, and proof strategies, in a style closer to formal logic. One popular proof strategy derives valid inequalities by first proving inequalities in a labelled variant of flag algebra and then transferring them to the original unlabelled setting using the so-called downward operator. We explain this strategy in detail and highlight that its transfer mechanism relies on the notion of what we call an adjoint pair, reminiscent of Galois connections and categorical adjunctions, which appear frequently in work on automated verification and programming languages. Along the way, we work through representative examples, including Mantel’s theorem and Goodman’s bound on Ramsey multiplicity, to illustrate how mathematical arguments can be carried out symbolically in the flag algebra framework. 1 Introduction Razborov’s flag algebra [ 17 ] is a framework for reasoning about asymptotic (i.e., large-size) properties of combinatorial structures. In extremal graph theory, many problems ask for the maximum or minimum possible density of a fixed finite pattern (such as an edge, a triangle, or an induced cycle) among all large graphs satisfying certain constraints (such as forbidding a subgraph). Flag algebra turns such questions into optimisation problems over a compact space of limit objects, and provides a symbolic calculus for deriving valid inequalities between densities of those finite patterns. Since its introduction, the flag algebra framework has led to solutions of, and substantial progress on, several central problems in extremal graph theory, including the minimum triangle density problem [ 18 ] , Erdős’s pentagon problem [ 11 , 9 ] , the induced 5 -cycle density problem [ 3 ] , Turán’s tetrahedron problem [ 19 , 1 ] , and the rainbow-triangle density problem [ 2 ] . Many key proof steps in the framework have also been automated: Flagmatic [ 6 , 16 ] is a widely used tool that underpins several of these results in extremal graph theory. This article surveys flag algebra for computer scientists working in logic, programming languages, automated verification, and formal methods. Although several excellent surveys on flag algebra exist [ 20 , 5 , 10 ] , they are written primarily for mathematicians, presenting flag algebra as a symbolic calculus for familiar arguments (e.g., double counting and applications of Cauchy–Schwarz). They also emphasise the algebraic viewpoint of flag algebra. By contrast, we take a logical perspective and present flag algebra in terms of syntax, semantics, and proof strategies, in a style closer to formal logic. We also highlight that some core constructions (notably the so-called downward operator that relates labelled and unlabelled settings) can be understood via ideas reminiscent of Galois connections and, more generally, categorical adjunctions—concepts that frequently appear in automated verification and programming languages. The results explained in this survey article, such as lemmas and their proofs, are from Razborov’s original paper on flag algebra [ 17 ] , although they are presented here in a slightly different style to emphasise the logical perspective and fit the overall narrative. The rest of the paper is organised as follows. In the remainder of this introduction, we fix some notation and terminology used throughout the paper. In Section 2 , we review the notion of induced subgraph density and use it to formulate representative asymptotic problems in extremal graph theory. In Section 3 , we introduce limiting graphs, which enable a concise description of these problems and form the semantic basis of flag algebra. In Section 4 , we present flag algebra as a logical system with two kinds of terms—density expressions and assertions—together with a semantics in terms of limiting graphs. We also illustrate, through two examples, how standard extremal arguments can be expressed as derivations in this system. The key steps in both examples rely on a nontrivial inequality. In Section 5 , we describe a strategy for proving such inequalities using labelled variants of flag algebra together with a mechanism for transferring inequalities from the labelled setting to the unlabelled one via the so-called downward operator. Finally, in Section 6 , we discuss research opportunities in flag algebra for computer scientists working in logic, programming languages, automated verification, and formal methods. Before we begin, we fix some notation and terminology. For each n\in\mathbb{N} , we write [n] for the set \{1,2,\ldots,n\} . For a set X and a nonnegative integer n , we write \binom{X}{n} for the set of all n -element subsets of X . Throughout the paper, we consider finite, simple, undirected graphs G whose vertex set is a subset of \mathbb{N} . Here, simple means that G has neither loops (i.e., edges from a vertex to itself) nor multiple edges (i.e., more than one edge between the same pair of vertices). Thus, such a graph G is formally a pair consisting of a finite set V\subseteq\mathbb{N} and a set E\subseteq\binom{V}{2} . We refer to these simply as graphs , and write \mathcal{G} for the set of all graphs. Note that \mathcal{G} is countably infinite. For a graph G , we write V(G) and E(G) for its vertex set and edge set, respectively, and v(G)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}|V(G)| and e(G)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}|E(G)| for their cardinalities. For U\subseteq V(G) , we write G[U] for the subgraph of G induced by U , i.e., the graph with vertex set U and edge set E(G)\cap\binom{U}{2} . We use standard notation for common graphs. The complete graph on vertex set [n] is denoted by K_{n} (so E(K_{n})=\binom{[n]}{2} ), the path on n vertices by P_{n} (i.e., V(P_{n})=[n] and E(P_{n})=\{\{i,i+1\}:i\in[n-1]\} ), and the edgeless graph with n vertices by I_{n} (i.e., V(I_{n})=[n] and E(I_{n})=\emptyset ). 2 Induced Subgraph Density Let H and G be graphs with v(H)\leq v(G) . The central notion in this survey article is the induced subgraph density of H in G , or simply the H -density in G , defined by p(H,G)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathbb{P}\big[G[\mathbf{U}]\simeq H\big], where \mathbf{U} is a uniformly random subset of V(G) of size v(H) , and \simeq denotes graph isomorphism. In words, p(H,G) is the probability that a uniformly random set of v(H) vertices of G induces a subgraph isomorphic to H . For instance, if H=K_{2} and G=K_{3} , then p(H,G)=1 , since every induced subgraph of G on two vertices is isomorphic to H . As another example, if H=K_{2} and G=P_{3} , then p(H,G)=\frac{2}{3} , since among the three induced subgraphs of G on two vertices, exactly two are isomorphic to H . By convention, we set p(H,G)=0 if v(H)>v(G) . Many asymptotic extremal problems can be phrased in terms of induced subgraph densities. A representative example is an asymptotic induced-subgraph version of a Turán-type problem: given a graph H and a finite set of forbidden graphs \mathcal{F} such that there exists at least one graph avoiding every graph in \mathcal{F} , determine the maximum possible H -density in large graphs that avoid

Read the complete text