Importance: High ✭✭✭
 Author(s):
 Subject: Graph Theory
 Keywords:
 Posted by: tchow on: February 19th, 2009
Problem   What is the Shannon capacity of ?

Let denote the independence number of the graph , and let denote the strong graph product of and (in which is adjacent to if and is adjacent to , or if and is adjacent to , or if is adjacent to and is adjacent to ). Then the Shannon capacity of is defined by where the strong graph product is over copies of . The Shannon capacity is important because it represents the effective size of an alphabet in a communication model represented by , but it is notoriously difficult to compute. Lovász [L] famously proved that the Shannon capacity of the five-cycle is , but even the Shannon capacity of remains unknown. However, Bohman [B] has shown that

## Bibliography

[B] Tom Bohman, A limit theorem for the Shannon capacity of odd cycles II, Proc. Amer. Math. Soc. 133 (2005), no. 2, 537-543.

[L] László Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Th. IT-25 (1979), 1-7.

* indicates original appearance(s) of problem.