Open Problem Garden

Importance: High ✭✭✭

Author(s):

Subject:

Keywords:

Recomm. for undergrads: no

Posted	by:	tchow
	on:	February 19th, 2009

Problem What is the Shannon capacity of $C_7$ ?

Let $\alpha(G)$ denote the independence number of the graph $G$ , and let $G*H$ denote the strong graph product of $G$ and $H$ (in which $(g,h)$ is adjacent to $(g',h')$ if $g=g'$ and $h$ is adjacent to $h'$ , or if $h=h'$ and $g$ is adjacent to $g'$ , or if $g$ is adjacent to $g'$ and $h$ is adjacent to $h'$ ). Then the Shannon capacity of $G$ is defined by $\theta(G) = \lim_{k\to\infty} \biggl({\alpha(G*G*\cdots*G) \over k}\biggr)^{1/k},$ where the strong graph product is over $k$ copies of $G$ . The Shannon capacity is important because it represents the effective size of an alphabet in a communication model represented by $G$ , but it is notoriously difficult to compute. Lovász [L] famously proved that the Shannon capacity of the five-cycle $C_5$ is $\sqrt{5}$ , but even the Shannon capacity of $C_7$ remains unknown. However, Bohman [B] has shown that $\lim_{k\to\infty}(k+(1/2)-\theta(C_{2k+1}))=0.$