Jeroen Zuiddan, Institute for Advanced Study

Abstract

We give a dual description of the Shannon capacity of graphs. The  Shannon capacity of a graph is the rate of growth of the independence number under taking the strong power, or in different language, it is the maximum rate at which information can be transmitted over a noisy communication channel. Our dual description gives Shannon capacity as a minimization over the "asymptotic spectrum of graphs", which as a consequence unifies previous results and naturally gives rise to new questions. Besides a gentle introduction to this topic we discuss the general idea of “asymptotic spectra”.