MATH Seminar

Title: Semidefinite programming in extremal graph theory
Seminar: Combinatorics
Speaker: Florian Pfender of The University of Colorado, Denver
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2014-11-03 at 4:00PM
Venue: W302
Download Flyer
Abstract: Razborov developed in 2007 the theory of flag algebras. Within this theory, densities of small substructures in large combinatorial structures can be described and computed. His so called "plain flag algebra method" uses semidefinite programming to optimally combine a large number of true inequalities to get bounds on densities in many contexts.\\ \\ One context the method can be used in is the inducibility of graphs. We are looking to maximize the number of induced copies of a given small graph in a very large graph. Whenever the extremal graph to a problem has a simple blow-up structure, the plain method often works very well. But when the structure is more complicated, the bounds tend to get weaker. We recently expanded the plain method to be able to deal with an iterated blow-up structure, which often appears as extremal construction for inducibility questions.