Bounds On Codes Based On Graph Theory | Awesome Learning to Hash Add your paper to Learning2Hash

Bounds On Codes Based On Graph Theory

Rouayheb Salim Y. El, Georghiades C. N., Soljanin E., Sprintson A.. Arxiv 2008

[Paper]    
ARXIV Graph

Let Aq(n,d) be the maximum order (maximum number of codewords) of a q-ary code of length n and Hamming distance at least d. And let A(n,d,w) that of a binary code of constant weight w. Building on results from algebraic graph theory and Erd\H{o}s-ko-Rado like theorems in extremal combinatorics, we show how several known bounds on Aq(n,d) and A(n,d,w) can be easily obtained in a single framework. For instance, both the Hamming and Singleton bounds can 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.

Similar Work