Math Conjectures

Shannon capacity of the seven-cycle

OPENMajorExact constant problemProposed 1956 · Canonical special case

Canonical statement

For finite simple graphs G,HG,H, define their strong product to have vertex set V(G)×V(H)V(G)\times V(H), with distinct (g,h)(g,h) and (g′,h′)(g',h') adjacent exactly when, in each coordinate, the entries are equal or adjacent and in at least one coordinate they are adjacent. Write G⊠kG^{\boxtimes k} for the kk-fold strong product and α(G)\alpha(G) for the maximum size of an independent vertex set. Determine exactly
Θ(C7):=sup⁡k≥1α(C7⊠k)1/k, \Theta(C_7):=\sup_{k\ge1}\alpha(C_7^{\boxtimes k})^{1/k},
where C7C_7 is the cycle on seven vertices.
View source LaTeX
For finite simple graphs \(G,H\), define their strong product to have vertex set \(V(G)\times V(H)\), with distinct \((g,h)\) and \((g',h')\) adjacent exactly when, in each coordinate, the entries are equal or adjacent and in at least one coordinate they are adjacent. Write \(G^{\boxtimes k}\) for the \(k\)-fold strong product and \(\alpha(G)\) for the maximum size of an independent vertex set. Determine exactly
\[
\Theta(C_7):=\sup_{k\ge1}\alpha(C_7^{\boxtimes k})^{1/k},
\]
where \(C_7\) is the cycle on seven vertices.
INFO-001:[Shannon1956ZeroError][Lovasz1979Capacity][PolakSchrijver2019C7][IttyEtAl2026OddCycles]
Information theoryGraph theory

Notes

Shannon introduced the zero-error capacity of a noisy channel in 1956 and observed that it reduces to a graph parameter: for a confusability graph GG, the capacity is Θ(G)=sup⁡kα(G⊠k)1/k\Theta(G)=\sup_k\alpha(G^{\boxtimes k})^{1/k}, where G⊠kG^{\boxtimes k} is the kk-fold strong product and α\alpha the independence number [Shannon1956ZeroError]. The problem asks for the exact value of Θ(C7)\Theta(C_7), the capacity of the seven-cycle.

Lovász's theta function resolved the five-cycle, giving Θ(C5)=5\Theta(C_5)=\sqrt{5}, and supplies the best known upper bound here: Θ(C7)≤7cos⁡(π/7)/(1+cos⁡(π/7))<3.3177\Theta(C_7)\le 7\cos(\pi/7)/(1+\cos(\pi/7))<3.3177 [Lovasz1979Capacity]. Lower bounds come from explicit independent sets in strong powers. Polak and Schrijver improved the lower bound using circular graphs [PolakSchrijver2019C7], and a 2026 construction of an independent set of size 134753134753 in C7⊠10C_7^{\boxtimes 10} gives Θ(C7)≥1347531/10>3.258020\Theta(C_7)\ge 134753^{1/10}>3.258020 [IttyEtAl2026OddCycles].

The seven-cycle is thus the first odd cycle whose capacity is unresolved. The gap between roughly 3.25803.2580 and 3.31773.3177 persists, and closing it requires either stronger constructions in high strong powers or an upper bound improving on the theta function.

References (4)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.