6.8 ***Shannon rate of communication***

See [Aigner et al. 2010, Chapter 37] for more details. Suppose $V$ is a set of symbols to be communicated over a network. However, some symbols are likely to be confused. How best to choose a set of symbols that cannot be confused ? Place an edge between two symbols that can be confused and form a graph $G$. Let us call $G$, the confusion graph. A set of symbols that cannot be confused is an independent set. Best strategy for communication is to choose independent set.

A different question leading to the same answer. $V$ is set of people trying to communicate but two neighbours cannot communicate at the same time. The best strategy is to choose an indepndent set of vertices and they can communicate at the same time.

In the first problem, if we are allowed to communicate over multiple rounds, can we do better ?

Given graphs $G,H$, define $G\times H$ as the graph with vertex set $V(G)\times V(H)$ and edges $(u_1,u_2)\sim (v_1,v_2)$ if $(u-1,v_1)\ne (u_2,v_2)$ and $u_i\sim v_i,i=1,2$. Then, the confusion graph for strings of length $2$ is $G^2:=G\times G$. Similarly, the confusion graph for strings of length $n$ is $G^n$.

TO BE COMPLETED