Independent sets of a given size and structure in the hypercube
Matthew Jenssen, Will Perkins, Aditya Potukuchi
Abstract
Abstract 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.
Topics & Concepts
HypercubeMathematicsCentral limit theoremLimit (mathematics)CombinatoricsEnumerationLambdaCluster (spacecraft)Discrete mathematicsComputer sciencePhysicsStatisticsMathematical analysisProgramming languageOpticsMarkov Chains and Monte Carlo MethodsStochastic processes and statistical mechanicsTopological and Geometric Data Analysis