Appears in collection : Shannon 100

In 1956 Claude Shannon defined the zero-error capacity of a discrete memoryless channel. He realized that the problem of its determination is immensely difficult and a simple formula for this capacity might not exist. Nevertheless, through the fortunate notion of perfect graphs of Claude Berge inspired by the concept of Shannon a new and beautiful chapter in graph theory was born. More generally, Shannon’s notion leads to a theory about the asymptotic behaviour of basic invariants in product structures. We explore the resulting merger of combinatorics and information theory.