Abstract

Let Γ be a simple connected graph on n vertices and C a code of length n whose coordinates are indexed by the vertices of Γ. We call C a \textit{storage code} on Γ if, for any codeword c∈C, one can recover the information at each coordinate of c by accessing its neighbors in Γ. In 2022, A. Barg and G. Z'emor asked whether the rates of storage codes on triangle-free graphs can be arbitrarily close to 1 and list some candidates. Among them, we will discuss the BCH family and show that it is of unit rate by using the polynomial method. Furthermore, we can generalize this construction and obtain more storage codes of unit rate on triangle-free graphs. At last, we will talk about 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)). This is a joint work with Hexiang Huang, Guobiao Weng and Qing Xiang.