Graphs & Matroids- Kris Siy

Thursday, November 29, 2018 3:30 pm - 3:30 pm EST (GMT -05:00)

Title: Flag algebras and subgraph density problems

Speaker: Kris Siy
Affiliation: University of Waterloo
Room: MC 5417

Abstract: Flag algebras are a tool introduced by Razborov in 2007 that has since been successfully used to approach or solve many problems in asymptotic extremal combinatorics. In particular, flag algebras give us a systematic framework generalising counting techniques in graph theory that allows us to computationally tackle problems about subgraph densities. With this in mind, this talk will motivate the study of and introduce the construction of flag algebras from the ground up, using Mantel's theorem as a guiding example. We will also briefly introduce the semidefinite method, which uses flag algebras to transform subgraph density problems into computationally approachable semidefinite programming problems.