# A robust version of Harper's theorem

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}$$.

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