Hello everyone,
I was wondering how to prove the following equality:
$\theta(G+H)=\theta(G)+\theta(H)$
where $G$ and $H$ are graphs and $\theta$ is the Lovasz Theta function.
correction: I apologize for not explaining what $G+H$ denotes.
The (disjoint) union of two graphs $G$ and H, denoted $G + H$, is the graph whose vertex set is the disjoint union of the vertex sets of $G$ and of $H$ and whose edge set is the (disjoint) union of the edge sets of $G$ and $H$
thanks in advance.
EDIT: The proof of the claim can also be found in section 18 of "The Sandwich Theorem" by Knuth. I feel like there is a misunderstanding in terms of definitions going on here... The OP should clarify if he or she cares about the Shannon capacity or Lovasz theta. (Also why the downvotes? :P)
Let $n,m$ be the number of vertices of $G$ and $K$, respectively. By definition $\theta(G+K)$ is the smallest $\theta$ so that there is an orthonormal representation of $G+K$, $\{u_1, \dots,u_n, v_1,\dots,v_m\}$ and a unit vector $c\in \mathbb R^{n+m}$ so that $(c\cdot u_i)^2\geq \frac{1}{\theta}$ and similarly $(c\cdot v_j)^2\geq \frac{1}{\theta}$. Since $u_i\cdot v_j=0$ for all $i,j$, the optimal $\theta$ is achieved when the coordinates of $c$ are so that $(c\cdot u_i)^2=\frac{r}{\theta(G)}$ and $(c\cdot v_j)^2=\frac{1-r}{\theta(K)}$ for some $0\le r\le 1$. So we obtain $$\theta(G+K)=\min_{0\le r\le 1} \max\left(\frac{\theta(G)}{r},\frac{\theta(K)}{1-r}\right)$$ It is not hard to see that this implies $\theta(G+K)=\theta(G)+\theta(K)$.
In fact, Noga Alon proved in 1998 that it is false in general that $\theta(G+K)=\theta(G) +\theta(K)$. See http://www.tau.ac.il/~nogaa/PDFS/shann3.pdf. See also Miniature 29 of J. Matoušek, Thirty-three Miniatures, American Mathematical Society, 2010.
