Flag Algebras: An Interim Report
Presenter
September 11, 2014
Keywords:
- Extremal combinatorics
MSC:
- 05Dxx
Abstract
Flag Algebras is a general method for proving results in asymptotic
extremal combinatorics that can be loosely described as ``systematic counting based on semi-definite programming''.
The concrete results proven via this method can be (again, loosely) classified into two groups of unequal size. Brute-force
applications use counting only; the role of a human being reduced to finding a tractable problem and doing a bit of programming.
In other applications of the method, more advanced concepts and tools from the general theory are used to help in finding
a ``flag algebra-assisted'' proof.
This talk will mostly be a survey of concrete results in extremal combinatorics obtained with the help of flag algebras provided
in either of these two modes. But instead of giving a plain and unannotated list of results, we will try to divide our account into several
connected stories that often include historical background, motivations and results obtained via other methods.