Graphs, Communication and Capacity

Kishor Barman School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road
Wednesday, 19 Aug 2009 (all day)
A-212 (STCS Seminar Room)
Suppose there is a graph G, whose vertices are letters in an alphabet A and in which adjacency means that the letters can be confused in a transmission. We would like to find the maximum number of messages which can be sent without any danger of confusion (zero error). To this end, we would define the notion of 'capacity' of a graph. This has a strong connection to the independent sets of certain graph powers. Although computing 'capacity' of a general graph is believed to be notoriously difficult, capacity of some special graphs are known. After introducing the problem, we would compute the capacity of the 5-cycle, as shown by Lovasz (The capacity of the 5-cycle was unknown until Lovasz found it in 1979, that is more than 20 year after Shannon had posed the problem).

(Note: Capacity is still unknown for all odd cycles of length more than 5. Check this out.)