Tata Institute of Fundamental Research
Graphs, Communication and Capacity
Student Seminar
Speaker:
Kishor Barman
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Date:
Wednesday, 19 Aug 2009 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.)
| Speaker: | Kishor Barman School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road |
| Date: | Wednesday, 19 Aug 2009 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.)
(Note: Capacity is still unknown for all odd cycles of length more than 5. Check this out.)