2
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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\}$.

$\endgroup$
19
  • $\begingroup$ hmmm ok.. but would there be a semidefinite derivation of the same number? I am unable to get it. $\endgroup$
    – Turbo
    Oct 13, 2014 at 4:49
  • $\begingroup$ You can take any of the definitions of the Lovász theta function and you will get the same thing, since all definitions result in the same number. You can try solving it for small $n$ on a computer and extrapolate. $\endgroup$ Oct 13, 2014 at 12:58
  • $\begingroup$ I am getting what lovasz gets for n cycles but cos(pi/n)/(1+cos(pi/n)) is not 1/2 for even n. That is what I am missing. $\endgroup$
    – Turbo
    Oct 13, 2014 at 18:02
  • $\begingroup$ So you are not finding the optimal solutions of the SDPs (or whatever formulation you are using). The solution for even cycles could be different from that of odd cycles. $\endgroup$ Oct 13, 2014 at 18:04
  • 1
    $\begingroup$ Right, that's what the paper claims, anyway. $\endgroup$ Oct 16, 2014 at 2:57
2
$\begingroup$

See Lovasz' definition of theta in terms of orthonormal representations of graphs. Even cycles have an orthonormal representation in two dimensions in which the odd nodes are mapped to (0,1) and the even nodes are mapped to (1,0). Odd cycles, on the other hand, do not have two-dimensional orthonormal representations. They have three-dimensional ones that take the form of an "umbrella".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.