Title: Razborov's flag algebras: Ten years on
| Speaker: | Sergey Norin |
| Affiliation: | McGill University |
| Room: | MC 5501 |
Abstract:
Many of the classical results in extremal combinatorics were obtained by ingenious application of elementary techniques, such as induction and Cauchy-Schwarz inequality. In 2007 Razborov introduced the language of flag algebras, which encodes these techniques and in some cases allows to computerize the search for a solution. Razborov's flag algebras have since been used in over a hundred papers. However, some of the most tantalizing open problems in the area have so far withstood the attack.
We will survey the progress in applications of flag algebras and discuss some of the challenges, focusing on the results surrounding the Caccetta-Haggkvist conjecture and Erdos's conjecture on bipartitions of triangle-free graphs.
The talk is based in part on joint work with Daniel Kral'. Hamed Hatami, Jan Hladky, Ping Hu, Bernard Lidicky, Taísa Martins, Alexander Razborov, Yue Ru Sun and Jan Volec.