CCapacity Atlas
five-cycle-index-coding

Undirected five-cycle index-coding problem

Each of five receivers knows its two neighbours and asks for its own independent message.

Index coding Finite alphabet Side information Multiple unicast Nonlinear coding Symmetric capacity Exact

Channel and question

Input
Five independent equal-length messages.
Output
A common noiseless broadcast word and the two adjacent side-information messages.
Law
Receiver r requests message r and knows messages r-1 and r+1 modulo five.
Quantity
Undirected five-cycle index-coding problem capacity \(C_{\mathrm{sym}}\), measured in message symbols per broadcast symbol.

Criterion. Unrestricted zero-error block codes.

  • Zero error is required for every message tuple.
  • Finite alphabets and vector block codes are unrestricted and need not be linear.
  • This is an index-coding problem, not the pentagon confusability-channel problem.

Current status

\[C_{\mathrm{sym}}=2/5\]
Known results and bounds for Undirected five-cycle index-coding problem
ResultRelationMethodYear
Exact\(C_{\mathrm{sym}}=2/5\)Vector coding achievability and an entropy-submodularity converse.2010

Formal verification

Lean coverageFormally stated

Concrete operational definitions and admitted research statements are present. Existing proofs are preserved. New statements require mathematical review and proof completion.

Claims

  • The undirected five-cycle has unrestricted zero-error symmetric capacity 2/5.
    operational-capacity · exact capacity · solved · Formally stated · v1
Lean declarations (1)

References

  1. Anna Blasiak, Robert Kleinberg, and Eyal Lubetzky (2010). Index Coding via Linear Programming. arXiv preprint, revised 2011.

Discussion

Find discussionStart discussion

Related problems

Directed-cycle index-coding problem

Each receiver in a directed cycle knows its successor message and requests its own message.

Index coding Finite alphabet Side information Multiple unicast Nonlinear coding Symmetric capacity Exact
Solved \(C_{\mathrm{sym}}=1/(m-1)\)
Index coding with at most five messages

The capacity regions of all 9,846 nonisomorphic index-coding instances with at most five messages are covered by a finite classification.

Index coding Finite alphabet Multiple unicast Side information Capacity region Exact Single-letter characterization
Solved \(\mathcal C(G)=\mathcal R_{\mathrm{composite}}(G)\quad\text{for }|V(G)|\le5\)
Sun-Jafar 11-message multiple-unicast index-coding instance SJ11

The linear-encoder symmetric capacity is known, while unrestricted nonlinear capacity remains open.

Index coding Finite alphabet Multiple unicast Non-Shannon inequalities Nonlinear coding Symmetric capacity Bounds only Linear-encoder-only result
Open \(\frac5{13}\le C_{\mathrm{sym}}\le\frac{11}{28}\)
Sun-Jafar six-message groupcast index-coding instance SJ6-GC

A six-message, ten-receiver groupcast instance has linear-encoder capacity 5/13 and a non-Shannon nonlinear upper bound 11/28.

Index coding Finite alphabet Non-Shannon inequalities Nonlinear coding Symmetric capacity Bounds only Linear-encoder-only result
Open \(\frac5{13}\le C_{\mathrm{sym}}\le\frac{11}{28}\)