\documentclass[ALCO,Unicode]{cedram} %\OneNumberAllTheorems %Packages \usepackage{graphicx} \usepackage{amssymb,amsmath,color} \usepackage{stmaryrd} \usepackage{dsfont} \usepackage{mathrsfs} \usepackage{enumitem} \usepackage{color} \usepackage{tikz} \usepackage{pgf} \usepackage{genyoungtabtikz} \usepackage{bm} %%%%Newcommands \newcommand{\RR}{\mathbb{R}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\CC}{\mathbb{C}} \newcommand{\XX}{\mathcal{X}} \newcommand{\PSD}{\mathcal{S}_+} \newcommand{\rank}{\textup{rank}\,} \newcommand{\rankplus}{\textup{rank}_+\,} \newcommand{\rankpsd}{\textup{rank}_{\textup{psd}}\,} \newcommand{\sqrtrank}{\textup{rank}_{\! \! {\sqrt{\ }}}\,} \newcommand{\diag}{\textup{diag}} \newcommand{\supp}{\textup{supp}} \newcommand{\conv}{\textup{conv}} \newcommand{\cone}{\textup{cone}} \newcommand{\xx}{\mathbf x} \newcommand{\onevec}{\mathbbm{1}} \renewcommand{\S}{\mathcal{S}} \newcommand{\pd}{\mathsf{d}} \newcommand{\pp}{\mathsf{p}} \newcommand{\EE}{\mathbb{E}} \newcommand{\Hzero}[0]{ \resizebox{0.58cm}{0.35cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm] (1) {}; \node[fill=black, circle, minimum size=0.3cm] (2) [below left of=1] {}; \node[fill=black, circle, minimum size=0.3cm] (3) [below right of=1] {}; \end{tikzpicture}}} \newcommand{\Hone}[0]{ \resizebox{0.58cm}{0.35cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm] (1) {}; \node[fill=black, circle, minimum size=0.3cm] (2) [below left of=1] {}; \node[fill=black, circle, minimum size=0.3cm] (3) [below right of=1] {}; \draw (2)--(1); \end{tikzpicture}}} \newcommand{\Htwo}[0]{ \resizebox{0.58cm}{0.35cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm] (1) {}; \node[fill=black, circle, minimum size=0.3cm] (2) [below left of=1] {}; \node[fill=black, circle, minimum size=0.3cm] (3) [below right of=1] {}; \draw (2)--(1)--(3); \end{tikzpicture}}} \newcommand{\Hthree}[0]{ \resizebox{0.58cm}{0.35cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm] (1) {}; \node[fill=black, circle, minimum size=0.3cm] (2) [below left of=1] {}; \node[fill=black, circle, minimum size=0.3cm] (3) [below right of=1] {}; \draw (2)--(1)--(3)--(2); \end{tikzpicture}}} \newcommand\nminusone{n-1} \newcommand{\ms}[1]{\color{red}Mohit: #1\color{black}} \newcommand{\todo}[1]{\vspace{5 mm}\par \noindent \marginpar{\textsc{ToDo}} \framebox{\begin{minipage}[c]{0.95 \textwidth} \tt #1 \end{minipage}}\vspace{5 mm}\par} \newcommand{\cherries}[0]{ \resizebox{0.58cm}{0.35cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm] (1) {}; \node[fill=black, circle, minimum size=0.3cm] (2) [below left \llbracketof=1] {}; \node[fill=black, circle, minimum size=0.3cm] (3) [below right of=1] {}; \draw (2)--(1)--(3); \end{tikzpicture}}} \newcommand{\coloredcherries}[0]{ \resizebox{0.58cm}{0.35cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm] (1) {}; \node[fill=black, circle, minimum size=0.3cm] (2) [below left of=1] {}; \node[fill=black, circle, minimum size=0.3cm] (3) [below right of=1] {}; \draw[thick] (2)--(1); \draw[red, thick] (1)--(3); \end{tikzpicture}}} \newcommand{\coloredtwodisjointedges}[0]{ \resizebox{0.4cm}{0.35cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm] (1) {}; \node[fill=black, circle, minimum size=0.3cm] (2) [below of=1] {}; \node[fill=black, circle, minimum size=0.3cm] (3) [right of=1] {}; \node[fill=black, circle, minimum size=0.3cm] (4) [below of=3] {}; \draw[thick] (2)--(1); \draw[red, thick] (4)--(3); \end{tikzpicture}}} \newcommand{\coloreddoublededge}[0]{ \resizebox{0.15cm}{0.35cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm] (1) {}; \node[fill=black, circle, minimum size=0.3cm] (2) [below of=1] {}; \draw[double, thick] (2)--(1); \draw[red, thick] (2)--(1); \end{tikzpicture}}} \newcommand{\labeledHone}[3]{%top label, bottom left label, bottom right label} \resizebox{0.8cm}{0.4cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#2}}] (2) [below left of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#3}}] (3) [below right of=1] {}; \draw (2)--(1); \end{tikzpicture}}} \newcommand{\labeledcherries}[3]{%top label, bottom left label, bottom right label} \resizebox{0.8cm}{0.4cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#2}}] (2) [below left of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#3}}] (3) [below right of=1] {}; \draw (2)--(1)--(3); \end{tikzpicture}}} \newcommand*{\flagnotflag}[4]{%top label, bottom left label, bottom right label} \resizebox{0.8cm}{0.6cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#2}}] (2) [below left of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#3}}] (3) [below right of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#4}}] (4) [below of=3] {}; \draw (2)--(1)--(3)--(4); \end{tikzpicture}}} \newcommand{\qexample}[4]{%top label, bottom left label, bottom right label} \resizebox{0.8cm}{0.6cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#2}}] (2) [below of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#3}}] (3) [right of=2] {}; \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#4}}] (4) [right of=1] {}; \draw (1)--(2)--(3)--(4)--(1); \end{tikzpicture}}} \newcommand{\notflag}[4]{%top label, bottom left label, bottom right label} \resizebox{0.8cm}{0.6cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#2}}] (2) [below left of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#3}}] (3) [below right of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#4}}] (4) [below of=3] {}; \draw (3)--(2)--(1)--(3)--(4); \end{tikzpicture}}} \newcommand{\labeledclaw}[4]{%top label, bottom left label, bottom middle label, bottom right label} \resizebox{0.8cm}{0.6cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#2}}] (2) [below left of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=below:\Huge{\textbf{#3}}] (3) [below of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#4}}] (4) [below right of=1] {}; \draw (2)--(1)--(3)--(1)--(4); \end{tikzpicture}}} \newcommand{\labeledtriangle}[3]{%top label, bottom left label, bottom right label} \resizebox{0.8cm}{0.4cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#2}}] (2) [below left of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#3}}] (3) [below right of=1] {}; \draw (2)--(1)--(3); \end{tikzpicture}}} \newcommand{\vedge}[0]{ \resizebox{0.12cm}{0.35cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm] (1) {}; \node[fill=black, circle, minimum size=0.3cm] (2) [below of=1] {}; \draw (2)--(1); \end{tikzpicture}}} \newcommand{\labeledvedge}[2]{%top label, bottom label \resizebox{0.32cm}{0.4cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#2}}] (2) [below of=1] {}; \draw (2)--(1); \end{tikzpicture}}} \newcommand{\labeledvnonedge}[2]{%top label, bottom label \resizebox{0.32cm}{0.4cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#2}}] (2) [below of=1] {}; \end{tikzpicture}}} \newcommand{\hedge}[0]{ \resizebox{0.4cm}{0.35cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm] (1) {}; \node[fill=black, circle, minimum size=0.3cm] (2) [right of=1] {}; \draw (2)--(1); \end{tikzpicture}}} \newcommand{\labeledhedge}[2]{%top label, bottom label \resizebox{0.4cm}{0.25cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=below:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=below:\Huge{\textbf{#2}}] (2) [right of=1] {}; \draw (2)--(1); \end{tikzpicture}}} \newcommand{\labeledleftwave}[3]{%left label, middle label, right label \resizebox{0.8cm}{0.4cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=below:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=below:\Huge{\textbf{#2}}] (2) [right of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=below:\Huge{\textbf{#3}}] (3) [right of=2] {}; \draw (1)--(2); \draw [thick] (2,0) arc (60:120:2cm); \end{tikzpicture}}} \newcommand{\labeledrightwave}[3]{%left label, middle label, right label \resizebox{0.8cm}{0.4cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=below:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=below:\Huge{\textbf{#2}}] (2) [right of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=below:\Huge{\textbf{#3}}] (3) [right of=2] {}; \draw (2)--(3); \draw [thick] (2,0) arc (60:120:2cm); \end{tikzpicture}}} \newcommand{\labeledupdownL}[3]{%top left label, top right label, bottom label \resizebox{0.75cm}{0.45cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#2}}] (2) [right of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#3}}] (3) [below of=1] {}; \draw (3)--(1)--(2); \end{tikzpicture}}} \newcommand{\labeledupdownmirrorL}[3]{%top left label, top right label, bottom label \resizebox{0.75cm}{0.45cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#2}}] (2) [right of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#3}}] (3) [below of=1] {}; \draw (3)--(2)--(1); \end{tikzpicture}}} \newcommand{\labeledV}[3]{%top left label, top right label, bottom label \resizebox{0.75cm}{0.45cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=right:\Huge{\textbf{#2}}] (2) [right of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=left:\Huge{\textbf{#3}}] (3) [below of=1] {}; \draw (2)--(3)--(1); \end{tikzpicture}}} \newcommand{\labeledstraight}[3]{%left label, middle label, right label \resizebox{0.8cm}{0.33cm}{ \begin{tikzpicture} \node[fill=black, circle, minimum size=0.3cm, label=below:\Huge{\textbf{#1}}] (1) {}; \node[fill=black, circle, minimum size=0.3cm, label=below:\Huge{\textbf{#2}}] (2) [right of=1] {}; \node[fill=black, circle, minimum size=0.3cm, label=below:\Huge{\textbf{#3}}] (3) [right of=2] {}; \draw (1)--(2)--(3); \end{tikzpicture}}} %%%Theorems %\theoremstyle{plain} %\newtheorem{theorem}{Theorem}[section] %\newtheorem{conjecture}[theorem]{Conjecture} %\newtheorem{corollary}[theorem]{Corollary} %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{example}[theorem]{Example} %\newtheorem{axiom}{Axiom} % %\theoremstyle{definition} %\newtheorem{definition}{Definition}[section] % %\theoremstyle{remark} %\newtheorem{remark}{Remark}[section] %\newtheorem*{notation*}{Notation} % %\usepackage[destlabel]{hyperref} \begin{document} \title{Symmetry in Tur{\'a}n sums of squares polynomials from flag algebras} \author{\firstname{Annie} \lastname{Raymond}} \address{Department of Mathematics and Statistics\\ University of Massachusetts Amherst\\ Amherst, MA 01003} \email{raymond@math.umass.edu} \author{\firstname{Mohit} \lastname{Singh}} \address{H. Milton Stewart School of Industrial and Systems Engineering\\ Georgia Institute of Technology,\\ Atlanta, GA 30332} \email{mohit.singh@isye.gatech.edu } \author{\firstname{Rekha} \middlename{R.} \lastname{Thomas}} \address{Department of Mathematics\\ University of Washington\\ Box 354350\\ Seattle, WA 98195} \email{rrthomas@uw.edu} \keywords{sums of squares, semidefinite programming, flag algebras, extremal combinatorics, symmetry} %% Mathematical classification (2000) %% This will not be printed but can be useful for database search \subjclass{05D99, 12D15, 90C22} \begin{abstract} Tur\'an problems in extremal combinatorics ask to find asymptotic bounds on the edge densities of graphs and hypergraphs that avoid specified subgraphs. The theory of flag algebras proposed by Razborov provides powerful methods based on semidefinite programming to find sums of squares that establish edge density inequalities in Tur\'an problems. Working with polynomial analogs of the flag algebra entities, we prove that such sums of squares created by flag algebras can be retrieved from a restricted version of the symmetry-adapted semidefinite program proposed by Gatermann and Parrilo. This involves using the representation theory of the symmetric group for finding succinct sums of squares expressions for invariant polynomials. The connection reveals several combinatorial and structural properties of flag algebra sums of squares, and offers new tools for Tur\'an and other related problems. \end{abstract} \maketitle \section{Introduction} The \emph{Tur{\'a}n problem} from extremal combinatorics asks the following question: given a graph $A$, what is the maximum number of edges in a graph on $n$ vertices not containing $A$ as a subgraph? Tur{\'a}n \cite{Turan} answered this question for $A=K_s$, the complete graph on $s$ vertices, generalizing a classical result of Mantel~\cite{Mantel07} for triangle-free graphs, and establishing the field of extremal graph theory. In general, for any graph $A$, Erd\"os and Stone~\cite{ES46} identified the maximum possible density of edges in any $A$-free graph asymptotically. The \emph{hypergraph Tur{\'a}n problem} asks the same question for hypergraphs, but the current understanding of this problem is far from satisfactory. In particular, even asymptotically, tight bounds on the maximum number of edges in a $n$-vertex $3$-uniform hypergraph\footnote{A $r$-uniform hypergraph has (hyper)edges of size $r$.} not containing a complete graph of size four is not known. A variety of general techniques have been developed to prove bounds for this long-standing hypergraph Tur{\'a}n problem; see for example \cite{ChungLu, FranklFuredi, LuZhao, Pikhurko, Sidorenko, Keevash11} for a survey. Recently, semidefinite programming methods arising from the powerful theory of \emph{flag algebras} introduced by Razborov~\cite{RazborovFlagAlgebras} have led to significant progress on this problem. Indeed, many of the previous bounds can be proven via this technique and several new results giving the tightest known bounds have been obtained~\cite{Razborov10,Razborov13,Razborov14,Falgas-RavryVaughan}. For instance, Razborov in \cite{Razborov10} proved that the (maximum) asymptotic edge density of a $3$-uniform hypergraph without a $4$-clique is 0.561666 (Tur\'an~\cite{Turan61} conjectured it to be $\frac{5}{9}$). Moreover, he also showed in the same paper that, if one forbids an additional subgraph, then the asymptotic edge density is indeed $\frac{5}{9}$. Razborov's method relies on establishing inequalities involving densities of suitably chosen subgraphs in any $n$-vertex graph/hypergraph. This is done by lower bounding density expressions with a scalar sum of squares (sos) coming from flags. A suitable sos is found by formulating a semidefinite program (SDP) whose size depends on the flags that are used. The key to the success of this method is that the size of the SDP is thus independent of the number of vertices, which is particularly helpful for asymptotic results. However, deciding which flags are needed to construct the flag sos expressions is an art. Our work is motivated by the basic question as to whether there is a fundamental connection between Razborov's scalar flag sos methods and the more standard sos theory for polynomials. Expressing a polynomial with real coefficients as a sos of polynomials in order to certify its nonnegativity is a well-established technique in real algebraic geometry going back at least to the 19th century. In recent years, these ideas have acquired new life following the realization that sos polynomials can be found via the modern tool of semidefinite programming which has led to remarkable progress in optimization and algorithm design. For an introduction to these methods, see one of \cite[Chapters 1 \& 2]{BPTSIAMBook} or \cite{LaurentSurvey, Parrilo}. In this paper, we show that indeed there is a deep connection between the sos methods coming from flags and those for polynomials in real algebraic geometry. We show that symmetry-reduction in polynomial optimization is precisely the right framework through which this relationship can be established. This brings in tools from the representation theory of the symmetric group, highlighting the many combinatorial features of flag sos expressions. Symmetry-reduction in polynomial optimization, or more generally semidefinite programming, is a powerful technique and has been useful in many settings \cite {Schrijver79, SchrijverInvariantSDPSurvey, associationSchemesSurvey, GatermannParrilo}. When a nonnegative polynomial is invariant under the action of a finite group, the representation theory of the group can be used to simplify the SDP used to obtain the sos certificate for its nonnegativity. In \cite{GatermannParrilo}, Gatermann and Parrilo show that in this invariant setting the original SDP breaks into several smaller (but coupled) SDPs, each indexed by an \emph{irreducible representation} of the group, leading to tremendous computational savings. We appeal to this framework to establish our results. Our main technical result shows that the flag algebra method for establishing graph density inequalities embeds naturally in a restricted version of the Gatermann-Parrilo symmetry-adapted SDP. Our results rely on the rich combinatorics hidden in the sos expressions coming from flag algebras that we expose using the representation theory of the symmetric group. We give a precise description of the symmetry-reduced SDP in terms of the irreducible representations of the symmetric group and show that only certain irreducibles are needed. Consequently, we prove that the size of this SDP is independent of the number of vertices in the associated graphs, as in Razborov's methods. This offers a systematic way of establishing graph density inequalities, and more generally, Cauchy-Schwarz proofs coming from flags, through standard sos methods where no sophisticated choices are necessary. \subsection{Our results in detail and the organization of the paper} For notational simplicity, we restrict the exposition in this paper to Tur\'an-type problems in the setting of graphs. Our results extend naturally to the broader realm of hypergraphs, digraphs, tournaments, etc, which carry many open problems. In the conclusion of this paper, we will elaborate on the modifications needed for these extensions. Restricting to the setting of graphs, assume that there is only one graph $A$ that must be avoided in a Tur\'an problem. The more general setting of avoiding all graphs in a family is treated similarly. Also, we will work in the setting of avoiding $A$ as an {\em induced} subgraph. Note that this setting is general, and that the non-induced setting can be modeled through it by forbidding every induced graph containing $A$. The main technical challenge in Tur\'an problems is to show an upper bound on the edge density of any $A$-free graph. The first step in linking flag algebra methods for Tur\'an problems to the symmetry-reduction techniques of \cite{GatermannParrilo} is to view graph density expressions as polynomials modulo an ideal, and flag sos expressions as polynomial sos expressions. This is done in Section~\ref{sec:FlagAlgebras}. We begin with a few basic definitions. For a fixed positive integer $n$, the polynomials we work with lie in $\RR[{\bf x}] := \RR[\mathsf{x}_{ij} \,:\, 1 \leq i < j \leq n]$, the polynomial ring over $\RR$ in $n \choose 2$ variables indexed by the edges in the complete graph $K_n$. If $A$ denotes the graph that must be avoided in the Tur\'an problem we are interested in, then the ideal we need, $\mathscr{I}_n^A$, is precisely the set of polynomials in $\RR[{\bf x}]$ that vanish on the characteristic vectors of all graphs on $n$ vertices that do not contain $A$ as an induced subgraph. A polynomial is nonnegative on this finite set of characteristic vectors if and only if it is equivalent to a sos polynomial {\em modulo} $\mathscr{I}_n^A$. Two polynomials $\mathsf{f}$ and $\mathsf{g}$ are equivalent modulo $\mathscr{I}_n^{{A}}$ if and only if $\mathsf{f}-\mathsf{g} \in \mathscr{I}_n^{{A}}$, written as $\mathsf{f} \equiv \mathsf{g}$ mod $\mathscr{I}_n^{{A}}$. This equivalence relation differentiates between functions on the zeros of $\mathscr{I}_n^{{A}}$, i.e., $\mathsf{f} \equiv \mathsf{g}$ mod $\mathscr{I}_n^{{A}}$ if and only if $\mathsf{f}(\bm{v}) = \mathsf{g}(\bm{v})$ for every zero $\bm{v}$ of $\mathscr{I}_n^{{A}}$. Therefore, if $\mathsf{g} = \sum \mathsf{h}_j^2$ is a sos, then $\mathsf{f}$ is nonnegative on the characteristic vectors of all ${A}$-free graphs on $n$ vertices. Further, we say that $\mathsf{f}$ is $d$-sos mod $\mathscr{I}_n^{{A}}$ if each $\mathsf{h}_j$ has degree at most $d$. Every $d$-sos polynomial has the form $\mathbf{y}^T Q \mathbf{y}$ where $Q$ is a $l\times l$ positive semidefinite (psd) matrix and $\mathbf{y}$ is a $l$-dimensional vector whose coordinates are polynomials of degree at most $d$. This allows us to use semidefinite programming to search for $d$-sos expressions for a given polynomial modulo $\mathscr{I}_n^{{A}}$. In Section~\ref{sec:FlagAlgebras}, we describe the polynomial analogs of the ingredients in a sos proof coming from flag algebras. This allows us to translate flag sos expressions to polynomial sos expressions for density polynomials as shown in Propositions \ref{prop:translation-sos} and \ref{cor:translation-sos}. We illustrate our polynomial translation on Mantel's theorem. The complete proof, including the flag algebra approach for Tur\'an problems, can be found in the Appendix. Given the polynomial formulation, an approach to showing an upper bound on the graph density polynomial is to use the standard sos method in polynomial optimization. This raises several natural questions. Firstly, whether flag sos expressions can be retrieved via this approach? Secondly, whether the size of the SDP formulated in this approach will be independent of $n$ as in the flag algebra framework? In this paper, we answer both questions affirmatively. A priori, searching for a $d$-sos proof leads to a SDP formulation whose size grows with $n$. The first step in establishing our result is to notice that the graph density polynomial whose nonnegativity we need to establish is invariant under an action induced by the symmetric group $\mathfrak{S}_n$ on $n$ letters acting on the vertices of $K_n$. Therefore, one can use the symmetry-reduction techniques in \cite{GatermannParrilo} to simplify the computational cost of searching for its sos certificate. This in turn relies on the representation theory of $\mathfrak{S}_n$; we explain the basics of this theory in Section~\ref{sec:representation theory basics}. We then describe the symmetry-reduction strategy of \cite{GatermannParrilo} in Section~\ref{sec:GP method} which breaks the SDP that searches for a sos expression into smaller SDPs that are indexed by the irreducible representations of $\mathfrak{S}_n$ or, equivalently, the partitions of $n$. This section is largely expository but it is crucial for understanding our main results in Section~\ref{sec:main results}. For efficiency, we tailor all discussion of \cite{GatermannParrilo} to $\mathfrak{S}_n$ which in turn creates a new set of combinatorial tools for problems to which flag sos methods apply. In Section~\ref{sec:main results}, we come to our main results. Suppose we fix a maximum degree $d$ for the sos polynomials we are searching for, and let $\RR[{\bf x}]_{\leq d}$ denote the vector space of all polynomials in $\RR[{\bf x}]$ of degree up to $d$. The group $\mathfrak{S}_n$ breaks $\RR[{\bf x}]_{\leq d}$ into a direct sum of subspaces indexed by the partitions of $n$, called the isotypic decomposition of $\RR[{\bf x}]_{\leq d}$. We first establish that the atomic pieces of the sos polynomials that come out of flag algebras are invariant with respect to the {\em row group} of a {\em tableau} defined from the flags that are chosen by the flag algebra method (Theorem~\ref{lcorbits}). Next, using the theory of restricted representations, we decide which subset of subspaces in the isotypic decomposition of $\RR[{\bf x}]_{\leq d}$ contain the polynomials in a flag algebra sos in their span. Finally, we show that the sos expressions from flag algebras can be retrieved from the Gatermann-Parrilo SDP restricted to those partitions that survive in the previous step. The key point to note here is that the number of partitions indexing these necessary subspaces is not a function of $n$, but rather of $d$. So if we fix $d$ and let $n$ go to infinity, the number of partitions, and the sizes of the corresponding SDPs, will stay fixed. This answers the two questions raised above and links flag algebra methods to symmetry-reduction in semidefinite programming. Under the usual action of $\mathfrak{S}_n$ on the polynomial ring $\RR[x_1, \ldots, x_n]$, \cite{Thorsten} has also shown that one can get sos expressions for symmetric polynomials whose size is independent of $n$. In Section~\ref{sec:Mantel1}, we illustrate our main results on the Mantel example. We will see that for any $n$, just two specific partitions are enough to obtain the sos expression from flag algebras. Since there are many simple proofs of Mantel's result, the goal of using this example is simply to illustrate the chain of results that make up this paper. It is both simple and rich enough for this purpose. We conclude in Section~\ref{sec:conclusion} where we explain how to apply our techniques in other settings such as directed graphs, hypergraphs and tournaments, and also discuss different future directions for this work. %\vspace{0.1cm} %\noindent{\bf Acknowledgements}. We thank Greg Blekherman for several important inputs to this paper relating to representation theory. They came at crucial junctures and helped us along greatly. We also thank Andrew Berget, Monty McGovern, Pablo Parrilo, James Pfeiffer, Paul Smith and Vasu Tewari for helpful conversations and suggestions. %We also thank the referees of this paper for their valuable comments which have improved the content and exposition. \section{Sums of squares from flag algebras} \label{sec:FlagAlgebras} In this section we present the polynomial analogs of Razborov's flag algebra method for proving inequalities on graph densities. As mentioned in the Introduction, we restrict our attention to graphs. For generalizations, see the conclusion of the paper. The key new feature distinguishing this work from the literature (\cite{Falgas-RavryVaughan, RazborovFlagAlgebras, Razborov14}) is that we think of all densities as polynomials that can be evaluated on characteristic vectors of graphs. If the reader is unfamiliar with flag algebras, we highly recommend reading Section~2.2 of \cite{Falgas-RavryVaughan} first to see a concrete application of the flag method to Mantel's theorem. The polynomial version may appear more difficult to parse at first but they are simply functions on the (finite) set of characteristic vectors of the graphs allowed by the problem that evaluate to density expressions as in \cite{Falgas-RavryVaughan} and \cite{Razborov10}. The polynomial translation illustrates how certificates based on flag algebras can be interpreted as polynomial sos proofs. The polynomials appearing in Razborov's sos proofs and their specific symmetries will be key in obtaining our main results efficiently via the Gatermann-Parrilo framework introduced in Section~\ref{sec:GatermannParrilo}. To illustrate the method on an example, we use the polynomial version of flag algebras to prove Mantel's theorem at the end of this section. Consider the general problem of certifying an inequality involving graph densities over all graphs with a certain property. We first fix $n$, the number of vertices in our graphs. Let $\mathcal{G}$ be the set of all undirected graphs up to isomorphism with the desired property, and let $\mathcal{G}_n$ be the graphs in $\mathcal{G}$ that have $n$ vertices. Also, let $V(G)$ and $E(G)$ denote the sets of vertices and edges of $G$. We represent a graph $G$ by its characteristic vector $\mathds{1}_G \in \{0,1\}^{\binom{n}{2}}$ whose $ij$-th coordinate is $1$ if and only if $\{i,j\}\in E(G)$. Throughout, we work with the polynomial ring $\RR[{\mathbf x}] = \RR[\mathsf{x}_{ij}:1 \leq i < j \leq n]$ described earlier. Fix an integer $m$ such that $m0$ and $\lambda_1+\ldots+\lambda_t=n$. A key partition for us is the \emph{hook partition} for which all the parts but one are $1$; we denote the hook partition with $k+1$ parts as $(n-k,1^k)$. There is a lexicographic order on the partitions of $n$; for $\bm{\lambda}=(\lambda_1, \ldots, \lambda_{t_1})$ and $\bm{\mu}=(\mu_1,\ldots, \mu_{t_2})$, we write $\bm{\lambda}\geq_{\textup{lex}} \bm{\mu}$ if the vector $(\lambda_1, \ldots, \lambda_{t_1})$ is lexicographically greater than or equal to the vector $(\mu_1, \ldots, \mu_{t_2})$. A partition $\bm{\lambda}$ has a shape (Young diagram) with rows of size $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_t$. A {\em tableau} of shape $\bm{\lambda}$, denoted as $\tau_{\bm{\lambda}}$, is a filling of the boxes in the diagram of ${\bf \lambda}$ by the numbers $1, \ldots,n$. The tableau is {\em standard} if the numbering increases along each row and column. The {\em row group} of a tableau $\tau_{\bm{\lambda}}$ is the subgroup of $\mathfrak{S}_n$ defined as $$\mathfrak{R}_{\tau_{\bm{\lambda}}} := \{ \mathfrak{s} \in \mathfrak{S}_n: \mathfrak{s} \textup{ fixes the set of numbers in each row of } \tau_{\bm{\lambda}}\}.$$ Note that this group is isomorphic to $\mathfrak{S}_{\bm{\lambda}} := \mathfrak{S}_{\lambda_1} \times \cdots \times \mathfrak{S}_{\lambda_t}$. We will show that the polynomials $\mathsf{p}_F^\theta$ from \eqref{dthetaf} are invariant under a particular row group for all flags $F\in \mathcal{F}_l^\sigma$. Recall that these polynomials were defined from the choice of a $\sigma$-flag $F$ of size $l$, and an injective map $\theta\in\textup{Inj}([k],[n])$. In particular, no partitions, tableaux or row groups were involved. We first present an example. \begin{example} \label{exorbit_part2} Consider $n=5$ and the hook partition $\bm{\lambda}=(2,1,1,1)$. The row group of the tableau $$\tau_{\bm{\lambda}}=\young(45,1,2,3) \,\,\,\,\textup{ is }\,\,\,\, \mathfrak{R}_{\tau_{\bm{\lambda}}}=\{1, (4,5)\}.$$ Suppose we choose the type $\sigma = \labeledcherries{1}{2}{3}$, set $l=4$, and consider the $\sigma$-flag $F =\labeledclaw{1}{2}{3}{}$. Since $n=5$, assume $\theta \,:\, [3] \rightarrow [5]$ is such that $\theta(1)=1$, $\theta(2)=2$ and $\theta(3)=3$. The set $\textup{Inj}_\theta(V(F),[5])$ contains two maps, both preserving $\theta$ and hence, sending $1,2,3$ to themselves. Suppose $\alpha_1 \in \textup{Inj}_\theta(V(F),[5])$ sends the unlabeled vertex in $F$ to $4$ and $\alpha_2 \in \textup{Inj}_\theta(V(F),[5])$ sends it to $5$. Using the formula in \eqref{eq:qhf}, one can see that \begin{align*} &\mathsf{q}^{\alpha_1}_F = \mathsf{x}_{12}\mathsf{x}_{13}\mathsf{x}_{14}(1-\mathsf{x}_{23})(1-\mathsf{x}_{24})(1-\mathsf{x}_{34}), \textup{ and }\\ &\mathsf{q}^{\alpha_2}_F = \mathsf{x}_{12}\mathsf{x}_{13}\mathsf{x}_{15}(1-\mathsf{x}_{23})(1-\mathsf{x}_{25})(1-\mathsf{x}_{35}). \end{align*} Similarly, from \eqref{dthetaf} we get that $$\mathsf{p}_F^\theta = \frac{1}{|\textup{Inj}_\theta(V(F),[n])|}\sum_{\alpha \in\textup{Inj}_\theta(V(F),[n])} \mathsf{q}^\alpha_F= \frac{1}{2} (\mathsf{q}^{\alpha_1}_F + \mathsf{q}^{\alpha_2}_F).$$ Note that $\mathsf{p}_F^\theta$ is invariant under $\mathfrak{R}_{\tau_{\bm{\lambda}}}$. Indeed, the action $1\in \mathfrak{R}_{\tau_{\bm{\lambda}}}$ applied to $\mathsf{p}_F^\theta$ doesn't change anything, and the action $(4,5)\in \mathfrak{R}_{\tau_{\bm{\lambda}}}$ sends $\mathsf{q}^{\alpha_1}_F$ to $\mathsf{q}^{\alpha_2}_F$ and vice-versa, thus leaving $\mathsf{p}_F^\theta$ unchanged. \end{example} We now prove that this observation is not accidental; a polynomial $\pp^{\theta}_F$ is $\mathfrak{R}_{\tau_{\bm{\lambda}}}$-invariant for some tableau $\tau_{\bm{\lambda}}$ of shape ${\bm \lambda}$ where $\bm{\lambda}$ is a specific hook partition. \begin{proposition}\label{pvsorbit} Let $F$ be a $\sigma$-flag where $|\sigma|=k$, and $\theta:[k]\rightarrow [n]$ be an injective map. Consider the hook partition $\bm{\lambda}=(n-k,1^k)$ and a tableau $\tau_{\bm{\lambda}}$ where we fill the first row by numbers from $[n]\setminus\{\theta(i):i\in [k]\}$ in any order, and the $k$ remaining rows of size one with numbers from $\{\theta(i):i\in [k]\}$ in any order. Then the polynomial $\pp^{\theta}_F$ is $\mathfrak{R}_{\tau_{\bm{\lambda}}}$-invariant. \end{proposition} \begin{proof} Consider any $\mathfrak{s}\in \mathfrak{R}_{\tau_{\bm{\lambda}}} \cong \mathfrak{S}_{n-k}$ and $\alpha:V(F)\rightarrow [n]$ in $\textup{Inj}_\theta(V(F),[n])$. Then $(\mathfrak{s}\circ \alpha):V(F)\rightarrow [n]$ is also an injective map preserving $\theta$. Indeed, for any $\alpha\in \textup{Inj}_\theta(V(F),[n])$, the composition gives a map from $\mathfrak{R}_{\tau_{\bm{\lambda}}}\rightarrow \textup{Inj}_\theta(V(F),[n])$ which is $\frac{|\mathfrak{R}_{\tau_{\bm{\lambda}}}|}{|\textup{Inj}_\theta(V(F),[n])|}$-to-one surjective. This is because there are $n-l$ elements of $[n]$ outside the range of $\alpha$ and $\alpha = \mathfrak{s} \circ \alpha$ for any $\mathfrak{s}\in \mathfrak{R}_{\tau_{\bm{\lambda}}}$ that fixes the range of $\alpha$. Since there are $$(n-l)! = \frac{(n-k)!}{(n-k)(n-k-1) \cdots (n-l+1)} = \frac{|\mathfrak{R}_{\tau_{\bm{\lambda}}}|}{|\textup{Inj}_\theta(V(F),[n])|}$$ such permutations $\mathfrak{s}$, we get that the $\mathfrak{R}_{\tau_{\bm{\lambda}}}$-invariant polynomial \begin{align*} \frac{1}{|\mathfrak{R}_{\tau_{\bm{\lambda}}}|} \sum_{\mathfrak{s}\in {\mathfrak{R}_{\tau_{\bm{\lambda}}}}} \mathfrak{s}\cdot\mathsf{q}_F^\alpha=\frac{1}{|\mathfrak{R}_{\tau_{\bm{\lambda}}}|} \cdot \frac{|\mathfrak{R}_{\tau_{\bm{\lambda}}}|}{|\textup{Inj}_\theta(V(F),[n])|} \sum_{\alpha\in \textup{Inj}_\theta(V(F),[n])}\mathsf{q}_F^\alpha =\pp_F^{\theta} \end{align*} by \eqref{dthetaf}, which implies that $\mathsf{p}_F^\theta$ is $\mathfrak{R}_{\tau_{\bm{\lambda}}}$-invariant. \end{proof} \begin{theorem}\label{lcorbits} Each polynomial $\mathsf{r}_j$ in the sos \eqref{deepsos} is invariant under the row group $\mathfrak{R}_{\tau_{\bm{\lambda}}}$ corresponding to the tableau $\tau_{\bm{\lambda}}$ and hook partition $\bm{\lambda}$ as in Proposition~\ref{pvsorbit}. \end{theorem} \proof Since each $\mathsf{r}_j$ is a linear combination of $\mathsf{p}_F^\theta$ with $F\in \mathcal{F}_{l}^\sigma$, and since $\tau_{\bm{\lambda}}$ only depends on $\theta$, all $\mathsf{p}_F^\theta$ for any $F\in \mathcal{F}_{l}^\sigma$ are invariant under the same $\mathfrak{R}_{\tau_{\bm{\lambda}}}$. Therefore, $\mathsf{r}_j$ is also $\mathfrak{R}_{\tau_{\bm{\lambda}}}$-invariant. \qed \begin{remark} Note that the hook $\bm{\lambda}$ in Proposition~\ref{pvsorbit} and Theorem~\ref{lcorbits} only depends on $k$, the size of the type $\sigma$ of the flags $F$ and not on their size $l$. \end{remark} \subsection{\texorpdfstring{$\mathfrak{R}_{\tau_{\bm{\lambda}}}$-invariant polynomials and the isotypic decomposition}{$\mathfrak{R}_{\tau_{\lambda}}$-invariant polynomials and the isotypic decomposition}}\label{sec:razborov-gatermann-parrilo} Our next goal is to show that a $\mathfrak{R}_{\tau_{\bm{\lambda}}}$-invariant polynomial $\mathsf{f}$ lies in the span of certain specific isotypics in the isotypic decomposition \eqref{eq:isotypic decomposition} of $V = \mathbb{R}[\mathbf{x}]_{\leq d}$. We will use this in the next subsection to prove that Razborov's sos can be obtained by restricting the Gatermann-Parrilo SDP to the subblocks indexed by these isotypics/partitions. Recall that the induced $\mathfrak{S}_n$-action we have decomposes $V$ into a direct sum as in \eqref{eq:irreducible decomposition}. Therefore, our polynomial $\mathsf{f} \in V$ decomposes as \begin{align}\label{eq:directsum} \mathsf{f}=\sum_{\bm{\mu} \vdash n} \sum_{i=1}^{m_{\bm{\mu}}} \mathsf{f}_{\bm{\mu},i} \end{align} where $\mathsf{f}_{\bm{\mu},i} \in V_{\bm{\mu}}^i$. Since $\mathsf{f}$ is $\mathfrak{R}_{\tau_{\lambda}}$-invariant, we may assume without loss of generality that each $\mathsf{f}_{\bm{\mu},i}$ in \eqref{eq:directsum} is also $\mathfrak{R}_{\tau_{\lambda}}$-invariant. Indeed, $$ \mathsf{f}= \frac{1}{| \mathfrak{R}_{\tau_{\lambda}} |} \sum_{\mathfrak{s} \in \mathfrak{R}_{\tau_{\lambda}}} \mathfrak{s} \mathsf{f} = \sum_{\bm{\mu} \vdash n} \sum_{i=1}^{m_{\bm{\mu}}} \left( \frac{1}{| \mathfrak{R}_{\tau_{\lambda}} |} \sum_{\mathfrak{s} \in \mathfrak{R}_{\tau_{\lambda}}} \mathfrak{s} \mathsf{f}_{\bm{\mu},i} \right), $$ and since $V_{\bm{\mu}}^i$ is $\mathfrak{R}_{\tau_{\lambda}}$-invariant (because it is $\mathfrak{S}_n$-invariant), $\frac{1}{| \mathfrak{R}_{\tau_{\lambda}} |} \sum_{\mathfrak{s} \in \mathfrak{R}_{\tau_{\lambda}}} \mathfrak{s} \mathsf{f}_{\bm{\mu},i}$ lies in $V_{\bm{\mu}}^i$. In the case when $\mathsf{f}$ is some $\mathsf{r}_j$ in the sos \eqref{deepsos}, we are interested in knowing when a $\mathsf{f}_{\bm{\mu},i}$ is non-zero, or equivalently, in determining which parts of $V$ contain $\mathsf{f}$. For this, we rely on the theory of {\em restricted representations} \cite[Chapter 4]{FultonHarrisBook}. The restricted representation of the subgroup $\mathfrak{R}_{\tau_{\bm{\lambda}}}$ on $V$ is the representation of $\mathfrak{R}_{\tau_{\bm{\lambda}}}$ on $V$ obtained by restricting the $\mathfrak{S}_n$ representation $\vartheta \,:\, \mathfrak{S}_n \rightarrow \textup{GL}(V)$ to the elements of $\mathfrak{R}_{\tau_{\bm{\lambda}}}$. This has the effect of refining the direct sum decomposition in \eqref{eq:irreducible decomposition} since an irreducible $V_{\bm{\mu}}^i$, while being $\mathfrak{R}_{\tau_{\bm{\lambda}}}$-invariant, may not be irreducible with respect to $\mathfrak{R}_{\tau_{\bm{\lambda}}}$ and hence will decompose into irreducible representations of $\mathfrak{R}_{\tau_{\bm{\lambda}}}$. The $\mathfrak{R}_{\tau_{\bm{\lambda}}}$-invariant polynomials in a $V_{\bm{\mu}}^i$ are contained in the copies of the trivial representation of $\mathfrak{R}_{\tau_{\bm{\lambda}}}$ in $V_{\bm{\mu}}^i$. Therefore, the component $ \mathsf{f}_{\bm{\mu},i}$ in \eqref{eq:directsum} is nonzero only if $V_{\bm{\mu}}^i$ contains at least one copy of the trivial representation of $\mathfrak{R}_{\tau_{\bm{\lambda}}}$ in the restricted representation of $\mathfrak{R}_{\tau_{\bm{\lambda}}}$ on $V_{\bm{\mu}}^i$. To characterize such partitions $\bm{\mu}$, we need the following definition. Let $\bm{\lambda}=(\lambda_1,\lambda_2,\ldots, \lambda_t)$ be a partition and $N_{\bm{\lambda}}$ be the sequence containing $\lambda_p$ copies of the number $p$ for $p =1,\ldots,t$. A semistandard tableau of shape $\bm{\mu}$ and type $\bm{\lambda}$ is a tableau of $\bm{\mu}$ with numbers coming from $N_{\bm{\lambda}}$ such that the numbers are non-decreasing along rows and increasing along columns. \begin{example} If $\bm{\lambda}=(4,2,1)$, then $N_{\bm{\lambda}}=(1,1,1,1,2,2,3)$ and the semistandard tableaux of type $\bm{\lambda}$ are \begin{center} \young(1111223) \quad \young(111122,3) \quad \young(111123,2) \vspace{0.2cm} \quad \young(11112,23) \quad \young(11113,22) \quad \young(11112,2,3) \vspace{0.2cm} \quad \young(1111,223)\quad \young(1111,22,3) \end{center} Among these, there is one of shape $(7)$, two of shape $(6,1)$, two of shape $(5,2)$, one of shape $(5,1,1)$, one of shape $(4,3)$, and one of shape $(4,2,1)$. \hfill{\qed} \end{example} The following theorem presented in many books (including in Corollary 4.39 and the discussion following it in \cite{FultonHarrisBook}) is exactly what we need. \begin{theorem}[Young's Rule]\label{YoungsRule} Let $\bm{\lambda}=(\lambda_1,\ldots, \lambda_t)$ and $\bm{\mu}$ be partitions of $n$. The multiplicity of the trivial representation of $\mathfrak{R}_{\tau_{\bm{\lambda}}}$ in the restriction of some irreducible representation $V^i_{\bm{\mu}}$ to $\mathfrak{R}_{\tau_{\bm{\lambda}}}$ is equal to the number of semistandard tableaux of shape $\bm{\mu}$ and type $\bm{\lambda}$. \end{theorem} Note that in \cite{FultonHarrisBook}, this result is given in terms of {\em induced representations}, but by {\em Frobenius reciprocity} \cite[Corollary 3.20]{FultonHarrisBook}, the above is an equivalent version. The number of semistandard tableaux of shape $\bm{\mu}$ and type $\bm{\lambda}$ is called the {\em Kostka number} $K_{\bm{\mu}\bm{\lambda}}$. We need to know when $K_{\bm{\mu}\bm{\lambda}}$ is non-zero, and the following standard fact gives a necessary characterization. \begin{lemma}\label{multzero} If $\bm{\lambda}$ is lexicographically greater than $\bm{\mu}$ or if $\bm{\mu}$ has more parts than $\bm{\lambda}$, then $K_{\bm{\mu}\bm{\lambda}}=0$. \end{lemma} \proof Suppose $\bm{\lambda}=(\lambda_1, \ldots, \lambda_{t_1})$ and $\bm{\mu}=(\mu_1, \ldots, \mu_{t_2})$. Note that since the numbers are increasing in the columns of any semistandard tableau of shape $\bm{\mu}$ and type $\bm{\lambda}$, the minimum number in row $i$ is $i$. Suppose $\lambda_i=\mu_i$ for all $1\leq i < i^*$ and $\lambda_{i^*}>\mu_{i^*}$, i.e., $\bm{\lambda}$ is lexicographically greater than $\bm{\mu}$. Then any semistandard tableau of shape $\bm{\mu}$ and type $\bm{\lambda}$ will have to have $\lambda_1$ 1's in row 1, $\ldots$, and $\lambda_{i^*-1}$ $(i^*-1)$'s in row $i^*-1$ in order to have increasing numbers along the columns. Then one would attempt to put $\lambda_{i^*}$ $i^*$'s in row $i^*$, but that is not possible since $\mu_{i^*}<\lambda_{i^*}$, and so at least one $i^*$ will have to be in row $i^*+1$, meaning that we don't have a semistandard tableau since the columns are not strictly increasing. Now suppose that $\bm{\mu}$ has more parts than $\bm{\lambda}$, i.e., $t_2>t_1$. Look at the first column of a semistandard tableau: there needs to be at least $t_2$ distinct numbers in it, but $N_{\bm{\lambda}}$ contains only $t_1$ distinct numbers and so there is no semistandard tableau. \qed \begin{definition} \label{def:unrhd} We define the ordering $\unrhd$ on partitions as follows: $\bm{\mu} \unrhd \bm{\lambda}$ if $\bm{\mu}$ is lexicographically greater than or equal to $\bm{\lambda}$ and has at most as many parts as $\bm{\lambda}$. \end{definition} Using Theorem \ref{YoungsRule} and Lemma~\ref{multzero}, we can determine which irreducibles in \eqref{eq:irreducible decomposition} contribute components to a given $\mathfrak{R}_{\tau_{\bm{\lambda}}}$-invariant polynomial. \begin{theorem} \label{thm:orbit polys in span of basis polys} A $\mathfrak{R}_{\tau_{\bm{\lambda}}}$-invariant polynomial $\mathsf{f}$ in $V = \RR[\bf x]_{\leq d}$ lies in $\bigoplus_{\bm{\mu} \unrhd \bm{\lambda}} V_{\bm{\mu}}$. \end{theorem} \proof Since $\mathsf{f}$ is $\mathfrak{R}_{\tau_{\bm{\lambda}}}$-invariant, by Theorem \ref{YoungsRule}, the multiplicity of the trivial representation of $\mathfrak{R}_{\tau_{\bm{\lambda}}}$ in $V_{\bm{\mu}}^i$ restricted to $\mathfrak{R}_{\tau_{\bm{\lambda}}}$ is the number of semistandard tableaux of shape $\bm{\mu}$ and type $\bm{\lambda}$. By Lemma \ref{multzero}, this multiplicity is zero if $\bm{\mu}$ is lexicographically smaller than $\bm{\lambda}$ or if it has more parts than $\bm{\lambda}$. Therefore, $\mathsf{f}\in \bigoplus_{\bm{\mu} \unrhd \bm{\lambda}} V_{\bm{\mu}}$. \qed Since $\mathsf{r}_j$ in $\sum_j \mathsf{r}_j^2$ from \eqref{deepsos} is $\mathfrak{R}_{\tau_{\bm{\lambda}}}$-invariant for a tableau $\tau_{\bm{\lambda}}$ of shape $(n-k,1^k)$ by Theorem~\ref{lcorbits}, and since for the hook $\bm{\lambda} = (n-k, 1^k)$, $\bm{\mu} \unrhd \bm{\lambda}$ if and only if $\bm{\mu} \geq_{\textup{lex}} \bm{\lambda}$, we get the following offshot. \begin{corollary}\label{cor:orbitpolyvectorspace} Any polynomial $\mathsf{r}_k \in V$ that contributes to the sos \eqref{deepsos} lies in $\bigoplus_{\bm{\mu} \geq_{\textup{lex}} \bm{\lambda}} V_{\bm{\mu}}$ where $\bm{\lambda} = (n-k, 1^k)$. \end{corollary} \subsection{From Razborov to Gatermann-Parrilo} We are now ready for the final step. We will show that a sos arising from flag algebras as in Proposition \ref{cor:translation-sos} can be retrieved from the Gatermann-Parrilo SDP by restricting to certain blocks in the sense of Definition \ref{def:restrictedGP}. We first define formally the concept of symmetrization, which we already saw a few times. \begin{definition}\label{def:symmetrization} The \emph{symmetrization} of a polynomial $\mathsf{f} \in \RR[{\bf x}]$ with respect to $\mathfrak{S}_n$ is denoted by $\textup{sym}({\mathsf{f}})$ and defined to be $$\textup{sym}({\mathsf{f}})=\frac{1}{n!}\sum_{\mathfrak{s}\in \mathfrak{S}_n} \mathfrak{s} \mathsf{f}.$$ \end{definition} \begin{proposition}\label{sosrazvsgp} If some $\mathfrak{S}_n$-invariant sos $\sum_{j} \mathsf{f}_j^2$ is such that $\mathsf{f}_j\in V_{\bm{\lambda}_1}\oplus \ldots\oplus V_{\bm{\lambda}_s}$ for all $j$, then this sos can be obtained through the Gatermann-Parrilo SDP restricted to $\bm{\lambda}_1, \ldots, \bm{\lambda}_s$. \end{proposition} \proof Suppose $\sum_{j}\mathsf{f}_j^2$ is a sos such that $\mathsf{f}_j=\mathsf{f}_{j,1} + \cdots + \mathsf{f}_{j,s}$ where $\mathsf{f}_{j,i} \in V_{{\bm{\lambda}}_i}$ for $i=1,\ldots,s$ for all $j$. Then \begin{align} \label{expansion of rk^2} \mathsf{f}_j^2= (\mathsf{f}_{j,1})^2+\ldots + (\mathsf{f}_{j,s})^2 + 2\sum_{i_1 < i_2} \mathsf{f}_{j,i_1} \mathsf{f}_{j,i_2}. \end{align} Since the sos $\sum_{j}\mathsf{f}_j^2$ is $\mathfrak{S}_n$-invariant, symmetrizing it with respect to $\mathfrak{S}_n$ leaves it unchanged. Therefore, \begin{align*} \sum_{j}\mathsf{f}_j^2&=\textup{sym}\left(\sum_{j}\mathsf{f}_j^2\right)=\sum_{j} \textup{sym} \left(\mathsf{f}_j^2\right)=\sum_{j} \textup{sym}\left((\mathsf{f}_{j,1}+\ldots +\mathsf{f}_{j,s})^2\right)\\ &=\sum_{j} \left(\sum_{i} \textup{sym} \left(\mathsf{f}_{j,i}^2\right) + 2\sum_{i_1_{\textup{lex}} (n-t,1^t)}V_{\bm{\mu}}$ by \eqref{cor:orbitpolyvectorspace}. Therefore, by \eqref{sosrazvsgp}, the sos \eqref{middlesos} can be obtained from the Gatermann-Parrilo SDP restricted to the partitions $\bm{\mu} \geq_{\textup{lex}} \bm{\lambda}$. \qed Finally, we tackle the general Razborov sos for proofs involving several $\sigma$ and $l$. \begin{corollary}\label{wholething} Consider a conic combination of sos \eqref{razborovsosshape} for different choices of $\sigma$ and $l$. Let $k^*$ be the maximum size of all types $\sigma$ present. Then this sos can be obtained through the Gatermann-Parrilo program restricted to partitions lexicographically greater or equal to the hook partition $(n-k^*, 1^{k^*})$. \end{corollary} \proof In Theorem \ref{cor:sos from same isotypics}, we proved that the sos \eqref{deepsos} can be obtained by restricting the Gatermann-Parrilo SDP to partitions $\bm{\mu}$ for $\bm{\mu}\geq_{\textup{lex}} (n-|\sigma|,1^{|\sigma|})$. Thus every sos in \eqref{razborovsosshape} for each $\theta, \sigma, l$ can be obtained from partitions $\bm{\mu}$ for $\bm{\mu}\geq_{\textup{lex}} (n-k^*, 1^{k^*})$ where $k^*$ is the maximum size of all types considered. Since the final sos is a conic combination of these smaller sos, it can also be obtained by restricting the Gatermann-Parrilo SDP to those same partitions. \qed We have established the relationship between the Gatermann-Parrilo framework and the flag algebra sos for Tur{\'a}n problems. We conclude with a few remarks that will be helpful in implementing the Gatermann-Parrilo framework. \begin{remark} Note that flag algebra Tur\'an sos uses fixed $k$ and $l$ (independent of $n$) and thus the number of partitions indexing blocks in the restricted SDP is also independent of $n$. Indeed, the number of partitions lexicographically greater than or equal to $(n-k,1^{k})$ is at most twice the number of partitions of $k$. Moreover, each small subblock in a block corresponding to a $\bm{\lambda}$ has size $m_{\bm{\lambda}}\times m_{\bm{\lambda}}$, which depends on $d$ but not $n$. Finally, even though the number of subblocks per block (i.e., the number of standard tableaux) increases as $n$ increases, by \eqref{onlyonetableau}, we only need one subblock. Thus, the size of the restricted SDP does not depend on $n$. \end{remark} \begin{remark} In Theorem~\ref{lcorbits}, we showed that a $\mathsf{r}_j$ in the sos \eqref{deepsos} is invariant under $\mathfrak{R}_{\tau_{\bm{\lambda}}}$ for some tableau $\tau_{\bm{\lambda}}$ where $\bm{\lambda}$ is a hook partition. One can obtain further savings in the size of the corresponding SDP by using symmetries of the $\sigma$-flags which allows us to replace the hook partition with partitions that are lexicographically larger than it. For example, in Example~\ref{exorbit_part2}, $\mathsf{p}_F^\theta$ is also invariant under the row group of $$\tau_{\bm{\lambda}} = \young(45,23,1) \,\,\,\,\textup{, i.e., }\,\,\,\, \mathfrak{R}_{\tau_{\bm{\lambda}}} = \{1, (2,3), (4,5), (2,3)(4,5)\}.$$ \end{remark} We also note that we have stated our results based on the isotypic decomposition of $V = \RR[{\mathbf x}]_{\leq d}$ and not of the quotient vector space $\RR[{\mathbf x}]_{\leq d} / \mathscr{I}_n^A$. This is again for simplicity and will not change the flavor of the results. The ideal is used implicitly in some places such as in the derivation of the sos \eqref{razborovsosshape}. \section{The symmetry-adapted SDP for Mantel's theorem} \label{sec:Mantel1} Recall the proof of Mantel's theorem from Section~\ref{sec:FlagAlgebras} using flag algebra calculus (see also the Appendix). The sos was divided into two parts: one involving $F_0$ and $F_1$, and one involving $H_1$. We show how to retrieve the former; the latter is similar in flavor. Since the flags $F_0$ and $F_1$ needed in the sos expression~\eqref{eq:mantel-short-sos} have a type of size $k=1$, Theorem~\ref{cor:sos from same isotypics} implies that we can retrieve this sos expression by restricting the Gatermann-Parrilo SDP to partitions $(n)$ and $(n-1,1)$. Moreover, $\mathsf{p}_{F}^{\theta}$ has degree at most one for $F\in \{F_0, F_1\}$ and therefore we only need to consider $V=\RR[{\mathbf{x}}]_{\leq 1}$. For illustration, we verify this. Observe that $n_{\bm{\lambda}}$, the number of standard tableaux of shape $\bm{\lambda}$, is $1$ for $\bm{\lambda}=(n)$ and $n-1$ for $\bm{\lambda}=(n-1,1)$. Restricting the expression in \eqref{onlyonetableau} to partitions $(n)$ and $(n-1,1)$ implies that there exist psd matrices $Q_{(n)}$ and $Q_{(n-1,1)}$ such that \begin{align}\label{eq:sos-mantel-short2} \mathsf{f} = 1 \cdot \langle Q_{(n)}, Y_{(n)}\rangle + (n-1)\cdot \langle Q_{(n-1,1)}, Y_{(n-1,1)} \rangle \end{align} \noindent where \begin{align*} \mathsf{f}=E_{\theta}\left[\begin{pmatrix}\pp^{\theta}_{F_0}(G) & \pp^{\theta}_{F_1}(G)\end{pmatrix} \begin{pmatrix} \frac12 &-\frac12 \\ -\frac12 & \frac12\end{pmatrix} \begin{pmatrix}\pp^{\theta}_{F_0}(G) \\ \pp^{\theta}_{F_1}(G) \end{pmatrix}\right] \end{align*} is the sos expression obtained using flag algebras in \eqref{eq:mantel-short-sos}. Recall that the expression~\eqref{eq:sos-mantel-short2} relies on the decomposition $V_{\bm{\lambda}} = \oplus_{i=1}^{n_{\bm{\lambda}}} W_{\tau_{\bm{\lambda}}^i}$ as in Equation~\eqref{eq:alternate-decomposition}. The matrices $Y_{\bm{\lambda}}$ come from the polynomials in the symmetry-adapted basis and can be computed using the algorithm in \cite[Chapter 5.2, pp.~113--114]{FaesslerStiefelBook}. Also recall that $Y_{\bm{\lambda}}$ depends only on one standard tableau of shape $\bm{\lambda}$. The algorithm yields the basis polynomials \begin{align*} \mathsf{p}_{0,0}:=1, \quad \mathsf{p}_{0,1}:= \frac{1}{\sqrt{\binom{n}{2}}}\cdot \sum_{1\leq in)$. Therefore, $$Y_{(n)}=\begin{pmatrix} \mathsf{p}_{0,0} & \mathsf{p}_{0,1} \end{pmatrix} \begin{pmatrix} \mathsf{p}_{0,0} \\ \mathsf{p}_{0,1} \end{pmatrix}.$$ Similarly, the algorithm yields the basis polynomial $$p_{1,n}:=\frac{1}{\sqrt{\binom{n-1}{2}\cdot 1^2+(n-1)\cdot \left(\frac{n-2}{2}\right)^2}}\left(\sum_{1\leq i < j \leq n-1}\mathsf{x}_{ij} - \frac{n-2}{2}\cdot\sum_{1\leq i \leq n-1} \mathsf{x}_{in}\right)$$ of degree one for $W_{\tau_{(n-1,1)}}$ where $\tau_{(n-1,1)}=\Yboxdimx{25pt}\Yboxdimy{10pt}\young(123<\ldots>,n).$ Thus, we have that $$Y_{(n-1,1)}=\frac{1}{|\mathfrak{S}_n|} \sum_{\mathfrak{s}\in \mathfrak{S}_n} \mathfrak{s}(\mathsf{p}_{1,n})(\mathsf{p}_{1,n})^T=\frac{1}{n}\sum_{i=1}^n (\mathsf{p}_{1,i})^2.$$ Altogether, we obtain a block SDP consisting of one block of size $2\times 2$ for $Q_{(n)}$ and another block of size $1\times 1$ for $Q_{(n-1,1)}$. For instance choosing psd matrices $$Q_{(n)}=\begin{pmatrix} \frac{(n-1)^2}{2} & \frac{-\sqrt{2(n-1)^3}}{\sqrt{n}} \\ \frac{-\sqrt{2(n-1)^3}}{\sqrt{n}} & \frac{4(n-1)}{n} \end{pmatrix}$$ and $$Q_{(n-1,1)}=\begin{pmatrix} \frac{2(n-1)(n-2)}{n} \end{pmatrix}$$ yields the expression~\eqref{eq:mantel-short-sos} as desired. \section{Conclusion}\label{sec:conclusion} The main result of this paper is that standard symmetry-reduction methods in polynomial sos theory can retrieve Razborov's sos proofs using flag densities that arise in the context of Tur\'an problems. For the sake of notational simplicity, we presented our results in the context of graphs. However, the same techniques can be used for Tur\'an and non-Tur\'an problems over hypergraphs, digraphs, tournaments, etc. Below, we give a few examples of the changes that need to be made in different cases. \begin{enumerate} \item {\em Hypergraphs}: For any optimization problem over $a$-uniform hypergraphs on $n$ vertices, we can use the ideal $$\langle x_{i_1\ldots i_a}^2-x_{i_1\ldots i_a} \quad \forall 1\leq i_1 < \ldots < i_a \leq n \rangle. $$ This ideal is $\mathfrak{S}_n$-invariant, which implies that our theory can still be applied. Thus any flag Cauchy-Schwarz proof in this setting can be retrieved by using symmetry-reduction and restricting to partitions lexicographically greater or equal to $(n-k^*, k^*)$ where $k^*$ is the size of the biggest $\sigma$ involved and by letting the degree be as big as the biggest flag present. For example, we could use this for the Tur\'an hypergraph problem of maximizing the hyperedge density in an $a$-uniform hypergraph on $n$ vertices where $a$-uniform hypercliques of size $b$ are forbidden by adding $$\prod_{\{i_1, \ldots, i_a\} \in E(Q)} x_{i_1\ldots i_a} \quad \forall b\textup{-clique } Q \textup{ in } K_n^a$$ to our ideal. In \cite{Razborov10}, Razborov gives a Cauchy-Schwarz proof that the maximum edge density in a $3$-uniform hypergraph without $4$-cliques is at most $0.561666$. This result can be translated in the polynomial language using the above-mentioned framework. \item {\em Digraphs}: For any optimization problem over digraphs on $n$ vertices, we can use the ideal $$\langle x_{ij}^2-x_{ij} \quad \forall 1\leq i,j \leq n \textup{ such that } i\neq j\rangle. $$ Again, the ideal is $\mathfrak{S}_n$-invariant, and so our techniques can again be used here. For example, we could use this for the Cacetta-H\"aggkvist conjecture which states that every simple digraph of order $n$ with minimum outdegree of at least $r$ has a cycle of length at most $\lceil \frac{n}{r} \rceil$ by adding $$\prod_{(i,j)\in E(C)} x_{ij} \quad \forall \textup{ cycles } C \textup{ such that } |C|\leq \lceil\frac{n}{r} \rceil$$ $$ \prod_{j\in S} (1-x_{ij}) \quad \forall i, \forall S \subseteq [n]\backslash \{i\} \textup{ such that } |S|=n-r+1$$ and check for feasibility. Indeed, the first set of constraints ensures that we get a directed graph on $n$ vertices, the second set of constraints forbids cycles of length less or equal to $\lceil \frac{n}{r} \rceil$, and the third set of constraints sets the outdegree of every vertex to be t least $r$. Of course, here the degree of these constraints being quite high makes it unlikely that this technique would yield any interesting results unless $r$ is very big. \item {\em Tournaments}: For an optimization problem over all tournaments of size $n$, we can use the ideal \begin{align*} \langle & x^2_{ij}-x_{ij} && \forall 1 \leq i,j \leq n \textup{ such that } i\neq j\\ &x_{ij}x_{ji} && \forall 1 \leq i < j \leq n \\ &(1-x_{ij})(1-x_{ji}) && \forall 1 \leq i < j \leq n \rangle \end{align*} since exactly one of the arcs $(i,j)$ and $(j,i)$ are present for any $1 \leq i < j \leq n$, as well as any additional constraints forbidding certain structures in the problem. Again, we have an ideal that is $\mathfrak{S}_n$-invariant, and our techniques can again be used here. \end{enumerate} The general theory of flag algebras \cite{RazborovFlagAlgebras} is couched in a broad setting using tools from algebra, topology, and probability. It is a formal calculus that came about from an attempt to systematize and distill the many ad hoc methods in extremal combinatorics. In this paper, we have shown that sos proofs that arise from flag densities are equivalent to polynomial sos proofs using symmetry-reduction. This connection allows for systematic ways to search for flag sos proofs which was part if our original motivation in undertaking this project. There are likely much further, and deeper, connections between Razborov's theory in its full generality, and the fundamental structures of real algebraic geometry. We hope to delve deeper in this direction. In \cite{RSST}, the authors, along with James Saunderson, established the converse to the result in this paper. By a $k$-subset hypercube we mean a hypercube whose coordinates are indexed by the $k$-element subsets of $[n]$. Thus the usual hypercube $\{0,1\}^n$ is the $1$-subset hypercube. The $2$-subset hypercube $\{0,1\}^{n \choose 2}$ arises in the context of optimization over (the edges of) a graph. The main result of \cite{RSST} is that flag methods can be used to provide sos certificates for the nonnegativity of symmetric polynomials over $k$-subset hypercubes. This extends their use beyond the realm of extremal combinatorics into general polynomial optimization. The two papers together establish that flag methods are equivalent to standard symmetry-reduction methods in polynomial sos theory over the class of $k$-subset hypercubes. \section{Appendix} We present here the full translation of \cite{Falgas-RavryVaughan} to polynomials, culminating with a verification of the equivalence~\eqref{equivalencemantel}. We first discuss the (non-trivial) inequality whose nonnegativity establishes the theorem. A few other quantities are also needed for the proof in \cite{Falgas-RavryVaughan} which we define here. Fix $m