Flag Algebras: An Interim Report

Thursday, September 11, 2014 - 2:00pm - 2:50pm
Keller 3-180
Alexander Razborov (University of Chicago)
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.
MSC Code: