School of Technology and Computer Science

Kahn's Theorem, Bregman's Theorem and Information Theory

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)
Category:
Student Seminar
  event.ics     Print
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.