Limitations of Sums of Squares Method for Turan Problems

Graph Theory Seminar
Thursday, October 11, 2018 - 12:00pm
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech
 A sum of squares of real numbers is always nonnegative. This elementary observation is quite powerful, and can be used to prove graph density inequalities in extremal combinatorics, which address so-called Turan problems. This is the essence of semidefinite method of Lov\'{a}sz and   Szegedy, and also Cauchy-Schwartz calculus of Razborov. Here multiplication and addition take place in the gluing algebra of partially  labelled graphs. This method has been successfully used on many occasions and has also been extensively studied theoretically. There are two  competing viewpoints on the power of the sums of squares method. Netzer and Thom refined a Positivstellensatz of Lovasz and Szegedy by  showing that if f> 0 is a valid graph density inequality, then for any a>0 the inequality f+a > 0 can be proved via sums of squares. On the  other hand,  Hatami and Norine showed that testing whether a graph density inequality f > 0 is valid is an undecidable problem, and also provided explicit but  complicated examples of inequalities that cannot be proved using sums of squares. 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. This  is joint work in progress with Annie Raymond, Mohit Singh and Rekha Thomas.