WHAT IS... a Flag Algebra?

Before attempting to answer the question from the title, it would be useful to say a few words about another one: what kind of problems have flag algebras been invented for? Let us consider three similar combinatorial puzzles. Assume that we have a (simple, undirected) graph with n vertices. What is the minimal number of edges m (as a function in n) that guarantee the existence of a triangle? And, assuming that m is above this threshold, how many triangles are guaranteed to exist? Let us now offset everything by one, and instead of graphs consider (simple) 3-graphs, i.e. sets of unordered triples (called 3-edges) on n vertices. We again ask what is the minimal value of m that guarantees the existence of four vertices such that all four possible triples spanned by these vertices are in the set of 3-edges. The sub-area of discrete mathematics that deals with questions of this sort is called extremal combinatorics, and it is very strategically located at a crossroad between “pure” mathematics and its applications. One good way to describe flag algebras is as an attempt to expose and emphasize some common mathematical structure underlying many standard techniques in extremal combinatorics, and a survey of concrete results obtained on this way can be found in [1]. Before going into more details, however, let me encourage the reader to put this article aside and try to predict the current status of the three problems from the previous paragraph. Ready? The first problem (on the threshold value m(n)) was solved in a classical paper by Mantel published in 1907. The second problem (on the minimal number of triangles beyond the threshold) had been open for some