OpenFrontiers
Join
← Back to the index
OP-12007OpenGraph theory

Shannon capacity of the 7-cycle (C9C_{9})

Shannon capacity of the 7-cycle: determine C9C_{9} or improve its bounds; the repository records 3.25883262 (lower) and 3.3177 (upper).

MSC 05C69 · Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)MSC 94A15 · Information theory (general)

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Let C7\mathcal{C}_{7} denote the cycle graph on 77 vertices. We define C9C_{9} to be the Shannon capacity of C7{\mathcal C}_{7}:

C9:=Θ(C7),C_{9} := \Theta({\mathcal C}_{7}),

where for a graph GG, the Shannon capacity Θ(G)\Theta(G) is defined by

Θ(G):=sup⁡n≥1α(G⊠n)1/n.\Theta(G) := \sup_{n \ge 1} \alpha(G^{\boxtimes n})^{1/n}.

Here α(H)\alpha(H) denotes the independence number of a graph HH, and ⊠\boxtimes is the strong graph product.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

  • Equivalently, Θ(G)\Theta(G) is the maximum zero-error information rate of a noisy channel whose confusability graph is GG.
  • Determining Θ(C2k+1)\Theta({\mathcal C}_{2k+1}) for odd cycles is a central open problem in information theory and extremal combinatorics.
  • For C5{\mathcal C}_{5}, Lovász famously proved Θ(C5)=5\Theta({\mathcal C}_{5})=\sqrt{5}, but no exact value is known for Θ(C7)\Theta({\mathcal C}_{7}).
  • It is possible that Θ(C2k+1)=ϑ(C2k+1)\Theta({\mathcal C}_{2k+1})=\vartheta({\mathcal C}_{2k+1}) for all kk, but this is currently open beyond k=2k=2.
  • [BPZ2026] also records improved lower bounds for larger odd cycles (not split out as separate constants): Θ(C11)≥5.294502522149…\Theta({\mathcal C}_{11})\ge 5.294502522149\ldots, Θ(C13)≥6.302455083464…\Theta({\mathcal C}_{13})\ge 6.302455083464\ldots, Θ(C15)≥7.301600534487…\Theta({\mathcal C}_{15})\ge 7.301600534487\ldots, Θ(C19)≥9.357192705918…\Theta({\mathcal C}_{19})\ge 9.357192705918\ldots, Θ(C21)≥10.342455853338…\Theta({\mathcal C}_{21})\ge 10.342455853338\ldots, Θ(C23)≥11.328224257774…\Theta({\mathcal C}_{23})\ge 11.328224257774\ldots.

References (from the repository page)

  • [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 C7C_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 C7C_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 C7C_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

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 3.25883262; best known upper bound 3.3177. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
7/2=3.57/2 = 3.5 [S1956] Fractional clique cover bound
ϑ(C7)≈3.3177\vartheta({\mathcal C}_{7}) \approx 3.3177 [L1979] Lovász theta-function bound

Known lower bounds

Bound Reference Comments
3 Trivial
3431/5≈3.2141343^{1/5} \approx 3.2141 [BMRRST1971]
1081/4≈3.2237108^{1/4} \approx 3.2237 [VZ2002]
3501/5≈3.2271350^{1/5} \approx 3.2271 [MO2017]
3671/5≈3.2578367^{1/5} \approx 3.2578 [PS2018] Independent set of size 367367 in C7⊠5{\mathcal C}_{7}^{\boxtimes 5}
1347531/10≈3.258020134753^{1/10} \approx 3.258020 [IRCR2026] Independent set of size 134753134753 in C7⊠10{\mathcal C}_{7}^{\boxtimes 10}; constructions at https://github.com/nathanielitty/lower-bounds-for-shannon-capacity
3.258789153908…3.258789153908\ldots [Gao2026] Recursive product of the size-367367 gadget; independent set of size M40M_{40} in C7⊠200{\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…3.258805369885\ldots [BPZ2026] Valid-tuple product in C7⊠200{\mathcal C}_{7}^{\boxtimes 200}. Lean 4 formalization: commit aa21eeb12b75 of https://github.com/spectra-research/shannon-capacity-lean
3.25883262…3.25883262\ldots [Tan2026] Heterogeneous recursion; independent set in C7⊠500{\mathcal C}_{7}^{\boxtimes 500}. Certificates: https://github.com/tandonravi/C7-Shannon-Capacity-Heterogeneous-Recursion
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Shannon capacity of the 7-cycle ($C_{9}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.