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.

Known results and bounds for Zero-error capacity of a general confusability graph
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

Open question

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

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

Research directions

  • 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.

Formal verification

Lean coverageNot formally stated

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

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

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\)
Seven-cycle zero-error channel C7

The Shannon capacity of the seven-cycle remains unknown.

Zero error Finite alphabet Discrete memoryless Zero-error capacity Bounds only Regularized characterization
Open \(367^{1/5}\le\Theta(C_7)\le\frac{7\cos(\pi/7)}{1+\cos(\pi/7)}\)
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)\)
Binary random-insertion channel

In the fixed iid random-insertion model, each transmitted bit may be followed by one independent fair inserted bit and exact capacity is unknown.

Point-to-point Finite alphabet Binary Memory Capacity Bounds only
Open \(0\le C_{\mathrm{ins}}(p)\le1\)