Improved lower bounds for the Shannon capacity of odd cycles

arXiv:2607.21517v1 Announce Type: cross 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.

Source: arXiv cs.AI | 2026-07-24