Volume 4, Issue 1
Improving the Gilbert-Varshamov Bound by Graph Spectral Method

Zicheng Ye, Huazi Zhang, Rong Li, Jun Wang, Guiying Yan & Zhiming Ma

CSIAM Trans. Appl. Math., 4 (2023), pp. 1-12.

Published online: 2023-01

Export citation
  • Abstract

We improve Gilbert-Varshamov bound by graph spectral method. Gilbert graph $G_{q,n,d}$ is a graph with all vectors in $\mathbb{F}^n_q$ 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 $G_{q,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.

  • Keywords

Gilbert–Varshamov bound, independence number, graph spectral method, Cayley graph, linear codes.

  • AMS Subject Headings

05C50, 05C69, 68P30

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{CSIAM-AM-4-1, author = {Ye , ZichengZhang , HuaziLi , RongWang , JunYan , Guiying and Ma , Zhiming}, title = {Improving the Gilbert-Varshamov Bound by Graph Spectral Method}, journal = {CSIAM Transactions on Applied Mathematics}, year = {2023}, volume = {4}, number = {1}, pages = {1--12}, abstract = {

We improve Gilbert-Varshamov bound by graph spectral method. Gilbert graph $G_{q,n,d}$ is a graph with all vectors in $\mathbb{F}^n_q$ 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 $G_{q,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.

}, issn = {2708-0579}, doi = {https://doi.org/ 10.4208/csiam-am.SO-2021-0024}, url = {http://global-sci.org/intro/article_detail/csiam-am/21333.html} }
TY - JOUR T1 - Improving the Gilbert-Varshamov Bound by Graph Spectral Method AU - Ye , Zicheng AU - Zhang , Huazi AU - Li , Rong AU - Wang , Jun AU - Yan , Guiying AU - Ma , Zhiming JO - CSIAM Transactions on Applied Mathematics VL - 1 SP - 1 EP - 12 PY - 2023 DA - 2023/01 SN - 4 DO - http://doi.org/ 10.4208/csiam-am.SO-2021-0024 UR - https://global-sci.org/intro/article_detail/csiam-am/21333.html KW - Gilbert–Varshamov bound, independence number, graph spectral method, Cayley graph, linear codes. AB -

We improve Gilbert-Varshamov bound by graph spectral method. Gilbert graph $G_{q,n,d}$ is a graph with all vectors in $\mathbb{F}^n_q$ 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 $G_{q,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.

Zicheng Ye, Huazi Zhang, Rong Li, Jun Wang, Guiying Yan & Zhiming Ma. (2023). Improving the Gilbert-Varshamov Bound by Graph Spectral Method. CSIAM Transactions on Applied Mathematics. 4 (1). 1-12. doi: 10.4208/csiam-am.SO-2021-0024
Copy to clipboard
The citation has been copied to your clipboard