Independent sets of a given size and structure in the hypercube


Abstract in English

We determine the asymptotics of the number of independent sets of size $lfloor beta 2^{d-1} rfloor$ in the discrete hypercube $Q_d = {0,1}^d$ for any fixed $beta in [0,1]$ as $d to infty$, extending a result of Galvin for $beta in [1-1/sqrt{2},1]$. Moreover, we prove a multivariate local central limit theorem for structural features of independent sets in $Q_d$ drawn according to the hard core model at any fixed fugacity $lambda>0$. In proving these results we develop several general tools for performing combinatorial enumeration using polymer models and the cluster expansion from statistical physics along with local central limit theorems.

Download