The Shannon Capacity of the 5-Cycle

Imagine a secret agent in a terrorist camp who needs to get messages to the outside world. He has scarves of 5 colours (A,B,C,D,E), and depending on the colour of the scarf he wears each day, an intelligence team who have satellite photography of the area decipher the message.

Unfortunately, the satellite system is not perfect and tends to mix up certain colours in it's images: A may be confused with E or B, B with A or C, and so on. The confusion graph forms a 5-cycle A-B-C-D-E-A. What protocol can the agent use to transmit his messages with the highest efficiency? (in terms of #messages per symbol)

For instance, if he uses just colours A,C, then he transmits 1 bit every day and these are not confused. So he sends one of 2^k messages in k days. But there is a better protocol that allows him to transfer one of 5^(k/2) messages in k days.

In a gem of a proof, Lovasz showed that this is indeed tight, and the agent can do no better. We shall see the proof of this result in the talk.