Lovasz theta function and independence number of product of simple odd-cycles

2011-03-26T02:46:24Z

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

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

$\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$?

Answer by Gjergji Zaimi for Lovasz theta function and independence number of product of simple odd-cycles

2011-08-18T13:57:11Z

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.

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

Lovasz theta function and independence number of product of simple odd-cycles - MathOverflow

Lovasz theta function and independence number of product of simple odd-cycles

Answer by Gjergji Zaimi for Lovasz theta function and independence number of product of simple odd-cycles