[Solved]: Lovasz theta of even cycle

Problem Detail: 

How does one show Lovasz theta of even $n$-cycle ($n$ is even) is of form $\frac{n}{2}$? Why is the Lovasz theta of such cycles not of form $\frac{n \cos(\frac{\pi}{n})}{1+\cos(\frac{\pi}{n})}$. Could someone provide a derivation for even cycle Lovasz theta number. It is clear that the Shannon Capacity is $\frac{n}{2}$. why is the cosine form tight only for odd cycles?

Asked By : Turbo

Answered By : Yuval Filmus

The Lovász theta function is bounded between the independence number and the clique covering number (the chromatic number of the complementary graph). For even cycles, both numbers are $n/2$. For example, for the $6$-cycle with vertices $1,2,3,4,5,6$, there are independent sets of size $3$, e.g. $\{1,3,5\}$, and the graph can be covered with the $3$ cliques $\{1,2\},\{3,4\},\{5,6\}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/31869

 Ask a Question

 Download Related Notes/Documents