Shannon Capacity

Let alpha(G) denote the independence number of a graph G. Then the Shannon capacity Theta(G), sometimes also denoted c(G), of G is defined as

 Theta(G)=lim_(k->infty)[alpha(G□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]...□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]G_()_(k))]^(1/k),

where □AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1] 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 G (Alon 1998).

Theta(G) satisfies


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

Lovász (1979) showed that the Shannon capacity of the (n,r)-Kneser graph is (n-1; r-1), that of a vertex-transitive self-complementary graph (which includes all Paley graphs) G is sqrt(|V(G)|), and that of the Petersen graph is 4.

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

See also

Graph Strong Product, Independence Number, Lovász Number, Perfect Graph, Sandwich Theorem

Explore with Wolfram|Alpha


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.á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., 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.

Referenced on Wolfram|Alpha

Shannon Capacity

Cite this as:

Weisstein, Eric W. "Shannon Capacity." From MathWorld--A Wolfram Web Resource.

Subject classifications