Geodesic
Note on the number of balanced independent sets in the Hamming cube
Jinyoung Park1
1Rutgers University
The electronic journal of combinatorics, Tome 29 (2022) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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-\Theta(1/\sqrt d))N/2.\] The key ingredient of the proof is an improved version of "Sapozhenko's graph container lemma".
DOI : 10.37236/10471
Classification : 05C69
Mots-clés : Sapozhenko's graph container lemma, \(d\)-dimensional Hamming cube

Jinyoung Park  1

1 Rutgers University 
@article{10_37236_10471,
     author = {Jinyoung Park},
     title = {Note on the number of balanced independent sets in the {Hamming} cube},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {2},
     doi = {10.37236/10471},
     zbl = {1491.05145},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10471/}
}
TY  - JOUR
AU  - Jinyoung Park
TI  - Note on the number of balanced independent sets in the Hamming cube
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10471/
DO  - 10.37236/10471
ID  - 10_37236_10471
ER  - 
%0 Journal Article
%A Jinyoung Park
%T Note on the number of balanced independent sets in the Hamming cube
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/10471/
%R 10.37236/10471
%F 10_37236_10471
Jinyoung Park. Note on the number of balanced independent sets in the Hamming cube. The electronic journal of combinatorics, Tome 29 (2022) no. 2. doi: 10.37236/10471

Cité par Sources :