Independent sets of a given size and structure in the hypercube

Matthew Jenssen, Will Perkins, Aditya Potukuchi

Research output: Working paper/PreprintPreprint

110 Downloads (Pure)

Abstract

We determine the asymptotics of the number of independent sets of size ⌊β2 d−1 ⌋ in the discrete hypercube Qd = {0, 1} d for any fixed β ∈ [0, 1] as d → ∞, extending a result of Galvin for β ∈ [1−1/ √ 2, 1]. Moreover, we prove a multivariate local central limit theorem for structural features of independent sets in Qd drawn according to the hard core model at any fixed fugacity λ > 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.
Original languageEnglish
Publication statusPublished - 17 Jun 2021

Keywords

  • math.CO

Fingerprint

Dive into the research topics of 'Independent sets of a given size and structure in the hypercube'. Together they form a unique fingerprint.

Cite this