Turan's Problem

Start: 03/23/2016 - 4:15pm
End  : 03/23/2016 - 5:15pm


Annie Raymond (University of Washington)


What is the maximum number of edges in a graph on n vertices without triangles? Mantel's answer in 1907 that at most half of the edges can be present started a new field: extremal combinatorics. More generally, what is the maximum number of edges in a n-vertex graph that does not contain any subgraph isomorphic to H? What about if you consider hypergraphs instead of graphs? We will explore different strategies to attack such problems, calling upon combinatorics, integer programming, semidefinite programming and flag algebras. We will conclude with some recent work where we embed the flag algebra techniques in more standard methods.


This is joint work with Mohit Singh and Rekha Thomas.

Argue Auditorium, Millikan, Pomona College