Improving the Gilbert-Varshamov Bound by Graph Spectral Method (Zhiming Ma, Guiying Yan)

　　This paper improves Gilbert-Varshamov bound by graph spectral method. Gilbert graph Gq,n,d is a graph with all vectors in Fnq as vertices where two vertices are adjacent if their Hamming distance is less than d. In this paper, we calculate the eigenvalues and eigenvectors of Gq,n,d using the properties of Cayley graph. The improved bound is associated with the minimum eigenvalue of the graph. Finally, we give an algorithm to calculate the bound and linear codes which satisfy the bound.

　　Publication: 

　　CSIAM Transaction on Applied Mathematics, Vol. 4, No. 1, pp. 1-12, 2023.

　　Authors:

　　Zicheng Ye

　　Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China.

　　University of Chinese Academy of Sciences, Beijing 100049, China.

　　Huazi Zhang

　　Hangzhou Research Center, Huawei Technologies Co., Ltd., Hangzhou 310052, Zhejiang Province, China.

　　Rong Li

　　Hangzhou Research Center, Huawei Technologies Co., Ltd., Hangzhou 310052, Zhejiang Province, China.

　　Jun Wang

　　Hangzhou Research Center, Huawei Technologies Co., Ltd., Hangzhou 310052, Zhejiang Province, China.

　　Guiying Yan

　　Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China.

　　University of Chinese Academy of Sciences, Beijing 100049, China.

　　Email: yangy@amss.ac.cn

　　Zhiming Ma

　　Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China.

　　University of Chinese Academy of Sciences, Beijing 100049, China.

　　Email: mazm@amt.ac.cn