Bounds On Codes Based On Graph Theory
Rouayheb Salim Y. El, Georghiades C. N., Soljanin E., Sprintson A.. Arxiv 2008
Let \(A_q(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 \(A_q(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