The Shannon Capacity of Graphs

Tommy Reddad

Originally studied by Shannon, the zero-error capacity of a noisy channel was eventually explicitly translated into a graph-theoretic problem by Lovász, in his seminal work on the topic. We present Lovász's theory of orthonormal representations for bounding the Shannon capacity of a graph, including a detailed geometric determination of the capacity of the 5-cycle. We also present a survey of interesting results concerning the Shannon capacity, and describe many of its related tantalizing open problems.