Chris Cox: Shannon capacity
Channel: Grad Student
Date: 2018-03-07

Abstract: The area of information theory is all about studying the maximum amount of information that can be transmitted across a noisy channel under various constraints. In this talk, we look at transmitting information across a channel described by a graph $G$ which dictates which symbols can be confused. More precisely, the symbols in our message are the vertices of $G$ and two symbols are confusable if they are connected by an edge of $G$. If we want to be able to transmit the message perfectly, then we must, naively, restrict the symbols that we use to an independent set in $G$. This way, any two messages sent will be distinguishable. However, sometimes by adding redundancy to our message by, for example, sending the message in chunks of size two, we can actually transmit more information. The theoretical limit on the amount of information that can be sent under this model is called the Shannon capacity of $G$, denoted by $\Theta(G)$. The Shannon capacity is notoriously difficult to calculate; despite being defined in the 50s, we still don't know the value of $\Theta(C_7)$. In fact, it's not even known if $\Theta(G)$ is computable! It isn't necessary to have any previous knowledge about information theory as Shannon capacity is really just a graph theory problem. We'll formally define $\Theta(G)$ and discuss two general upper bounds: Lov\'asz's theta function and Haemers' minimum rank.