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
