Sums of Squares in Extremal Combinatorics

Greg Blekherman — Georgia Tech

I will explain how sums of squares in the gluing algebra of partially labelled graphs can be used to prove graph density inequalities in extremal combinatorics. This is the essence of semidefinite method of Lovasz and Szegedy, and also Cauchy-Schwartz calculus of Razborov.  I will introduce the sums of squares method, do several examples of sums of squares proofs, and then present simple explicit inequalities that show strong limitations of the sums of squares method. No background in combinatorics is necessary.  This is joint work with Annie Raymond, Mohit Singh and Rekha Thomas.