Note on the number of balanced independent sets in the Hamming cube

2021/03/20 by Jinyoung Park, Park, Jinyoung · 1 citation
Mathematics · #Limits and Structures in Graph Theory #Analytic Number Theory Research #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.48550/arxiv.2103.11198

Abstract

Let Q_d be the d-dimensional Hamming cube and N=|V(Q_d)|=2^d. An independent set I in Q_d is called balanced if I contains the same number of even and odd vertices. We show that the logarithm of the number of balanced independent sets in Q_d is (1-Θ(1/√ d))N/2. The key ingredient of the proof is an improved version of "Sapozhenko's graph container lemma."

Cited by

• Asymptotic enumeration via graph containers and entropy

Related

• The number of maximal independent sets in the Hamming cube
• An isoperimetric inequality for the Hamming cube and some consequences
• Counting independent sets in triangle-free graphs
• Independent sets in the discrete hypercube
• Number of Independent Sets in Regular and Irregular Graphs: A 31 Year Journey