Abstract:
In this talk we shall discuss two problems concerning the number of independent sets in regular graphs.
The results of Kahn and Zhao show that among all d-regular graphs on n vertices, the graph consisting of disjoint copies of complete bipartite graphs maximizes the number of independent sets. In the first part we discuss a spectral stability phenomenon for this result. Further, we are interested in counting “biased” independent sets in regular bipartite graphs, i.e. independent sets which are essentially contained in one of the partition classes. This problem is related to the hard-core model and the Glauber dynamics from statistical physics.
Joint work with Prasad Tetali.