On Shannon's Zero Error Capacity of a Graph

by Gowtham Raghunath Kurri (School of Technology and Computer Science, TIFR)

Friday 1 Sept 2017, 17:15 → 18:15 Asia/Kolkata

A-201 (STCS Seminar Room)

Suppose we want to transmit messages across a noisy channel to a receiver. The maximum rate of transmission such that the receiver may recover the original message without errors (i.e., zero error) is called zero error capacity of the channel. In this context, a channel can be represented by a graph and Shannon(1956) computed the capacity of all graphs with five or fewer vertices - with the single exception of C_5 (a cycle with 5 vertices). Later, Laszlo Lovasz (1979) solved this seemingly very difficult combinatorial problem by showing that capacity of C_5 is \sqrt(5) with an astonishingly simple argument. In this talk, we will first develop the required background and discuss his proof.