index-coding-at-most-five-messages

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.

Channel and question

Input: Up to five independent messages held by one broadcaster.
Output: One receiver per message, each with an arbitrary subset of the other messages as side information.
Law: All nonisomorphic multiple-unicast side-information patterns on at most five messages.
Quantity: Complete small-instance capacity-region classification \(\{\mathcal C(G):|V(G)|\le5\}\), measured in message symbols per broadcast symbol for each rate coordinate.

Criterion. Exact capacity region for every isomorphism class.

\[\mathcal C(G)=\mathcal R_{\mathrm{composite}}(G)\quad\text{for }|V(G)|\le5\]

Known results and bounds for Index coding with at most five messages
Result	Relation	Method	Year
Exact	\(\mathcal C(G)=\mathcal R_{\mathrm{composite}}(G)\text{ for all }\|V(G)\|\le5\)	Composite coding inner bound matched to the polymatroidal converse over all 9,846 nonisomorphic instances.	2013

Lean coverageDefinitions only

Lean declarations (2)

CapacityAtlas.IndexCoding.Instance API
lean/CapacityAtlasForMathlib/Network/IndexCoding.lean — General finite index-coding instance.
CapacityAtlas.IndexCoding.symmetricCapacity API
lean/CapacityAtlasForMathlib/Network/IndexCoding.lean — Operational zero-error symmetric capacity.

Fatemeh Arbabjolfaei, Bernd Bandemer, Young-Han Kim, Eren Sasoglu, and Lele Wang (2013). On the Capacity Region for Index Coding. IEEE International Symposium on Information Theory. DOI 10.1109/ISIT.2013.6620369.