Flag algebras are an important computational tool in the field of graph theory which have a wide range of applications in homomorphism density and related topics. Roughly, they formalize the notion of adding and multiplying homomorphism densities and set up a framework to solve graph homomorphism inequalities with computers by reducing them to semidefinite programming problems. Originally introduced by Alexander Razborov in a 2007 paper, the method has since come to solve numerous difficult, previously unresolved graph theoretic questions. These include the question regarding the region of feasible edge density, triangle density pairs and the maximum number of pentagons in triangle free graphs.
Motivation
The motivation of the theory of flag algebras is credited to John Adrian Bondy and his work on the Caccetta-Haggkvist conjecture, where he illustrated his main ideas via a graph homomorphism flavored proof to Mantel's Theorem. This proof is an adaptation on the traditional proof of Mantel via double counting, except phrased in terms of graph homomorphism densities and shows how much information can be encoded with just density relationships. Theorem (Mantel): The edge density in a triangle-free graph is at most . In other words, As the graph is triangle-free, among 3 vertices in , they can either form an independent set, a single induced edge , or a path of length 2 . Denoting as the induced density of a subgraph in , double counting gives: Intuitively, since a just consists of two s connected together, and there are 3 ways to label the common vertex among a set of 3 points. In fact, this can be rigorously proven by double counting the number of induced s. Letting denote the number of vertices of , we have:
where is the path of length 2 with its middle vertex labeled, and represents the density of s subject to the constraint that the labeled vertex is used, and that is counted as a proper induced subgraph only when its labeled vertex coincides with . Now, note that since the probability of choosing two s where the unlabeled vertices coincide is small (to be rigorous, a limit as should be taken, so acts as a limit function on a sequence of larger and larger graphs . This idea will be important for the actual definition of flag algebras.) To finish, apply the Cauchy–Schwarz inequality to get
Plugging this back into our original relation proves what was hypothesized intuitively. Finally, note that so
The important ideas from this proof which will be generalized in the theory of flag algebras are substitutions such as , the use of labeled graph densities, considering only the "limit case" of the densities, and applying Cauchy at the end to get a meaningful result.
Definition
Fix a collection of forbidden subgraphs and consider the set of graphs of -free graphs. Now, define a type of size to be a graph with labeled vertices . The type of size 0 is typically denoted as .
First, we define a -flag, a partially labeled graph which will be crucial for the theory of flag algebras: Definition: A -flag is a pair where is an underlying, unlabeled, -free graph, while defines a labeled graph embedding of onto the vertices . Denote the set of -flags to be and the set of -flags of size to be . As an example, from the proof of Mantel's Theorem above is a -flag where is a type of size 1 corresponding to a single vertex.
For -flags satisfying , we can define the density of the -flags onto the underlying graph in the following way: Definition: The density of the -flags in is defined to be the probability of successfully randomly embedding into such that they are nonintersecting on and are all labeled in the exact same way as on .
More precisely, choose pairwise disjoint at random and define to be the probability that the -flag is isomorphic to for all .
Note that, when embedding into , where are -flags, it can be done by first embedding into a -flag of size and then embedding into , which gives the formula: . Extending this to sets of -flags gives the Chain Rule: Theorem (Chain Rule): If are -flags, are naturals such that fit in , fit in a -flag of size , and a -flag of size combined with fit in , then .