论文标题
具有渐近单位速率的coset图上的存储代码
Storage codes on coset graphs with asymptotically unit rate
论文作者
论文摘要
图$ g $上的存储代码是对顶点的符号分配的一组，因此每个顶点都可以通过查看其邻居来恢复其值。我们考虑在构造的无三角形图上构建大型存储代码的问题，该图形构造为二进制线性代码的coset图。以前证明，coset图上有无限的二进制存储代码家族，速率趋于3/4。在这里，我们表明，此类图上的代码可以渐近地达到速率1。同等地，可以将此问题称为图表上HAT猜测游戏的一种版本（例如P.J. Cameron E.A.在这种语言中，我们构建了无三角形的图形，随着顶点趋于无限的数量，玩家接近一个的概率。此外，找到接近零的速率的线性索引代码也是一个等效的问题。 A. Golovnev和I. Haviv（第36个计算复杂性conf。，2021年）在不含三角形的速率图上的另一个存储代码系列构建，依靠不同的图表。
A storage code on a graph $G$ is a set of assignments of symbols to the vertices such that every vertex can recover its value by looking at its neighbors. We consider the question of constructing large-size storage codes on triangle-free graphs constructed as coset graphs of binary linear codes. Previously it was shown that there are infinite families of binary storage codes on coset graphs with rate converging to 3/4. Here we show that codes on such graphs can attain rate asymptotically approaching 1. Equivalently, this question can be phrased as a version of hat-guessing games on graphs (e.g., P.J. Cameron e.a., \emph{Electronic J. Comb.} 2016). In this language, we construct triangle-free graphs with success probability of the players approaching one as the number of vertices tends to infinity. Furthermore, finding linear index codes of rate approaching zero is also an equivalent problem. Another family of storage codes on triangle-free graphs of rate approaching 1 was constructed earlier by A. Golovnev and I. Haviv (36th Computational Complexity Conf., 2021) relying on a different family of graphs.
