Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
You need to tell us what $G+H$ denotes? –  Chris Godsil Jul 29 '11 at 11:30
    
thank you Chris. fixed. –  BarShu Jul 29 '11 at 12:31

2 Answers 2

up vote 5 down vote accepted

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)$.

share|improve this answer

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.

share|improve this answer
    
Here's a Google Books link to Matoušek's proof on (top of) p. 141: books.google.com/… –  Joseph O'Rourke Jul 29 '11 at 23:26
6  
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 '11 at 0:50
    
oops, my bad. :( –  Richard Stanley Jul 31 '11 at 14:21
    
Never mind, I enjoyed learning about that paper! –  Thierry Zell Aug 25 '11 at 1:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.