2026/07/23 by Nathaniel Itty, Christopher D. Rosin, Chase Carstensen +1 · 1 citation
Computer Science · Mathematics · #cs.AI #cs.DM #cs.IT #math.CO #math.IT
v2: added improvement on lower bound for the Shannon capacity of C15
arxiv created 2026/07/30 · arxiv updated 2026/07/31
The Shannon capacity Θ(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 α(Gd)1/d for any d, where α(Gd) is the independence number of the d-th strong product of G. We construct independent sets of size 134753 in C710, 21909 in C116, 62530 in C136, and 8076974 in C158, improving the best known lower bounds for the Shannon capacity of these graphs to Θ(C7)≥ 1347531/10>3.258020, Θ(C11)≥ 219091/6>5.289773, Θ(C13)≥ 625301/6>6.300109, and Θ(C15)≥ 80769741/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.