Search papers, labs, and topics across Lattice.
This paper improves the lower bounds for the Shannon capacity of odd cycles by constructing independent sets of significant size in the strong powers of cycles \(C_7\), \(C_{11}\), and \(C_{13}\). By achieving independent sets of sizes 134753, 21909, and 62530 respectively, the authors establish new lower bounds for the Shannon capacities of these graphs, surpassing previous estimates. Additionally, the research highlights the utility of Large Language Models (LLMs) in discovering explicit combinatorial constructions, showcasing an innovative intersection of AI and combinatorial optimization.
New independent set constructions push the Shannon capacity lower bounds for odd cycles, revealing the surprising power of LLMs in combinatorial discovery.
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.
