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 homomorphisms in graphs and independent sets in linear hypergraphs) and, time permitting, 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.
Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.
The ACO Seminar (2019–2020)