Independent sets in the middle two layers of Boolean lattice

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

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume178
DOIs
StatePublished - Feb 2021

Keywords

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

ASJC Scopus subject areas

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

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

Cite this