通过优化递归构造中的中间结构,提升奇数环的零错误容量下界。
Strengthening Recursive Constructions for Zero-Error Shannon Capacity

- 引入异质化递归策略,允许不同部分使用不同独立集。
- 在七元环500次强幂中构造出大小为3.25883262的独立集。
- 揭示了中间结构使用方式影响最终性能的通用原则。
除五元环外,所有奇数环的精确香农容量均未知,使其成为零错误信息论的核心难题。提升已知下界需在这些图的强幂中构造大独立集。近期基于AI的探索快速推进:在Itty等人工作基础上,Gao提出递归乘积构造以组合结构化独立集,随后Buys、Polak与Zuiddam(BPZ)通过更丰富的递归框架进一步强化。本文延续此路线,提出异质化改进方案。核心观察是:中间构造的效用不仅取决于当前主独立集大小,还与其携带的辅助结构有关。因此,辅助结构各部分可采用不同独立集,递归中不同位置亦可采用不同中间表示。我们针对Gao的二元乘积形式化该思想,推导出显式传播规则,展示异质选择如何增强生成装置而保持当前码长不变;并拓展至更一般的BPZ框架,依其在递归中的角色定制构造。应用于七元环 $C_7$,获得 $C_7^{oxtimes 500}$ 中大小为 $3.25883262\ldots$ 的独立集,突破现有下界。除数值提升外,结果揭示通用原则:相同维数与码长的中间结构,因递归中使用位置和方式不同,具有不同下游价值。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。