香蕉视频

Title: Simple Graph Density Inequalities with no Sum of Squares Proofs

Abstract: Establishing inequalities among graph densities is a central pursuit in extremal graph theory. One way to certify the nonnegativity of a graph density expression is to write it as a sum of squares or as a rational sum of squares. In this talk, we will explore how one does so and we will then identify simple conditions under which a graph density expression cannot be a sum of squares or a rational sum of squares. These results extend to the powerful frameworks of flag algebras by Razborov and graph algebras by Lov谩sz and Szegedy. This is joint work with Greg Blekherman, Mohit Singh, and Rekha Thomas.