Seminars & Colloquia Calendar
The asymptotic spectrum of graphs: duality for Shannon capacity
Jeroen Zuiddan, IAS
Location: Hill 705
Date & time: Monday, 29 April 2019 at 2:00PM - 3:00PM
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”.