Zero-error capacities and graph-capacity benchmarks

Zero-error communication requires perfectly distinguishable messages at every blocklength, unlike vanishing-error Shannon transmission. Classical messages, quantum states, entanglement assistance, one-shot transmission and asymptotic rates define different quantities.

Classically, an independent-set problem on strong graph powers defines $\Theta(G)$, while the capacity in bits per use is $\log_2\Theta(G)$. Lovász settled the five-cycle; the seven-cycle remains a benchmark. Quantum channels lead to noncommutative graphs/operator systems and quantum Lovász-type SDP bounds. Established superactivation and entanglement-assisted enhancements show that zero-error resources can behave very differently from ordinary capacities.

Preprint progress (31 August 2026): Tandon claims a certified independent set in the 500th strong power of the seven-cycle, yielding $\Theta(C_7)\geq3.25883262\ldots$. This is a classical graph-capacity lower bound, not a bit rate or a generic quantum-capacity theorem; the exact value remains unresolved.

The active programme is computable bounds and matching characterizations in stated models. Specialized zero-error undecidability results must not be transferred to ordinary memoryless quantum capacity in C1/U4.

Source disclosures

Tandon reports ChatGPT and Claude use for constructions, proof development/checks, implementation and writing, and supplies exact computations and machine-readable certificates under author responsibility. Source

Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.

preprint: Certified classical seven-cycle Shannon-capacity lower bound from an independent set in a 500th strong power, not an exact capacity. Evidence