- Series
- Graph Theory Seminar
- Time
- Thursday, October 11, 2018 - 12:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Greg Blekherman – Georgia Tech
- Organizer
- Xingxing Yu

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.