Videos

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.