Shannon capacity of the seven-cycle

Importance: High ✭✭✭
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: tchow
on: February 19th, 2009

\begin{problem} What is the Shannon capacity of $C_7$? \end{problem}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}

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.$$


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries) [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.