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,[1] 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.[2]

Motivation

edit

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.[3] 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.[4]

Definition

edit

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

 .

Recall that the previous proof for Mantel's involved linear combinations of terms of the form  . The relevant ideas were slightly imprecise with letting   tend to infinity, but explicitly there is a sequence   such that   converges to some   for all  , where   is called a limit functional. Thus, all references to   really refer to the limit functional. Now, graph homomorphism inequalities can be written as linear combinations of   with different  s, but it would be convenient to express them as a single term. This motivates defining  , the set of formal linear combinations of  -flags over  , and now   can be extended to a linear function over  .

However, using the full space   is wasteful when investigating just limit functionals, since there exist nontrivial relations between densities of certain  -flags. In particular, the Chain Rule shows that

 

is always true. Rather than dealing with all of these elements of the kernel, let the set of expressions of the above form (i.e. those obtained from Chain Rule with a single  -flag) as   and quotient them out in our final analysis. These ideas combine to form the definition for a flag algebra:

Definition (Flag Algebras): A flag algebra is defined on the space of linear combinations of  -flags   equipped with bilinear operator

 

for   and any natural   such that   fit in a  -flag of size  , extending the operator linearly to  .

It remains to check that the choice of   does not matter for a pair   provided it is large enough (this can be proven with Chain Rule) as well as that if   then  , meaning that the operator respects the quotient and thus forms a well-defined algebra on the desired space.

One important result of this definition for the operator is that multiplication is respected on limit functionals. In particular, for a limit functional  , the identity   holds true. For example, it was shown that   in our proof for Mantel's, and this result is just a corollary of this statement. More generally, the fact that   is multiplicative means that all limit functionals are algebra homomorphisms between   and  .

The downward operator

edit

The definition above provides a framework for dealing with  -flags, which are partially labeled graphs. However, most of the time, unlabeled graphs, or  -flags, are of greatest interest. To get from the former to the latter, define the downward operator.

The downward operator is defined in the most natural way: given a  -flag  , let   to be the  -flag resulting from forgetting the labels assigned to  . Now, to define a natural mapping between  -flags and unlabeled graphs, let   be the probability that an injective map   taken at random has image isomorphic to  , and define  . Extending   linearly to   gives a valid linear map which sends combinations of  -flags to combinations of unlabeled ones.

The most important result regarding   is its averaging properties. In particular, fix a  -flag   and unlabeled graph   with  , then choosing an embedding   of   on   at random defines random variable  . It can be shown that

 

Optimization with flag algebras

edit

All linear functionals,   are algebra homomorphisms  . Furthermore, by definition,   for any  -flag   since   represents a density limit. Thus, say that a homomorphism   is positive if and only if  , and let   be the set of positive homomorphisms. One can show that the set of limit functionals   is exactly the set of positive homomorphisms  , so it suffices to understand the latter definition of the set.

In order for a linear combination   to yield a valid graph homomorphism inequality, it needs to be nonnegative over all possible linear functionals, which will then imply that it is true for all graphs. With this in mind, define the semantic cone of type  , a set   such that

 

Once again,   is the case of most interest, which corresponds to the case of unlabeled graphs. However, the downward operator has the property of mapping   to  , and it can be shown that the image of   under   is a subset of  , meaning that any results on the type   semantic cone readily generalize to unlabeled graphs as well.

Just by naively manipulating elements of  , numerous elements of the semantic cone   can be generated. For example, since elements of   are nonnegative for  -flags, any conical combination of elements of   will yield an element of  . Perhaps more non-trivially, any conical combination of squares of elements of   will also yield an element of the semantic cone.

Though one can find squares of flags which sum to nontrivial results manually, it is often simpler to automate the process. In particular, it is possible to adapt the ideas in sum-of-squares optimization for polynomials to flag algebras. Define the degree of a vector   to be the largest flag with nonzero coefficient in the expansion of  , and let the degree of   to be the minimum degree of a vector over all choices in  . Also, define   as the canonical embedding sending   to itself for all  . These definitions give rise to the following flag-algebra analogue:

Theorem: Given  ,  , then there exist   for some   if and only if there is a positive semidefinite matrix   such that  .

With this theorem, graph homomorphism problems can now be relaxed into semidefinite programming ones which can be solved via computer. For example, Mantel's Theorem can be rephrased as finding the smallest   such that  . As   is poorly understood, it is difficult to make progress on the question in this form, but note that conic combinations of  -flags and squares of vectors lie in  , so instead take a semidefinite relaxation. In particular, minimize   under the constraint that   where   is a conic combination of  -flags and   is positive semi-definite. This new optimization problem can be transformed into a semidefinite-programming problem which is then solvable with standard algorithms.[5]

Generalizations

edit

The method of flag algebras readily generalizes to numerous graph-like constructs. As Razborov wrote in his original paper, flags can be described with finite model theory instead. Instead of graphs, models of some nondegenerate universal first-order theory   with equality in a finite relational signature   with only predicate symbols can be used. A model  , which replaces our previous notion of a graph, has ground set  , whose elements are called vertices.

Now, defining sub-models and model embeddings in an analogous way to subgraphs and graph embeddings, all of the definitions and theorems above can be nearly directly translated into the language of model theory. The fact that the theory of flag algebras generalizes well means that it can be used not only to solve problems in simple graphs, but also similar constructs such as, but not limited to, directed graphs and hypergraphs.

References

edit
  1. ^ Razborov, Alexander (December 2007). "Flag algebras" (PDF). The Journal of Symbolic Logic. 72 (4): 1239–1282. doi:10.2178/jsl/1203350785. S2CID 15583096. Retrieved 27 November 2021.
  2. ^ Hatami, Hamed; Hladký, Jan; Král, Daniel; Norine, Serguei; Razborov, Alexander (2013). "On the Number of Pentagons in Triangle-Free Graphs". Journal of Combinatorial Theory, Series A. 120 (3): 722–732. arXiv:1102.1634. doi:10.1016/j.jcta.2012.12.008. S2CID 13162237.
  3. ^ Bondy, John Adrian (1997). "Counting Subgraphs: A new approach to the Caccetta-Häggkvist conjecture" (PDF). Discrete Mathematics. 165/166: 71–80. doi:10.1016/S0012-365X(96)00162-8. Retrieved 27 November 2021.
  4. ^ De Carli Silva, Marcel K.; De Oliveira Filho, Fernando Mário; Sato, Cristiane Maria (September 2016). "Flag Algebras: A First Glance" (PDF). Nieuw Archief voor Wiskunde. arXiv:1607.04741.
  5. ^ Razborov, Alexander (November 2013). "What is a Flag Algebra" (PDF). Notices of the AMS. 60 (10): 1324–1327. Retrieved 27 November 2021.