3
$\begingroup$

Shannon capacity $\Theta(G)$ of pentagon is achieved at $2$-fold strong product of the pentagon.

It is also known that the Lov\'asz theta $\vartheta(G)^m\neq\alpha(G^{\boxtimes m})$ for any finite positive integer $m$ if $G$ is an odd cycle of length $>5$.

Is it known that $\Theta(G)^m\neq\alpha(G^{\boxtimes m})$ for any finite positive integer $m$ if $G$ is an odd cycle of length $>5$? That is $\limsup_{m\rightarrow\infty}\alpha(G^{\boxtimes m})^{\frac{1}{m}}$ is not attained at a finite positive integer $m$.

Note that the the above statement is true would still not be strong enough to decide $\vartheta(G)=\Theta(G)$.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ As far as I know, nothing is known here. I.e., it's possible that the Shannon capacity of an odd cycle is always attained by some finite power, it's possible that it never is beyond the pentagon, and it's possible that it sometimes is and sometimes isn't. $\endgroup$
    – Henry Cohn
    Oct 4, 2013 at 13:42
  • $\begingroup$ The last phrase "....it's possible that it sometimes is and sometimes isn't." seems to echo the first phrase "..is always attained by some finite power" since if it is attained at a finite power, then it is attained at all multiples of the finite power. Isn't this the case? $\endgroup$
    – Turbo
    Oct 4, 2013 at 15:35
  • $\begingroup$ I see what you mean is for some graphs it is and for some graphs it is not; and not what I interpreted (for some powers it is and for some powers of the same graph it is not). $\endgroup$
    – Turbo
    Oct 4, 2013 at 16:08

1 Answer 1

Reset to default
1
$\begingroup$

Currently, there are no known examples of graphs where the Shannon Capacity is realized in a dimension other than $1$ or $2$.

However, there are cases (Such as $C_5$ union a point) where the Shannon Capacity is not achieved in any dimension, and it is believed by many that this is the case for $C_7$.

Improve this answer
$\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.