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).
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).
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." Combinatorica18, 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. Combinatorics1, 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.
denote the independence number of a graph
. Then the Shannon capacity 
, sometimes also denoted 
, of 
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),](/images/equations/ShannonCapacity/NumberedEquation1.svg)
![□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]](/images/equations/ShannonCapacity/Inline6.svg)
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).
is bounded from below by the
independence number
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).
-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.
(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).
