Let $S$ be subset of $\{0,1\}^n$ with cardinality $k$.

Denote by $\Gamma_r(S)$ the union of all Hamming balls with centers in $S$ and radius $r$.

Harpers's theorem states that $\Gamma_d(S)$ is minimal if $S$ is a Hamming ball (see also this question).

Denote this minimal number by $V(k, r)$. My question is about a robust version of this theorem. Assume that $\Gamma_r(S) \le \text{poly}(n) \cdot V(k, r)$.

Can we say that then 99% points of $S$ belongs to a union of $2^{o(n)}$ Hamming balls with radius $r_{\min} + o(n)$?

Here $r_{\min}$ is the smallest number such that the volume of Hamming ball with radius $r_{\min}$ is greater than $k$.

UPD: I have found two related papers: Vertex-isoperimetric stability in the hypercube and Stability for vertex isoperimetry in the cube

The authors there prove that if poly(n) = 1 + o(1) then almost all of $S$ belongs to a single Hamming ball.

UPD2: The question is also interesting if we assume that $r(n)=\Omega(n)$ and $p(n)=\text{const}$.

  • 1
    $\begingroup$ The last inequality in the post should be completely different, shouldn’t it? $\endgroup$ Apr 28 at 8:21
  • $\begingroup$ @IlyaBogdanov, yes, thank you. $\endgroup$ Apr 28 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.