Computer Science/Discrete Mathematics Seminar II

The field of continuous combinatorics studies large (dense) combinatorial structures by encoding them in a "continuous" limit object, which is amenable to tools from analysis, topology, measure theory, etc. The syntactic/algebraic approach of "flag algebras" (Razborov '07) to the subject has gained considerable attention in the last years due to its applications to extremal combinatorics. More specifically, the semidefinite method of flag algebras provides a hierarchy of semidefinite programs whose optimal values provide asymptotic upper bounds to any extremal combinatorics problem on maximization of a polynomial function of sub-object densities. Furthermore, even though the only theoretical guarantee is that the semidefinite upper bounds converge to the true extremal value, in several extremal combinatorial problems considered in the literature a very low level of the hierarchy provides not only tight bounds but also structural information about extremality.

In the lecture, I will give an introduction to the theory of flag algebras and its semidefinite method.