Citation
Abstract
In 1956, Shannon defined the zero-error capacity of a discrete memoryless channel as the largest rate at which information can be transmitted over the channel with zero error probability. He exhibited one particularly interesting channel with five inputs and outputs whose Zero error capacity he could not compute. The problem of computing this capacity remained unsolved until very recently, when Lovasz computed it in an astonishing simple manner. We show that Lovasz’ ideas, combined with some of our own, lead to an extremely powerful and general technique, which we phrase in terms of graph theory, for studying combinatorial packing problems. In particular, Delsarte’s linear programming bound for cliques in association schemes appear as a special case of the Lovasz bound.
Details
- Volume
- 42-45
- Published
- June 15, 1978
- Pages
- 133–146
- File Size
- 1.2 MB