The number of maximal independent sets in the Hamming cube

2019/09/10 by Jeff Kahn, Jinyoung Park, Kahn, Jeff +1 · 1 citation
Mathematics · #05C69 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.1909.04283

openalex publication_date 2019/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let Q_n be the n-dimensional Hamming cube and N=2ⁿ. We prove that the number of maximal independent sets in Q_n is asymptotically 2n2^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 Q_n.

Cited by

• Asymptotic enumeration via graph containers and entropy

Related

• Note on the number of balanced independent sets in the Hamming cube
• Maximal independent sets in the middle two layers of the Boolean lattice
• An isoperimetric inequality for the Hamming cube and some consequences
• Independent sets in the discrete hypercube
• Counting maximal antichains and independent sets