Problem of the Week
Hilton Memorial Lecture
Arising from problems in electrical engineering, Information Theory is not often linked with combinatorics. Nevertheless, certain information theory problems, such as compressing a data source with an ambiguous alphabet, can be thought of as graph colouring problems. In this talk I will survey some of those connections. I will also explain the related concepts of graph entropy and complementary graph entropy, and their relationship to perfect graphs. Finally, I will mention some open problems in information theory that may be of interest to combinatorists, particularly graph theorists. No knowledge of information theory is assumed.