Independent sets in the hypercube revisited
Matthew Jenssen, Will Perkins
Abstract
We revisit Sapozhenko's classic proof on the asymptotics of the number of independent sets in the discrete hypercube {0,1}d and Galvin's follow-up work on weighted independent sets. We combine Sapozhenko's graph container methods with the cluster expansion and abstract polymer models, two tools from statistical physics, to obtain considerably sharper asymptotics and detailed probabilistic information about the typical structure of (weighted) independent sets in the hypercube. These results refine those of Korshunov and Sapozhenko and Galvin, and answer several questions of Galvin.
Topics & Concepts
HypercubeMathematicsProbabilistic logicDiscrete mathematicsGraphCombinatoricsIndependent setCluster (spacecraft)Class (philosophy)Cluster expansionGraph theorySet (abstract data type)Computer scienceAxiomContainer (type theory)AlgorithmStatistical modelCluster analysisMarkov Chains and Monte Carlo MethodsStochastic processes and statistical mechanicsLimits and Structures in Graph Theory