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

Lovasz theta function $\vartheta(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 \vartheta(G)$.

If the graph is a pentagon ($G=C_{5}$), then $\Theta(C_{5}) = \vartheta(C_{5})$.

$\Theta(C_{2k+1}) \ne \vartheta(C_{2k+1})$ if $k > 2$ since $\vartheta(C_{2k+1})^{r}$ fails to be integral for any $r \in \mathbb{Z}^{+}$. However, are there known lower and upper bounds for for $\vartheta(C_{2k+1}) - \Theta(C_{2k+1})$ that depends on $k$?

share|improve this question
    
Isn't it still unknown whether $\Theta(C_{2k+1}) = \theta(C_{2k+1})$? –  Graphth Dec 10 '12 at 18:49

1 Answer 1

up vote 2 down vote accepted

The theta function of odd cycles can be calculated explicitly: $$\vartheta(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 \vartheta(G)$, there haven't been any improvements when $G$ is an odd cycle.

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 limit theorem for the Shannon capacities of odd cycles, I" 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$$

share|improve this answer

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.