Symmetry and Turan Sums of Squares

ACO Colloquium
Monday, April 18, 2016 - 15:05
1 hour (actually 50 minutes)
Skiles 006
University of Washington, Seattle, WA
Given a graph H, the Turan graph problem asks to find the maximum number of edges in a n-vertex graph that does not contain any subgraph isomorphic to H. In recent years, Razborov's flag algebra methods have been applied to Turan hypergraph problems with great success. We show that these techniques embed naturally in standard symmetry-reduction methods for sum of squares representations of invariant polynomials.  This connection gives an alternate computational framework for Turan problems with the potential to go further. Our results expose the rich combinatorics coming from the representation theory of the symmetric group present in flag algebra methods. This is joint work with James Saunderson, Mohit Singh and Rekha Thomas.