CCapacity Atlas
graph-zero-error-capacity

Zero-error capacity of a general confusability graph

For a finite confusability graph, the regularized independence number defines capacity but is difficult to compute or characterize.

Zero error Finite alphabet Discrete memoryless Zero-error capacity Regularized characterization Bounds only

Channel and question

Input
Vertices of a finite graph G.
Output
Outputs identify which pairs of inputs are confusable.
Law
Blocklength-n zero-error codes are independent sets in the strong power of G.
Quantity
Shannon graph capacity \(\Theta(G)\), measured in multiplicative alphabet growth; log2 gives bits per use.

Criterion. Asymptotic zero-error communication.

  • Error probability is exactly zero.
  • The confusability graph is finite.

Current status

\[\Theta(G)=\sup_{n\ge1}\alpha(G^{\boxtimes n})^{1/n}\]

No general finite-letter formula or efficient exact algorithm is known.

ResultRelationMethodYear
Lower\(\alpha(G)\le\Theta(G)\)Repeat a one-shot independent set.1956
Upper\(\Theta(G)\le\vartheta(G)\)A semidefinite graph parameter that is multiplicative under strong product.1979

Research frontier

Compute or sharply characterize Shannon capacity for broad graph classes and explicit unresolved graphs.

Why it remains open. Strong powers create combinatorial structure across arbitrarily many uses, and standard graph parameters can leave persistent gaps.

What would count as progress

  • Resolve a concrete small graph whose capacity is unknown.
  • Find a new multiplicative upper bound below Lovász theta.
  • Formalize graph-channel equivalence and the pentagon theorem.

Lean formalization

Canonical statementNone

Version 1 · Lean. The canonical statement should reuse Mathlib graph products and a shared zero-error code definition.

Substantial proofs0 linked

No external Lean proof is registered. Proofs longer than roughly 50 lines or requiring problem-specific infrastructure should live in a dedicated repository and link back to this statement version.

History

  1. Lavi and Sason surveyed recent advances and obtained exact values and new bounds for several graph families.

References

  1. Claude E. Shannon (1956). The Zero Error Capacity of a Noisy Channel. IRE Transactions on Information Theory. DOI 10.1109/TIT.1956.1056798.
  2. László Lovász (1979). On the Shannon Capacity of a Graph. IEEE Transactions on Information Theory. DOI 10.1109/TIT.1979.1055985.
  3. Nitay Lavi and Igal Sason (2026). Advances in the Shannon Capacity of Graphs. AIMS Mathematics. DOI 10.3934/math.2026111.

Discussion

Thread key: capacityatlas:graph-zero-error-capacity

Find discussionStart discussion

Related problems

Pentagon zero-error channel C5

The confusability graph is a five-cycle, whose Shannon capacity is exactly the square root of five.

Zero error Finite alphabet Discrete memoryless Zero-error capacity Exact Regularized characterization
Solved \(\Theta(C_5)=\sqrt5,\qquad C_0(C_5)=\frac12\log_2 5\)
Binary deletion channel BDC

Each input bit is independently deleted without an erasure marker; the exact capacity is unknown for every nontrivial deletion probability.

Point-to-point Binary Finite alphabet Memory Deletion Capacity Bounds only
Open \(0.1221(1-d)<C_{\mathrm{del}}(d)\le0.3578(1-d)\)
Discrete memoryless multiple-access channel with feedback

Common noiseless output feedback lets distributed encoders cooperate, but the general capacity region is unknown.

Multiple access Finite alphabet Discrete memoryless Feedback Capacity region Bounds only
Open \(\mathcal R_{\mathrm{CL}}\subseteq\mathcal C_{\mathrm{MAC,fb}}\subseteq\mathcal R_{\mathrm{DB}}\)
Discrete memoryless two-way channel

Two terminals exchange messages while adapting each input to their own past observations.

Two-way Finite alphabet Discrete memoryless Feedback Capacity region Bounds only
Open \(\mathcal R_{\mathrm{Shannon,in}}\subseteq\mathcal C_{\mathrm{TWC}}\subseteq\mathcal R_{\mathrm{Shannon,out}}\)