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 <br

Time: 

Thursday, 5 November 2009 (All day)

Venue: 

  • A-212 (STCS Seminar Room)

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.