Improved lower bounds for the Shannon capacity of odd cycles

📄 arXiv: 2607.21517v1 📥 PDF

作者: Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

分类: cs.IT, cs.AI, cs.DM, math.CO

发布日期: 2026-07-23

💡 一句话要点

通过构造独立集提升奇数环的香农容量下界

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 香农容量 奇数环 独立集 组合数学 信息理论 大型语言模型 图论

📋 核心要点

  1. 现有方法在奇数环的香农容量下界上存在不足，未能充分利用独立集的构造。
  2. 论文通过构造独立集，提出了一种新的方法来提升奇数环的香农容量下界。
  3. 主要结果显示，C_7^{10}、C_{11}^{6}和C_{13}^{6}的香农容量下界均有显著提升，分别超过3.258020、5.289773和6.300109。

📝 摘要（中文）

香农容量Θ(G)量化了在噪声信道上以零错误传输信息的最大速率。本文通过构造独立集，提升了奇数环图C_7^{10}、C_{11}^{6}和C_{13}^{6}的香农容量下界，分别达到Θ(C_7)≥134753^{1/10}、Θ(C_{11})≥21909^{1/6}和Θ(C_{13})≥62530^{1/6}。此外，论文还改进了若干奇数环的强幂的独立数下界，展示了大型语言模型在组合构造中的潜力。

🔬 方法详解

问题定义：本文旨在提升奇数环图的香农容量下界，现有方法未能有效构造足够大的独立集以实现这一目标。

核心思路：通过构造特定的独立集，论文提出了一种新的方法来提高奇数环的香农容量下界，利用组合数学的原理进行创新。

技术框架：研究首先定义了奇数环的强幂，然后通过迭代与大型语言模型的交互，发现并构造出新的独立集，最终计算出香农容量下界。

关键创新：论文的创新在于通过大型语言模型辅助发现独立集的构造方法，这一方法在组合构造领域具有潜在的广泛应用。

关键设计：在构造独立集时，论文详细设计了独立集的大小和结构，确保其满足香农容量下界的要求。

🖼️ 关键图片

img_0
img_1
img_2

📊 实验亮点

实验结果显示，论文成功构造了C_7^{10}中的独立集大小为134753，C_{11}^{6}为21909，C_{13}^{6}为62530，显著提升了这些图的香农容量下界，分别超过3.258020、5.289773和6.300109，展示了新方法的有效性。

🎯 应用场景

该研究的潜在应用领域包括通信网络设计、信息理论以及组合优化等。通过提升香农容量下界，可以为更高效的信息传输方案提供理论支持，推动相关技术的发展与应用。

📄 摘要（原文）

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 $α(G^d)^{1/d}$ for any $d$, where $α(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 $Θ(C_7)\geq 134753^{1/10}>3.258020$, $Θ(C_{11})\geq 21909^{1/6}>5.289773$, and $Θ(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.