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.



Lovasz function equality - combinatoric graph theory.
EDIT: The proof of the claim can also be found in section 18 of ["The Sandwich Theorem"](http://arxiv.org/abs/math/9312214) 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)$.


