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

Jinyoung Park

paper

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

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/\sqrt d))N/2.\] The key ingredient of the proof is an improved version of "Sapozhenko's graph container lemma."

6 pages. Comments are welcome!