LLM-Guided Search Improves 30-Year-Old Shannon Capacity Bounds for Odd Cycles C7, C11, and C13

arXiv 2607.21517·medium signal

Itty, Rosin, Carstensen and Reichman constructed independent sets of size 134,753 in C7^10, 21,909 in C11^6, and 62,530 in C13^6, raising the best known Shannon capacity lower bounds to Θ(C7) > 3.258020, Θ(C11) > 5.289773, and Θ(C13) > 6.300109. The constructions were discovered through iterative interactions with a large language model, making this a concrete instance of LLM-assisted discovery producing verifiable, checkable combinatorial objects rather than plausible-sounding prose. The result is independently verifiable — an independent set either exists at that size or it doesn't — which sidesteps the usual credibility problem with claimed AI-assisted math results.