You are here: Seminars > 2024 > March 27th

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

邓海华 Haihua Deng


Time: 16:00-17:00 (GMT+8), Wednesday March 27th, 2024
Location: Zoom

Abstract: Let \(\Gamma\) be a simple connected graph on \(n\) vertices and \(C\) a code of length \(n\) whose coordinates are indexed by the vertices of \(\Gamma\). We call \(C\) a storage code on \(\Gamma\) if, for any codeword \(c\in C\), one can recover the information at each coordinate of \(c\) by accessing its neighbors in \(\Gamma\). In 2022, A. Barg and G. Zémor 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(C_n))\). This is a joint work with Hexiang Huang, Guobiao Weng and Qing Xiang.

Host: 陈俊彦 Junyan Chen