Linear Shannon Capacity of Cayley Graphs
share
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 √(5) via his theta function. This bound is achieved by a simple linear code over 𝔽_5 mapping x ↦ 2x. Motivated by this, we introduce 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 √(5). Our method applies more generally to Cayley graphs over the additive group of finite fields 𝔽_q. We compare our bound to the Lovász theta function, showing that they match for self-complementary Cayley graphs (such as C_5), and that our bound is smaller in some cases. We also exhibit a quadratic gap between linear and general Shannon capacity for some graphs.
READ FULL TEXT