2023/01/12 by Ghurumuruhan Ganesan, Ganesan, Ghurumuruhan
Biochemistry, Genetics and Molecular Biology · Computer Science · #Combinatorics (math.CO) #Cooperative Communication and Network Coding #DNA and Biological Computing #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2301.04808
openalex publication_date 2023/01/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study the redundancy of linear codes with graph constraints. First we consider linear parity check codes based on bipartite graphs with diversity and with generalized graph constraints. We describe sufficient conditions on the constraint probabilities and use the probabilistic method to obtain linear codes that achieve the Gilbert-Varshamov redundancy bound in addition to satisfying the constraints and the diversity index. In the second part we consider a generalization of graph capacity which we call as the fractional graph capacity and use the probabilistic method to determine bounds on the fractional capacity for arbitrary graphs. Specifically, we establish an upper bound in terms of the full graph capacity and a lower bound in terms of the average and maximum vertex degree of the graph.