UW-PIMS Mathematics Colloquium: Rekha Thomas

  • Date: 11/22/2019
  • Time: 15:30
Rekha Thomas, University of Washington

University of Washington


Graph Density Inequalities and Sums of Squares


Many results in extremal graph theory can be formulated as inequalities on graph densities. While many inequalities are known,many more are conjectured. A standard tool to establish an inequality is to write the expression whose nonnegativity needs to be certified, as a sum of squares. This technique has had many successes but also limitations. In this talk I will describe new restrictions that show that several simple inequalities cannot be certified by sums of squares. These results extend to the powerful frameworks of flag algebras by Razborov and graph algebras by Lovasz and Szegedy. Joint work with Greg Blekherman, Annie Raymond, and Mohit Singh.

Other Information: 

Location: GWN 201


For further information on the UW-PIMS Mathematics Colloquium, please refer to their website.