Shannon Capacity

Let  denote the independence number of a graph . Then the Shannon capacity , sometimes also denoted , of  is defined as

where  denoted the graph strong product (Shannon 1956, Alon and Lubetzky 2006). The Shannon capacity is an important information theoretical parameter because it represents the effective size of an alphabet in a communication model represented by a graph  (Alon 1998).

 satisfies

The Shannon capacity is in general very difficult to calculate (Brimkov et al. 2000). In fact, the Shannon capacity of the cycle graph  was not determined as  until 1979 (Lovász 1979), and the Shannon capacity of  is perhaps one of the most notorious open problems in extremal combinatorics (Bohman 2003).

Lovász (1979) showed that the Shannon capacity of the -Kneser graph is , that of a vertex-transitive self-complementary graph (which includes all Paley graphs)  is , and that of the Petersen graph is 4.

All graphs whose Shannon capacity is known attain their capacity either at  (i.e., at their independence number; e.g., perfect graphs),  (e.g., self-complementary vertex-transitive graphs-including the Paley graphs), or else do not attain it at any value of  (e.g., the graph union of the cycle graph  with a singleton graph) (Alon and Lubetzky 2006).

REFERENCES

Alon, N. "Explicit Ramsey Graphs and Orthonormal Labelings." Elec. J. Combin. 1, No. R12, 1-8, 1994.

Alon, N. "The Shannon Capacity of a Union." Combinatorica 18, 301-310, 1998.

Alon, N. and Lubetzky, E. "The Shannon Capacity of a Graph and the Independence Numbers of Its Powers." IEEE Trans. Inform. Th. 52, 2172-2176, 2006.

Bohman, T. "A Limit Theorem for the Shannon Capacities of Odd Cycles. I." Proc. Amer. Math. Soc. 131, 3559-3569, 2003.

Bohman, T. and Holzman, R. "A Nontrivial Lower Bound on the Shannon Capacities of the Complements of Odd Cycles." IEEE Trans. Inform. Th. 49, 721-722, 2003.

Brimkov, V. E.; Codenotti, B.; Crespi, V.; and Leoncini, M. "On the Lovász Number of Certain Circulant Graphs." In Algorithms and Complexity. Papers from the 4th Italian Conference (CIAC 2000) Held in Rome, March 1-3, 2000 (Ed. G. Bongiovanni, G. Gambosi, and R. Petreschi). Berlin: Springer-Verlag, pp. 291-305, 2000.

Haemers, W. "An Upper Bound for the Shannon Capacity of a Graph." In Algebraic Methods in Graph Theory. Szeged, Hungary: pp. 267-272, 1978.

Haemers, W. "On Some Problems of Lovász Concerning the Shannon Capacity of a Graph." IEEE Trans. Inform. Th. 25, 231-232, 1979.

Knuth, D. E. "The Sandwich Theorem." Electronic J. Combinatorics 1, No. 1, A1, 1-48, 1994. http://www.combinatorics.org/Volume_1/Abstracts/v1i1a1.html.Lovász, L. "On the Shannon Capacity of a Graph." IEEE Trans. Inform. Th. IT-25, 1-7, 1979.

Riis, S. "Graph Entropy, Network Coding and Guessing." 27 Nov 2007. http://arxiv.org/abs/0711.4175v1.

Schrijver, A. "A Comparison of the Delsarte and Lovász Bounds." IEEE Trans. Inform. Th. 25, 425-429, 1979.

Shannon, C. E. "The Zero-Error Capacity of a Noisy Channel." IRE Trans. Inform. Th. 2, 8-19, 1956.van Lint, J. H. and Wilson, R. M. A Course in Combinatorics. New York: Cambridge University Press, 1992.