Improved lower bounds for the Shannon capacity of odd cycles

Source

Source name: arXiv
Source kind: paper
Authors / organization: Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman
Venue: arXiv: cs.IT
Published: 2026-07-23
Collected: 2026-07-24
URL: http://arxiv.org/abs/2607.21517v1
PDF: https://arxiv.org/pdf/2607.21517v1
DOI: UNKNOWN

Plain-Language Brief

Researchers have improved lower bounds for the Shannon capacity of odd cycles, which quantifies the maximum rate at which information can be transmitted with zero error over a noisy channel. They achieved this by constructing independent sets in certain odd cycle graphs, leading to improved lower bounds for the Shannon capacities of these graphs.

What the Document Says

The authors discuss the Shannon capacity of a graph G, which is lower bounded by α(G^d)^{1/d} for any d.
They constructed independent sets of size 134753 in C_7^{10}, 21909 in C_{11}^{6}, and 62530 in C_{13}^{6}
This led to improved lower bounds for the Shannon capacity of these graphs: Θ(C_7)≥ 134753^{1/10} > 3.258020, Θ(C_{11})≥ 21909^{1/6} > 5.289773, and Θ(C_{13})≥ 62530^{1/6} > 6.300109
The authors also improved 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)
This illustrates the potential of LLMs for finding explicit combinatorial constructions

Key Concepts Mentioned

Shannon capacity
graph
independent sets
odd cycles
iterative interactions
Large Language Model

Claims Made by the Document

The authors improved lower bounds for the Shannon capacity of certain odd cycle graphs.
They discovered these constructions through iterative interactions with a Large Language Model.

Evidence Used

Construction of independent sets of size 134753 in C_7^{10}, 21909 in C_{11}^{6}, and 62530 in C_{13}^{6}
Improved lower bounds for the Shannon capacity of these graphs: Θ(C_7)≥ 134753^{1/10} > 3.258020, Θ(C_{11})≥ 21909^{1/6} > 5.289773, and Θ(C_{13})≥ 62530^{1/6} > 6.300109

Methods / Approach

UNKNOWN

Limitations Stated by the Authors

UNKNOWN

Limitations Noted by the Agent

Agent interpretation — not from the source.

UNKNOWN

Open Questions

UNKNOWN

Notes for Future Q&A

May include interpretation. Labeled where it does.

UNKNOWN

Raw Abstract / Excerpt

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.