Algebra & Combinatorics Seminar

Title: Counting Independent Sets in Graphs and Hypergraphs and Spectral Stability
Speaker: Prasad Tetali (Regents' Professor, Georgia Tech, Atlanta, USA; and Satish Dhawan Visiting Professor, IISc)
Date: 13 September 2019
Time: 3 pm
Venue: LH-1, Mathematics Department

In 2001, Jeff Kahn showed that a disjoint union of $n/(2d)$ copies of the complete bipartite graph $K_{d,d}$ maximizes the number of independent sets over all $d$-regular bipartite graphs on n vertices, using Shearer’s entropy inequality. In this lecture I will mention several extensions and generalizations of this extremal result (to graphs and hypergraphs) and will describe a stability result (in the spectral sense) to Kahn’s result.

The lecture is based on joint works with Emma Cohen, David Galvin, Will Perkins, Michail Sarantis and Hiep Han.


Contact: +91 (80) 2293 2711, +91 (80) 2293 2265 ;     E-mail: chair.math[at]iisc[dot]ac[dot]in
Last updated: 17 Sep 2019