Skip to main content

Bounds on Codes Based on Graph Theory

01 January 2007

New Image

Building on results from algebraic graph theory and the Erds- Ko-Rado like theorems in extremal combinatorics, we show how several known bounds on codes can be easily obtained in a single framework. For instance, both the Hamming and Singleton bounds can be derived as an application of a property relating the clique number and the independence number of vertex transitive graphs. Using the same techniques, we also derive some new bounds and present some additional applications.