New Lower Bounds for the Shannon Capacity of Odd Cycles

Abstract

The Shannon capacity of a graph $G$ is defined as $c(G)={\sup }_{d\ge 1}(\alpha (G^d){)}^{\frac{1}{d}},$ where $\alpha (G)$ is the independence number of $G$. The Shannon capacity of the cycle $C_5$ on $5$ vertices was determined by Lovász in 1979, but the Shannon capacity of a cycle $C_p$ for general odd $p$ remains one of the most notorious open problems in information theory. By prescribing stabilizers for the independent sets in $C_p^d$ and using stochastic search methods, we show that $\alpha (C_7^5)\ge 350$, $\alpha (C_{11}^4)\ge 748$, $\alpha (C_{13}^4)\ge 1534$ and $\alpha (C_{15}^3)\ge 381$. This leads to improved lower bounds on the Shannon capacity of $C_7$ and $C_{15}$: $c(C_7)\ge 350^{\frac{1}{5}}>3.2271$ and $c(C_{15})\ge 381^{\frac{1}{3}}>7.2495$.