## Lovasz function equality - combinatoric graph theory.

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$

-
You need to tell us what $G+H$ denotes? – Chris Godsil Jul 29 2011 at 11:30
thank you Chris. fixed. – BarShu Jul 29 2011 at 12:31

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.

-
Here's a Google Books link to Matoušek's proof on (top of) p. 141: books.google.com/… – Joseph O'Rourke Jul 29 2011 at 23:26
The question says "the Lov\'asz theta function". I see no reason not to take this at face value - I have never seen a lower case theta used for Shannon capacity. So I think Gjergi's solution stands. – Chris Godsil Jul 30 2011 at 0:50
oops, my bad. :( – Richard Stanley Jul 31 2011 at 14:21
Never mind, I enjoyed learning about that paper! – Thierry Zell Aug 25 2011 at 1:07