OpenAlex ·
Strengthening Recursive Constructions for Zero-Error Shannon Capacity
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2608.30273
- Original
- Read it at the publisher
- Topics
Abstract
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)\ge 3.25883262\ldots$, 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Rotational Equivariance in Machine Learning: A Comprehensive Tutorial
The Truncated Octahedral Conjecture
Points of maximal traffic on a grid with obstruction
Localization of the Caro-Wei bound and its applications to bipartiteness
A new proof that more than $2/3$ of the zeros of the Riemann zeta function are simple and on the critical line
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.