Bounds On Codes Based On Graph Theory
Rouayheb Salim Y. El, Georghiades C. N., Soljanin E., Sprintson A.. Arxiv 2008
[Paper]
ARXIV
Graph
Let be the maximum order (maximum number of codewords) of a
-ary code of length and Hamming distance at least . And let
that of a binary code of constant weight . 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 and
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