Strengthening the Gilbert-Varshamov bound (Q1973922)

It is well known to be an extremely difficult problem to improve the Varshamov-Gilbert bound asymptotically. This paper describes some ideas for strengthening the Gilbert-Varshamov bound for linear codes in the non-asymptotic case. The idea is to construct a certain graph constructed on vectors of low weight in the cosets of the code \(C\). The graph is defined as the following undirected graph: The vertex set \(V\) consists of all \(n\)-dimensional vectors with components from GF\((q)\) having Hamming weight at most \(\alpha\). Two vertices are joined by an edge if and only if their difference is a nonzero code word in the code \(C\). The number of edges in the graph turns out to be a function of the weight distribution of the code. Simple estimates of the number of connected components in the graph (in the case \(\alpha= d-2)\) lead to better lower bounds for the minimum distance of linear codes. The paper presents an interesting unifying approach to non-asymptotic improvements of the Varshamov-Gilbert bound. The paper also includes new proofs and improvements of previously known results in the literature.