Conférencier: Annie Raymond (UMass Amherst)

Abstract: Establishing inequalities among graph densities is a central pursuit in extremal combinatorics. A standard tool to certify the nonnegativity of a graph density expression is to write it as a sum of squares. We identify a simple condition under which a graph density expression cannot be a sum of squares. Using this result, we prove that the Blakley-Roy inequality does not have a sum of squares certificate when the path length is odd. We also show that the same Blakley-Roy inequalities cannot be certified by sums of squares using a multiplier of the form one plus a sum of squares. These results answer two questions raised by Lovász. This is joint work with Greg Blekherman, Mohit Singh and Rekha Thomas.