Megan Owen (Cornell)

Combinatorics in Information Theory

Abstract for the Combinatorics Seminar
2006 March 9

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.


To the Combinatorics Seminar Web page.