10
$\begingroup$

The post is related to: https://mathoverflow.net/questions/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles

How far away is the Lovasz bound from the zero-error capacity of regular graphs? Are there any examples where the Lovasz bound is known to be not equal to the zero-error capacity of a regular graph? (This was answered below by Oleksandr Bondarenko.)

In particular is any strict inequality known for odd cycles of sides greater than or equal to $7$?

Update What improvement is needed in spectral theory to improve the Lovasz theta function so that the gap between Shannon capacity and Lovasz Theta for the cases for which a gap exists could be lowered? (Note I am concerned only from spectral perspective)

$\endgroup$
  • $\begingroup$ I've delete my wrong answer. Thanks for the correction! $\endgroup$ – Hsien-Chih Chang 張顯之 Mar 28 '11 at 7:18
  • $\begingroup$ I do not understand the update, if there is a gap between zero-error capacity and $\vartheta$, how can you "lower" it? $\endgroup$ – Sasho Nikolov Dec 21 '13 at 19:15
  • $\begingroup$ I thing the phrasing is bad. Say $\delta=\vartheta-\Theta$ is the capacity gap between $\vartheta$ and $\Theta$. If some improvement could be made to spectral theory technology so that the new technique yields a sharper upper bound as compared to $\vartheta$ when $\delta>0$, what could that possible improvemnt be in spectral theory technology? Basically the update asks if spectral theory as of today faces such blocks to improvement. $\endgroup$ – T.... Dec 22 '13 at 14:57
13
$\begingroup$

In fact there is known a regular graph $G$ for which zero-error capacity $\Theta(G)$ is less than the Lov$\acute{a}$sz bound $\vartheta(G)$. W. Haemers in $[1]$ has proved that for the complement of Schl$\ddot{a}$fli graph $G$ the following holds: $\Theta(G)\leqslant7<\vartheta(G)=9$.

In $[2]$ it is noted that "The best known upper bounds on $\Theta(C_m)$ and $\Theta(\overline{C}_m)$ for $m$ odd and greater than $5$ are given by the Lovasz theta function ...". From this I conclude that that the answer to your last question is no (since then I don't know any results improving on this.).

Finding Shannon capacity even for $C_7$ would be a major breakthrough for this hard problem. Additionally, it can be noticed that

"it is not known if the problem of deciding whether the Shannon capacity of a given input graph exceeds a given value is decidable".

  1. W. Haemers, “On some problems of Lov$\acute{a}$sz concerning the Shannon capacity of a graph,” IEEE Trans. on Information Theory, vol. 25, no. 2, pp. 231–232, Mar. 1979.
  2. T. Bohman, "A limit theorem for the Shannon capacities of odd cycles. II," Proceedings of the American Mathematical Society, 2005.
  3. N. Alon, "Combinatorial Reasoning in Information Theory".
$\endgroup$
  • $\begingroup$ Thank you very much. Is the same known for simple odd cycles? For example $7$-sided polygon? $\endgroup$ – T.... Mar 28 '11 at 2:38
  • 1
    $\begingroup$ SO it is not known. This is very interesting. $\endgroup$ – T.... Mar 28 '11 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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