Flag algebras.

*(English)*Zbl 1146.03013Although this paper is presented as a work in (relational) finite model theory, it is also a very significant and interesting work in extremal combinatorics. It presents a formal calculus for computing densities of occurrences of combinatorial substructures within combinatorial structures, most notably for the occurrences of (isomorphic copies of) a graph within larger graphs. In the introduction, the author proposes to distill and organize a “handful” of techniques into an algebraic apparatus that would clarify the mathematics and on occasion make it more accessible to computerization. The paper is presented largely in terms of graphs and digraphs, but it actually applies to any signature for relational structures.

The basic idea is the notion of a flag algebra. Fixing a signature, a flag is a model with a specific submodel (fixed by an assignment \(\sigma\)), and \(\mathcal F^{\sigma}\) is the set of all (isomorphism types of) flags with the submodel specified by \(\sigma\) (and \(\mathcal F^{\sigma}_{\ell}\) is the set of such flags of cardinality \(\ell\)). Then, if \(\mathbb R \mathcal F^{\sigma}\) is the (formal) linear algebra of basis \(\mathcal F^{\sigma}\), we can mod out a kernel of formal combinations to get an algebra generated by equalities

\[ \widetilde F = \sum_{F\in \mathcal F^{\sigma}_{\ell}} p(\widetilde F, F) F, \] where \(p(F_1, F_2)\) is the probability that if we chose card\((F_1)\) points at random (in accordance with some given distribution) from \(F_2\), including the common submodel fixed by \(\sigma\), the resulting flag would be isomorphic to \(F_1\). (The sum turns out to be independent of \(\ell\) provided that the flag \(F\) has at least \(\ell\) elements.)

The resulting algebra \(\mathcal A^{\sigma}\) is extended to include multiplication, allowing for formal products of graphs representing distributions of the factors. These formal expressions are decoded using (positive) homomorphisms \(\mathcal A^{\sigma} \to \mathbb R\), which are used to define a partial ordering on \(\mathcal A\) that is preserved under these maps. The end results are numerical formulas or equations giving relations between edge densities, subgraph densities, and other quantities. For example, an asymptotic density result arising from [L. LovĂˇsz and M. Simonovits, “On the number of complete subgraphs of a graph. II”, Studies in pure mathematics, Mem. of P. Turan, 459–495 (1983; Zbl 0519.05042)], that in a graph the density of edges \(d_2\) and the density of triangles \(d_3\) is related by \(d_3 \geq 2d_2^2 - d_2\), follows from the fact that in \(\mathcal A^{\sigma}\), for \(K_{\ell}\) being the \(\ell\)-clique, \(K_3 \geq K_2 (2K_2 - 1)\).

The calculus proposed is rather difficult, and the exposition is very dense (and uses many applications from a variety of areas of mathematics), yet the potential seems impressive. In fact, there is a certain air of elephant-crushing-walnut in the examples at the end, and it seems likely that once this system is polished and made accessible to a broad audience, it will find a broad applicability.

The basic idea is the notion of a flag algebra. Fixing a signature, a flag is a model with a specific submodel (fixed by an assignment \(\sigma\)), and \(\mathcal F^{\sigma}\) is the set of all (isomorphism types of) flags with the submodel specified by \(\sigma\) (and \(\mathcal F^{\sigma}_{\ell}\) is the set of such flags of cardinality \(\ell\)). Then, if \(\mathbb R \mathcal F^{\sigma}\) is the (formal) linear algebra of basis \(\mathcal F^{\sigma}\), we can mod out a kernel of formal combinations to get an algebra generated by equalities

\[ \widetilde F = \sum_{F\in \mathcal F^{\sigma}_{\ell}} p(\widetilde F, F) F, \] where \(p(F_1, F_2)\) is the probability that if we chose card\((F_1)\) points at random (in accordance with some given distribution) from \(F_2\), including the common submodel fixed by \(\sigma\), the resulting flag would be isomorphic to \(F_1\). (The sum turns out to be independent of \(\ell\) provided that the flag \(F\) has at least \(\ell\) elements.)

The resulting algebra \(\mathcal A^{\sigma}\) is extended to include multiplication, allowing for formal products of graphs representing distributions of the factors. These formal expressions are decoded using (positive) homomorphisms \(\mathcal A^{\sigma} \to \mathbb R\), which are used to define a partial ordering on \(\mathcal A\) that is preserved under these maps. The end results are numerical formulas or equations giving relations between edge densities, subgraph densities, and other quantities. For example, an asymptotic density result arising from [L. LovĂˇsz and M. Simonovits, “On the number of complete subgraphs of a graph. II”, Studies in pure mathematics, Mem. of P. Turan, 459–495 (1983; Zbl 0519.05042)], that in a graph the density of edges \(d_2\) and the density of triangles \(d_3\) is related by \(d_3 \geq 2d_2^2 - d_2\), follows from the fact that in \(\mathcal A^{\sigma}\), for \(K_{\ell}\) being the \(\ell\)-clique, \(K_3 \geq K_2 (2K_2 - 1)\).

The calculus proposed is rather difficult, and the exposition is very dense (and uses many applications from a variety of areas of mathematics), yet the potential seems impressive. In fact, there is a certain air of elephant-crushing-walnut in the examples at the end, and it seems likely that once this system is polished and made accessible to a broad audience, it will find a broad applicability.

Reviewer: Gregory Loren McColm (Tampa)

##### MSC:

03C13 | Model theory of finite structures |

05A16 | Asymptotic enumeration |

05C35 | Extremal problems in graph theory |

05D05 | Extremal set theory |

05E99 | Algebraic combinatorics |

15A99 | Basic linear algebra |

##### Keywords:

asymptotic extremal combinatorics; densities of substructures; formal algebras; graph isomorphisms; positive graph homomorphisms##### References:

[1] | Discrete Mathematics 166 pp 71– (1997) · Zbl 0860.68078 |

[2] | DOI: 10.1080/10556789908805765 · Zbl 0973.90524 · doi:10.1080/10556789908805765 |

[3] | Real algebraic geometry (1998) |

[4] | Matematicko Fizicki Lapok 48 pp 436– (1941) |

[5] | Wiskundige Opgaven 10 pp 60– (1907) · JFM 38.0702.01 |

[6] | DOI: 10.1007/978-3-0348-5438-2_41 · doi:10.1007/978-3-0348-5438-2_41 |

[7] | Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science pp 419– (2002) |

[8] | DOI: 10.2307/2310464 · Zbl 0092.01305 · doi:10.2307/2310464 |

[9] | DOI: 10.1002/jgt.3190130411 · Zbl 0673.05046 · doi:10.1002/jgt.3190130411 |

[10] | Probabilistic methods in combinatorics (1974) · Zbl 0308.05001 |

[11] | DOI: 10.1007/BF02579292 · Zbl 0529.05027 · doi:10.1007/BF02579292 |

[12] | DOI: 10.1006/jctb.1999.1938 · Zbl 1027.05073 · doi:10.1006/jctb.1999.1938 |

[13] | DOI: 10.1007/BF02125347 · Zbl 0715.05057 · doi:10.1007/BF02125347 |

[14] | Congressus Numerantium 21 pp 181– (1978) |

[15] | Topics in discrete mathematics pp 315– (2006) |

[16] | Proceedings of the Fifth British Combinatorial Conference pp 79– (1976) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.