Independent sets in random subgraphs of the hypercube
Gal Kronenberg (Oxford)
Abstract: Independent sets in bipartite regular graphs have been studied extensively in combinatorics, probability, computer science and more. The problem of counting independent sets is particularly interesting in the $d$-dimensional hypercube $\{0,1\}^d$, motivated by the lattice gas hardcore model from statistical physics. Independent sets also turn out to be very interesting in the context of random graphs.
The number of independent sets in the hypercube $\{0,1\}^d$ was estimated precisely by Korshunov and Sapozhenko in the 1980s and recently refined by Jenssen and Perkins.
In this talk we will discuss new results on the number of independent sets in a random subgraph of the hypercube. The results extend to the hardcore model and rely on an analysis of the antiferromagnetic Ising model on the hypercube.
This talk is based on joint work with Yinon Spinka.
combinatorics
Audience: researchers in the topic
Series comments: This is the online combinatorics seminar at Warwick.
| Organizers: | Jan Grebik, Oleg Pikhurko |
| Curator: | Hong Liu* |
| *contact for this listing |