Strengthening Recursive Constructions for Zero-Error Shannon Capacity
Abstract
The exact Shannon capacity is unknown for every odd cycle beyond the five-cycle C5, 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 C7, we obtain an independent set in C7boxtimes 500 yielding Θ(C7)≥ 3.25883262…, 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.
Related
- Sunflower-Free Uniform Families: Recursive Constructions and Explicit Bounds
- Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation
- Shannon Capacity and Related Graph Invariants for Lexicographic Products
- Unlocking Exponential and Unbounded Robust Gains in Shannon Capacity of Classical Multiple Access Channels with Causal CSIT via Quantum Entanglement Assistance
- Error-Correcting Weakly Constrained Codes: Constructions and Achievable Rates
BibTeX
@misc{tandon2026strengthening,
title = {{Strengthening Recursive Constructions for Zero-Error Shannon Capacity}},
author = {Ravi Tandon},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.30273},
eprint = {2608.30273},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.30273},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Strengthening Recursive Constructions for Zero-Error Shannon Capacity
AU - Ravi Tandon
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.30273
UR - https://arxiv.org/abs/2608.30273
AB - 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)≥ 3.25883262…, 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.
ER -