Lovasz theta function and independence number of product of simple odd-cycles - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T13:50:21Z http://mathoverflow.net/feeds/question/59631 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles Lovasz theta function and independence number of product of simple odd-cycles unknown (google) 2011-03-26T02:46:24Z 2011-08-18T21:10:03Z <p>Lovasz theta function $\theta(G)$ of a graph $G$ provides an upper bound for the independence number of a graph, $\alpha(G)$ and $\Theta(G) = \lim_{k\rightarrow \infty}\sqrt[k]{\alpha(G^{k})}$. That is, $\Theta(G) \le \theta(G)$.</p> <p>If the graph is a pentagon ($G=C_{5}$), then $\Theta(C_{5}) = \theta(C_{5})$.</p> <p>$\Theta(C_{2k+1}) \ne \theta(C_{2k+1})$ if $k > 2$ since $\theta(C_{2k+1})^{r}$ fails to be integral for any $r \in \mathbb{Z}^{+}$. However, are there known lower and upper bounds for for $\theta(C_{2k+1}) - \Theta(C_{2k+1})$ that depends on $k$?</p> http://mathoverflow.net/questions/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles/73152#73152 Answer by Gjergji Zaimi for Lovasz theta function and independence number of product of simple odd-cycles Gjergji Zaimi 2011-08-18T13:57:11Z 2011-08-18T21:10:03Z <p>The theta function of odd cycles can be calculated explicitly: $$\theta(C_{2n+1})=\frac{(2n+1)\cos(\frac{\pi}{2n+1})}{1+\cos(\frac{\pi}{2n+1})}=n+\frac{1}{2}-O(1/n)$$ while computing $\Theta(C_{2n+1})$ for any $n\geq 3$ is an open problem. So your question is about bounds on $\Theta(C_{2n+1})$. The best upper bound is the one we know for all graphs, $\Theta(G)\le \theta(G)$, there haven't been any improvements when $G$ is an odd cycle.</p> <p>As for lower bounds, a first improvement on $\Theta(C_{2n+1})\geq \alpha(C_{2n+1})=n$ is given by $$\Theta(C_{2n+1})\geq \sqrt{\alpha(C_{2n+1}^2)}=\sqrt{n^2+\lfloor\frac{n}{2}\rfloor}=n+\frac{1}{4}-O(1/n)$$ and further by considering a lower bound on $\alpha(C_{2n+1}^3)$, Bohman, Ruszink and Thoma proved in "Shannon capacity of large odd cycles" that $$\Theta(C_{2n+1})\geq n+\frac{1}{3}-O(1/n)$$ I believe the best known lower bounds are the ones one gets from extracting the exact counting given in <a href="http://www.jstor.org/pss/1194666" rel="nofollow">"A limit theorem for the Shannon capacities of odd cycles, I"</a> and II, by T. Bohman. Bohman didn't write the explicit lower bound but instead just gave an estimate which is enough to prove $$\lim_{n\to \infty} \left(n+\frac{1}{2}-\Theta(C_{2n+1})\right)=0$$</p>