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)

Improve this question
$\endgroup$
3
  • $\begingroup$ I've delete my wrong answer. Thanks for the correction! $\endgroup$
    – Hsien-Chih Chang 張顯之
    Mar 28, 2011 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, 2013 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$
    – Turbo
    Dec 22, 2013 at 14:57

1 Answer 1

Reset to default
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".
Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much. Is the same known for simple odd cycles? For example $7$-sided polygon? $\endgroup$
    – Turbo
    Mar 28, 2011 at 2:38
  • 1
    $\begingroup$ SO it is not known. This is very interesting. $\endgroup$
    – Turbo
    Mar 28, 2011 at 7:07

Your Answer

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

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