Improved lower bounds for the Shannon capacity of odd cycles

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 power of $G$. We construct independent sets of size $134753$ in $C_7^{10}$, $21909$ in $C_{11}^{6}$, and $62530$ in $C_{13}^{6}$, 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$, and $\Theta(C_{13})\geq 62530^{1/6}>6.300109$. We also improve the best known lower bounds on the independence numbers of several individual strong powers 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.

Information Theory (cs.IT); Artificial Intelligence (cs.AI); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

arXiv:2607.21517 [cs.IT]

(or arXiv:2607.21517v1 [cs.IT] for this version)

https://doi.org/10.48550/arXiv.2607.21517 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.