Independent sets in the middle two layers of Boolean lattice

József Balogh, Ramon I. Garcia, Lina Li

Research output: Contribution to journalArticlepeer-review


For an odd integer n=2d−1, let B(n,d) be the subgraph of the hypercube Qn induced by the two largest layers. In this paper, we describe the typical structure of independent sets in B(n,d) and give precise asymptotics on the number of them. The proofs use Sapozhenko's graph container method and a recently developed method of Jenssen and Perkins, which combines Sapozhenko's graph container lemma with the cluster expansion for polymer models from statistical physics.

Original languageEnglish (US)
Article number105341
JournalJournal of Combinatorial Theory. Series A
StatePublished - Feb 2021


  • Boolean lattice
  • Cluster expansion
  • Graph container method
  • Independent set

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Independent sets in the middle two layers of Boolean lattice'. Together they form a unique fingerprint.

Cite this