Geodesic
An isoperimetric inequality for Hamming balls and local expansion in hypercubes
Zilin Jiang1 ; Amir Yehudayoff2
1Massachusetts Institute of Technology
2Technion – Israel Institute of Technology
The electronic journal of combinatorics, Tome 29 (2022) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We prove a vertex isoperimetric inequality for the $n$-dimensional Hamming ball $\mathcal{B}_n(R)$ of radius $R$. The isoperimetric inequality is sharp up to a constant factor for sets that are comparable to $\mathcal{B}_n(R)$ in size. A key step in the proof is a local expansion phenomenon in hypercubes.
DOI : 10.37236/9860
Classification : 05D05, 05C35
Mots-clés : \(n\)-dimensional Hamming ball, local expansion

Zilin Jiang  1   ; Amir Yehudayoff  2

1 Massachusetts Institute of Technology
2 Technion – Israel Institute of Technology 
@article{10_37236_9860,
     author = {Zilin Jiang and Amir Yehudayoff},
     title = {An isoperimetric inequality for {Hamming} balls and local expansion in hypercubes},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {1},
     doi = {10.37236/9860},
     zbl = {1481.05152},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9860/}
}
TY  - JOUR
AU  - Zilin Jiang
AU  - Amir Yehudayoff
TI  - An isoperimetric inequality for Hamming balls and local expansion in hypercubes
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9860/
DO  - 10.37236/9860
ID  - 10_37236_9860
ER  - 
%0 Journal Article
%A Zilin Jiang
%A Amir Yehudayoff
%T An isoperimetric inequality for Hamming balls and local expansion in hypercubes
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9860/
%R 10.37236/9860
%F 10_37236_9860
Zilin Jiang; Amir Yehudayoff. An isoperimetric inequality for Hamming balls and local expansion in hypercubes. The electronic journal of combinatorics, Tome 29 (2022) no. 1. doi: 10.37236/9860

Cité par Sources :