Independent sets in random subgraphs of the hypercube

Gal Kronenberg (Oxford)

Wed Jun 15, 13:00-14:00 (3 weeks ago)

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.


Audience: researchers in the topic

Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.

Organizers: Jan Grebik, Oleg Pikhurko
Curator: Hong Liu*
*contact for this listing

Export talk to