Shannon capacity of the 7-cycle
Description of constant
Let $\mathcal{C}_{7}$ denote the cycle graph on $7$ vertices. We define $C_{9}$ to be the Shannon capacity of ${\mathcal C}_{7}$:
\[C_{9} := \Theta({\mathcal C}_{7}),\]where for a graph $G$, the Shannon capacity $\Theta(G)$ is defined by \(\Theta(G) := \sup_{n \ge 1} \alpha(G^{\boxtimes n})^{1/n}.\) Here $\alpha(H)$ denotes the independence number of a graph $H$, and $\boxtimes$ is the strong graph product.
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $\vartheta({\mathcal C}_{7}) \approx 3.3177$ | [L1979] | Lovász theta-function bound |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| 3 | Trivial | |
| $343^{1/5} \approx 3.2141$ | [BMRRST1971] | |
| $108^{1/4} \approx 3.2237$ | [VZ2002] | |
| $350^{1/5} \approx 3.2271$ | [MO2017] | |
| $367^{1/5} \approx 3.2578$ | [PS2018] |
Additional comments and links
- Equivalently, $\Theta(G)$ is the maximum zero-error information rate of a noisy channel whose confusability graph is $G$.
- Determining $\Theta({\mathcal C}_{2k+1})$ for odd cycles is a central open problem in information theory and extremal combinatorics.
- For ${\mathcal C}{5}$, Lovász famously proved $\Theta({\mathcal C}{5})=\sqrt{5}$, but no exact value is known for $\Theta({\mathcal C}_{7})$.
- It is widely conjectured that $\Theta({\mathcal C}{2k+1})=\vartheta({\mathcal C}{2k+1})$ for all $k$, but this is currently open beyond $k=2$.
References
- [BMRRST1971] L. Baumert, R. McEliece, E. Rodemich, H. Rumsey, R. Stanley, H. Taylor, A combinatorial packing problem, Computers in Algebra and Number Theory, American Mathematical Society, Providence, RI (1971), 97–108.
- [L1979] Lovász, L. On the Shannon capacity of a graph. IEEE Transactions on Information Theory 25 (1979), 1–7.
- [PS2018] Sven Polak, Alexander Schrijver, New lower bound on the Shannon capacity of $C_{9}$ from circular graphs, arXiv:1808.07438.
- [MO2017] K.A. Mathew, P.R.J. Östergård, New lower bounds for the Shannon capacity of odd cycles, ¨ Designs, Codes and Cryptography, 84 (2017), 13–22.
- [VZ2002] A. Vesel, J. Zerovnik, Improved lower bound on the Shannon capacity of $C_{9}$, Information Processing Letters, 81 (2002), 277–282.
Contribution notes
ChatGPT DeepResearch was used to prepare an initial version of this page.