<p>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 <a href="http://en.wikipedia.org/wiki/Schl%C3%A4fli_graph">Schl$\ddot{a}$fli graph</a> $G$ the following holds: $\Theta(G)\leqslant7&lt;\vartheta(G)=9$.</p>

<p>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.).</p>

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

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

<ol>
<li>W. Haemers, “<a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1056027">On some problems of Lov$\acute{a}$sz concerning the Shannon capacity of a graph</a>,” IEEE Trans. on Information Theory, vol. 25, no. 2, pp. 231–232, Mar. 1979.</li>
<li>T. Bohman, "<a href="http://www.ams.org/journals/proc/2005-133-02/S0002-9939-04-07470-2/S0002-9939-04-07470-2.pdf">A limit theorem for the Shannon capacities of odd cycles. II</a>," Proceedings of the American Mathematical Society, 2005.</li>
<li>N. Alon, "<a href="http://scholar.google.com/scholar?q=%22Combinatorial%20Reasoning%20in%20Information%20Theory%22&amp;hl=en&amp;btnG=Search&amp;as_sdt=1,5">Combinatorial Reasoning in Information Theory</a>".</li>
</ol>

CC BY-SA 2.5
2011-03-28T02:38:34.887Z
Thank you very much. Is the same known for simple odd cycles? For example $7$-sided polygon?
Turbo
CC BY-SA 2.5
2011-03-28T07:07:48.127Z
SO it is not known. This is very interesting.
Turbo
CC BY-SA 2.5
2011-03-27T19:21:27.363Z
2011-03-28T09:41:57.817Z
2011-03-28T09:41:57.817Z
Oleksandr Bondarenko
<p>The post is related to:
<a href="https://mathoverflow.net/questions/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles">https://mathoverflow.net/questions/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles</a></p>

<p>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.)</p>

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

<p><strong>Update</strong>
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)</p>

CC BY-SA 2.5
2011-03-28T07:18:34.823Z
I've delete my wrong answer. Thanks for the correction!
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2013-12-21T19:15:59.060Z
I do not understand the update, if there is a gap between zero-error capacity and $\vartheta$, how can you "lower" it?
Sasho Nikolov
CC BY-SA 3.0
2013-12-22T14:57:57.753Z
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.
Turbo
<graph-theory><it.information-theory>
Lovasz theta function and regular graphs (odd cycles in particular) - connections to spectral theory
Turbo
# Lovasz theta function and regular graphs (odd cycles in particular) - connections to spectral theory

(Asked by: username_0 on 2011-03-27)

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)

**Tags:** graph-theory, it.information-theory
> **Comments:**
> **username_1**: I've delete my wrong answer. Thanks for the correction!  
> **username_2**: I do not understand the update, if there is a gap between zero-error capacity and $\vartheta$, how can you "lower" it?  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_3 on 2011-03-27. Score: 13

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](http://en.wikipedia.org/wiki/Schl%C3%A4fli_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](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1056027),” 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](http://www.ams.org/journals/proc/2005-133-02/S0002-9939-04-07470-2/S0002-9939-04-07470-2.pdf)," Proceedings of the American Mathematical Society, 2005.
3. N. Alon, "[Combinatorial Reasoning in Information Theory](http://scholar.google.com/scholar?q=%22Combinatorial%20Reasoning%20in%20Information%20Theory%22&hl=en&btnG=Search&as_sdt=1,5)".

> **Comments:**
> **username_0**: Thank you very much. Is the same known for simple odd cycles? For example $7$-sided polygon?  
> **username_0**: SO it is not known. This is very interesting.  

---

