Flag algebras and extremal combinatorics
Note: These are very rough scribe notes of what was covered by Pablo Parrilo. Please see the video for more complete coverage.
Look at the problem of certifying \(p(x)\geq 0\) for symmetric polynomial \(p\).
Example: Compute \(\alpha(G)\) where \(G\) is the Hamming weight graph with vertices corresponding to \(\bits^n\) and edges corresponding to pairs with Hamming distance at most \(k\). In this case \(\alpha(G)\) is the maximum size of an error correcting code of block length \(n\) and distance \(k\).
Let \(\cG\) be a group of linear transformations over \(\R^n\). We say that a polynomial \(p\) is \(\cG\) symmetric if \(p(x)=p(\tau(x))\) for every \(\tau\in \cG\).
Digression to representation theory.
A representation is \(\rho\from\cG\to GL(V)\) where \(V\) is a subspace which is homomorphic.
Example: \(S_2\): group of permutations on set of two elements. We can write \(S_2 = \{ e,g\}\) , \(g^2=e\) and \(e\) is the identity element.
Natural representation is \(\rho\from S_2\to GL(\R^2)\) where \(\rho(e) = \bigl(\begin{smallmatrix} 1 & 0 \\ 0 & 1 \end{smallmatrix}\bigr)\) and \(\rho(g) = \bigl(\begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}\bigr)\). That is \(\rho(e)\) is the map \((x,y)\mapsto (x,y)\) while \(\rho(g)\) is the map \((x,y)\mapsto (-y,x)\).
This representation has two invariant one dimensional subspaces \(\{ x=y \}\) and \(\{ x= -y \}\). Restricting it to these two subspaces gives the trivial representation and the alternating / sign representation where \(\rho(g)=+1\) and \(\rho(e)=-1\).
An invariant subspace of a representation \(\rho\from\cG\to GL(V)\) is a subspace \(W \subseteq V\) such that \(\rho(GgW = W\) for all \(g\in\cG\). We say that an invariant subspace is trivial if \(W=V\) or \(W = \{ 0 \}\). An irreducible representation (irrep) is a representation without any non-trivial invariant subspace.
We say that two representations \(\rho\from\cG\to GL(V)\) and \(\rho'\from\cG\to GL(V')\) are equivalent if there is an invertible linear transformation \(T\from V\to V'\) such that \[ \rho(g) = T^{-1} \rho'(g) T \] for every \(g\in\cG\).
Example 2: \(S_3\) - group of permutations on set of three elements. We can write \(S_3 = \{ e,s,c,c^2,cs,sc \}\) where in cycle notation \(s=(1,2)\) and \(c=(1,2,3)\). The relations that this satisfies is \(c^3 =e\), \(s^2 = e\) and \(s=csc\).
We can express the possible irreps in a Young tableus that satisfy the relation \(n!= \sum d_i^2\).
Example 3: \(\mathbb{C}_n = \{0,\ldots,n-1\}\) with addition modulo \(n\). We can represent this in \(n\) ways with \(\rho_k(j) = \omega^{kj}\) for \(\omega = e^{2\pi i/n}\). (In Abelian group all irreps have dimension one.)
Convexity and symmetry
Suppose we want to minimize a univariate function \(f\from\R\to\R\) and suppose that it is symmetric in the sense that \(f(x)=f(-x)\). A priori that gives us no information about it, but if we add the condition that \(f\) is convex then we can deduce that it must have a global minimum at \(x=0\).
More generally, we say that \(f\from V\to\R\) is symmetric with respect to a group \(\cG\) and a representation \(\rho\) if \(f(\rho(g)x) = f(x)\) for all \(g\in\cG\).
If \(f\) is symmetric w.r.t. \(\cG,\rho\) and convex then it always has a minimum \(x\) that satisfies the property that \(x=\rho(g)x\) for every \(g\in G\).
Given \(x\) which achieves the minimum of \(f\), by symmetry and convexity, the same will hold for \(x^* = \tfrac{1}{|\cG}\sum_{g\in \cG} \rho(g)x\), but it is not hard to verify (exercise!) that the latter will satisfy the above property.
For a group \(\cG\) and a representation \(\rho\from\cG\to V\), we define the fixed point subspace of \(\rho\) to be \(\{ x\in V : x=\rho(g)x \forall g\in\cG \}\). (Exercise: Verify that this is indeed a linear subspace.)
Example: Lovasz theta function
Consider the following convex relaxation for the independent set problem:
For an \(n\) vertex graph \(G\), recall that the independent set number is defined as \(\alpha(G) = \max \sum x_i\) over \(x\in\bits^n\) such that \(x_ix_j\) for all \(i \sim j\) in \(G\). We can relax this as \(\vartheta(G) = \max \Tr(JX)\) over all p.s.d. matrices \(X \succeq 0\) such that \(\Tr(X)=1\), \(X_{i,j}=0\) for all \(i\sim j\) and where \(J\) is the all \(1\)’s matrix.
For every \(G\), the value \(\vartheta(G)\) can be thought of as the maximum of a concave (in fact linear) function over a convex set and so also as minimizing a convex function. If the graph itself has symmetries then \(\vartheta\) itself has symmetries and so its minimum is known to lie in some nice space. For example, if the graph is the cycle, then the minimum is achieved by a matrix \(X\) which is circulant.
Semidefinite programs and representations.
In sos programs the representations inherit the symmetry in the instance in a “nice form” which is that if \(X \in \R^{n^d\times n^d}\) is a matrix representing the degree \(2d\) sos solution and \(\rho\from\cG\to GL(\R^n)\) is a representation with respect to the original function is symmetric, then if we let \(\rho'\from\cG\to GL(\R^{n^{\otimes d}})\) be the representation obtained by tensoring \(\rho\) then the value of \(X\) as a solution to the sos program equals the value of \({\rho'(g)}^\top X \rho'(g)\) for all \(g\in\cG\). This allows to use Shor’s Lemma to reduce the study of solution to a potentially much smaller number of equivalence classes.
Examples:
- Minimizing univariate \(p(x)\) that satisfies \(p(x)=p(-x)\) and hence \(p(x)=q(x^2)\).
- Minimizing \(p(x)\) over \(x\in\bits^n\) such that \(p\) is \(S_n\)-symmetric and hence \(p(x)=q(\tfrac{1}{n}\sum x_i)\) for some \(q\).
- In coding, we can bound the best possible rate of a code with given distance (which is the logarithm of the independence number of the Hamming graph) by the \(\vartheta\) function, which corresponds to degree \(2\) sos, and analyze it using symmetry which allows to reduce this SDP to an LP. A more sophisticated bound was given by looking at the degree \(4\) sos.