2008/06/30 by Salim Y. El Rouayheb, C. N. Georghiades, Rouayheb, Salim Y. El +8 · 1 citation
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #FOS: Computer and information sciences #Information Theory (cs.IT) #Limits and Structures in Graph Theory #cs.IT #graph theory and CDMA systems #math.IT
paper · pdf · doi:10.48550/arxiv.0806.4979
arxiv created 2008/06/30 · openalex publication_date 2008/06/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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ő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.