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 |
|---|---|---|
| $7/2 = 3.5$ | [S1956] | Fractional clique cover bound |
| $\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] | Independent set of size $367$ in ${\mathcal C}_{7}^{\boxtimes 5}$ |
| $134753^{1/10} \approx 3.258020$ | [IRCR2026] | Independent set of size $134753$ in ${\mathcal C}_{7}^{\boxtimes 10}$; constructions at https://github.com/nathanielitty/lower-bounds-for-shannon-capacity |
| $3.258789153908\ldots$ | [Gao2026] | Recursive product of the size-$367$ gadget; independent set of size $M_{40}$ in ${\mathcal C}_{7}^{\boxtimes 200}$. Verification code: commit b13031ba76e3 of https://github.com/xyz2606/recursive_construction_of_the_Shannon_capacity_of_C_7 |
| $3.258805369885\ldots$ | [BPZ2026] | Valid-tuple product in ${\mathcal C}_{7}^{\boxtimes 200}$. Lean 4 formalization: commit aa21eeb12b75 of https://github.com/spectra-research/shannon-capacity-lean |
| $3.25883262\ldots$ | [Tan2026] | Heterogeneous recursion; independent set in ${\mathcal C}_{7}^{\boxtimes 500}$. Certificates: https://github.com/tandonravi/C7-Shannon-Capacity-Heterogeneous-Recursion |
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 possible that $\Theta({\mathcal C}_{2k+1})=\vartheta({\mathcal C}_{2k+1})$ for all $k$, but this is currently open beyond $k=2$.
- [BPZ2026] also records improved lower bounds for larger odd cycles (not split out as separate constants): $\Theta({\mathcal C}_{11})\ge 5.294502522149\ldots$, $\Theta({\mathcal C}_{13})\ge 6.302455083464\ldots$, $\Theta({\mathcal C}_{15})\ge 7.301600534487\ldots$, $\Theta({\mathcal C}_{19})\ge 9.357192705918\ldots$, $\Theta({\mathcal C}_{21})\ge 10.342455853338\ldots$, $\Theta({\mathcal C}_{23})\ge 11.328224257774\ldots$.
References
- [S1956] C. Shannon. The zero error capacity of a noisy channel. IRE Transactions on Information Theory, vol. 2, no. 3 (1956), 8-19. doi: 10.1109/TIT.1956.1056798
- [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_7$ from circular graphs. Information Processing Letters, 143 (2019), 37-40. 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_7$. Information Processing Letters, 81 (2002), 277–282.
- [IRCR2026] N. Itty, C. D. Rosin, C. Carstensen, D. Reichman. Improved lower bounds for the Shannon capacity of odd cycles. 2026. arXiv:2607.21517
- [Gao2026] Y. Gao. A recursive construction improving the lower bound on the Shannon capacity of $C_7$. 2026. arXiv:2607.27869
- [BPZ2026] P. Buys, S. Polak, J. Zuiddam. Lean-verified lower bounds for the Shannon capacity of odd cycles. 2026. arXiv:2607.29681
- [Tan2026] R. Tandon. Strengthening recursive constructions for zero-error Shannon capacity. 2026. arXiv:2608.30273
Contribution notes
ChatGPT DeepResearch was used to prepare an initial version of this page. The July–August 2026 lower-bound cascade was added from the cited arXiv texts (abstracts, theorems, and construction sizes checked against the papers).