The Number of Maximal Independent Sets in the Hamming Cube

Jeff Kahn, Jinyoung Park

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

Let Qn be the n-dimensional Hamming cube and N = 2n. We prove that the number of maximal independent sets in Qn is asymptotically 2 n2 N/4, as was conjectured by Ilinca and the first author in connection with a question of Duffus, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof that it is also an upper bound draws on various tools, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in Qn.

Original languageEnglish (US)
Pages (from-to)853-880
Number of pages28
JournalCombinatorica
Volume42
Issue number6
DOIs
StatePublished - Dec 2022

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'The Number of Maximal Independent Sets in the Hamming Cube'. Together they form a unique fingerprint.

Cite this