Tata Institute of Fundamental Research
Kahn's Theorem, Bregman's Theorem and Information Theory
Student Seminar
Speaker:
Kishor Baman
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Date:
Thursday, 5 Nov 2009 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
We'll discuss an information theoretic proof of the Kahn's theorem that upper bounds the number of independent sets of a regular bi-partite graph. If time permits, we'll also discuss an information theoretic proof of the Bregman's theorem (the proof is due to Jaikumar), which upper bounds the number of perfect matchings of a bi-partite graph.
| Speaker: | Kishor Baman School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road |
| Date: | Thursday, 5 Nov 2009 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
We'll discuss an information theoretic proof of the Kahn's theorem that upper bounds the number of independent sets of a regular bi-partite graph. If time permits, we'll also discuss an information theoretic proof of the Bregman's theorem (the proof is due to Jaikumar), which upper bounds the number of perfect matchings of a bi-partite graph.