THIS SITE

Information for

Tutte Distinguished Lecture - Sergey NorinExport this event to calendar

Friday, November 2, 2018 — 3:30 PM EDT

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.

Location 
MC - Mathematics & Computer Building
5501
200 University Avenue West
Waterloo, ON N2L 3G1
Canada