通过智能构造提升奇数环图的香农容量下界，突破此前理论极限。
Improved lower bounds for the Shannon capacity of odd cycles
- 利用大语言模型迭代生成独立集，优化强积图中的独立数。
- 在C7^10等图中构造出超百万级独立集，使香农容量下界提升至3.258以上。
- 方法可复用于其他组合优化问题，适合对理论构造感兴趣的学者。
图G的香农容量Θ(G)衡量在噪声信道中实现零错误传输的信息最大速率。它由α(G^d)^{1/d}下界，其中α(G^d)是G的d阶强积图的独立数。本文在C_7^{10}中构造出大小为134753的独立集，在C_{11}^{6}中构造出21909，在C_{13}^{6}中构造出62530，在C_{15}^{8}中构造出8076974，从而将相应图的香农容量下界提升至Θ(C_7)≥134753^{1/10}>3.258020，Θ(C_{11})≥21909^{1/6}>5.289773，Θ(C_{13})≥62530^{1/6}>6.300109，Θ(C_{15})≥8076974^{1/8}>7.301399。还改进了多个奇数环强积图的独立数下界，但未提升香农容量。构造过程借助大语言模型（LLM）的迭代交互完成，展示了其在发现显式组合构造中的潜力。
原文摘要 · Abstract (English)
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 product of $G$. We construct independent sets of size $134753$ in $C_7^{10}$, $21909$ in $C_{11}^{6}$, $62530$ in $C_{13}^{6}$, and $8076974$ in $C_{15}^{8}$, 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$, $Θ(C_{13})\geq 62530^{1/6}>6.300109$, and $Θ(C_{15})\geq 8076974^{1/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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。