Linear Shannon Capacity of Cayley Graphs

Authors Venkatesan Guruswami, Andrii Riazanov

Publication date 11 September 2020

Abstract: 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'asz famously proved that the Shannon capacity of

C_{5}

(the 5-cycle) is at most

s q r t 5

via his theta function. This bound is achieved by a simple linear code over

m a t h b b F_{5}

mapping

x m a p s t o 2 x

. 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

s q r t 5

. Our method applies more generally to Cayley graphs over the additive group of finite fields

m a t h b b F_{q}

, giving an upper bound on the linear Shannon capacity. We compare this bound to the Lov'asz 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.

This page was built for publication: Linear Shannon Capacity of Cayley Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6348933)