Given a graph H, the Turán 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 Turán 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 Turán 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.