The BCH Family of Storage Codes on Triangle-Free Graphs and Its Relation to R(3, t)

Consider a simple, connected graph Γ with n vertices. Let C be a code of length n with its coordinates corresponding to the vertices of Γ. We define C as a storage code on Γ if, for any codeword c ∈ C , the information at each coordinate of c can be recovered by accessing its neighboring coordinates. The main problem here is to construct high-rate storage codes on triangle-free graphs. In this paper, we employ the polynomial method to address a question proposed by Barg and Zémor in 2022, demonstrating that the BCH family of storage codes on triangle-free Cayley graphs achieves a unit rate. Furthermore, we generalize the construction of the BCH family and obtain more storage codes of unit rate on triangle-free graphs. We also compare the BCH family with the other known constructions by examining the rate of convergence of 1/(1- R ( Cn )) with respect to the length n , where R ( Cn ) is the rate of code Cn . At last, we reveal a connection between the storage codes on triangle-free graphs and the Ramsey number R (3, t ), which leads to an upper bound for the rate of convergence of 1/(1 - R ( Cn )).