An Isoperimetric Inequality for Hamming Balls and Local Expansion in Hypercubes

  • Zilin Jiang
  • Amir Yehudayoff

Abstract

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.

Published
2022-01-28
Article Number
P1.15