Improving the Gilbert-Varshamov Bound by Graph Spectral Method (CSIAM Transactions on Applied Mathematics, 2023)
We improve Gilbert-Varshamov bound by graph spectral method. Gilbertgraph $G_{q,n,d}$ is a graph with all vectors in $\mathbb{F}^n_q$ as vertices where two vertices are adjacentif their Hamming distance is less than $d.$ In this paper, we calculate the eigenvaluesand eigenvectors of $G_{q,n,d}$ using the properties of Cayley graph. The improved boundis associated with the minimum eigenvalue of the graph. Finally we give an algorithmto calculate the bound and linear codes which satisfy the bound.
Keywords: Gilbert–Varshamov bound; independence number; graph spectral method; Cayley graph; linear codes.