AI summaryⓘ
The authors focus on a long-standing problem in information theory about finding how much information can be sent without errors using odd cycle graphs, especially the seven-node cycle. They build on recent AI-driven methods that create large sets of non-adjacent nodes (independent sets) in products of these graphs, improving the known lower bounds. Their main idea is to let different parts of the construction use different auxiliary structures to better help future recursive steps, rather than using a uniform approach. By applying this new method to the seven-cycle graph, they improved the best known lower bound for its Shannon capacity. Their work also shows a broader lesson: intermediate structures that look the same at one step can have different value later depending on their role in the recursion.
Shannon capacityodd cycle graphzero-error information theoryindependent setgraph powersrecursive constructionC7 cycleAI-assisted methods
Abstract
The exact Shannon capacity is unknown for every odd cycle beyond the five-cycle $C_5$, making odd cycles a central open problem in zero-error information theory. Improving the known lower bounds requires constructing large independent sets in strong powers of these graphs. Recent AI-assisted work has produced a rapid sequence of improvements: building on the construction of Itty et al., Gao developed a recursive product construction for combining structured independent sets, and Buys, Polak, and Zuiddam (BPZ) subsequently strengthened this through a richer recursion framework. We continue this line of AI-assisted exploration and introduce a heterogeneous refinement of these constructions. The central observation is that the usefulness of an intermediate construction depends not only on the size of its current main independent set, but also on the auxiliary structure it carries into subsequent recursion. Consequently, different parts of that auxiliary structure need not use the same independent set, and different occurrences in a recursion need not use the same intermediate representation. We formalize this for Gao's binary product and derive explicit propagation rules showing how heterogeneous choices strengthen the resulting gadget while leaving its current code size unchanged, then extend the principle to the more general BPZ framework, tailoring constructions to the distinct roles they play within the recursion. Applying these refinements to the seven-cycle $C_7$, we obtain an independent set in $C_7^{\boxtimes 500}$ yielding $Θ(C_7)\ge 3.25883262\ldots$, improving the best known lower bound. Beyond the numerical gain, the results illustrate a general principle for recursive zero-error constructions: intermediate structures with the same dimension and current code size can have different downstream value depending on where and how they are used in the recursion.