论文标题
Cayley图的线性香农容量
Linear Shannon Capacity of Cayley Graphs
论文作者
论文摘要
图形的香农容量是零纠纷信息理论中的基本数量，该理论测量了图中独立集的生长速率。尽管经过了充分的研究，但这个数量仍在构成几个谜团。 Lovász著名地证明了Shannon的容量$ C_5 $（5-Cycle）最多是$ \ sqrt {5} $通过他的Theta功能。通过$ \ mathbb {f} _5 $映射$ x \ mapsto 2x $上的简单线性代码来实现此界限。这激发了图形线性能力的概念，这是将自己限制在线性代码上时可达到的最大速率。我们基于多项式方法给出了一个简单的证明，即$ C_5 $的线性香农容量为$ \ sqrt {5} $。我们的方法更普遍地适用于在有限字段$ \ mathbb {f} _q $上的加性图上的Cayley图，从而在线性香农容量上给出了上限。我们将此与LovászTheta函数进行比较，表明它们匹配自相互的Cayley图（例如$ c_5 $），并且在某些情况下，界限较小。对于某些图，我们还表现出线性和一般香农容量之间的二次差距。
The Shannon capacity of a graph is a fundamental quantity in zero-error information theory measuring the rate of growth of independent sets in graph powers. Despite being well-studied, this quantity continues to hold several mysteries. Lovász famously proved that the Shannon capacity of $C_5$ (the 5-cycle) is at most $\sqrt{5}$ via his theta function. This bound is achieved by a simple linear code over $\mathbb{F}_5$ mapping $x \mapsto 2x$. This motivates the notion of linear Shannon capacity of graphs, which is the largest rate achievable when restricting oneself to linear codes. We give a simple proof based on the polynomial method that the linear Shannon capacity of $C_5$ is $\sqrt{5}$. Our method applies more generally to Cayley graphs over the additive group of finite fields $\mathbb{F}_q$, giving an upper bound on the linear Shannon capacity. We compare this bound to the Lovász theta function, showing that they match for self-complementary Cayley graphs (such as $C_5$), and that the bound is smaller in some cases. We also exhibit a quadratic gap between linear and general Shannon capacity for some graphs.
