Abstract

The Shannon capacity $\Theta(G)$ of a graph $G$ quantifies the maximum rate at which information can be transmitted with zero error over a noisy channel. It is lower bounded by $\alpha(G^d)^{1/d}$ for any $d$, where $\alpha(G^d)$ is the independence number of the $d$-th strong product of $G$. We construct independent sets of size $134753$ in $C_7^{10}$, $21909$ in $C_{11}^{6}$, $62530$ in $C_{13}^{6}$, and $8076974$ in $C_{15}^{8}$, improving the best known lower bounds for the Shannon capacity of these graphs to $\Theta(C_7)\geq 134753^{1/10}>3.258020$, $\Theta(C_{11})\geq 21909^{1/6}>5.289773$, $\Theta(C_{13})\geq 62530^{1/6}>6.300109$, and $\Theta(C_{15})\geq 8076974^{1/8}>7.301399$. We also improve the best known lower bounds on the independence numbers of several individual strong products of odd cycles that do not improve the Shannon capacity lower bound. The constructions were discovered through iterative interactions with a Large Language Model (LLM), illustrating the potential of LLMs for finding explicit combinatorial constructions.

arXiv Link

Find our paper on arXiv:2607.21517

Recommended citation: Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, and Daniel Reichman. "Improved lower bounds for the Shannon capacity of odd cycles." arXiv preprint arXiv:2607.21517, 2026.
Download Paper | Download Bibtex