10
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The last inequality in the post should be completely different, shouldn’t it? $\endgroup$
    – Ilya Bogdanov
    Commented Apr 28, 2021 at 8:21
  • $\begingroup$ @IlyaBogdanov, yes, thank you. $\endgroup$
    – Alexey Milovanov
    Commented Apr 28, 2021 at 12:06
  • $\begingroup$ can you clarify exactly what your equation $poly(n)=1+o(1)$ means? $\endgroup$
    – kodlu
    Commented Apr 29 at 14:00
  • 1
    $\begingroup$ @kodlu for example in arxiv.org/pdf/1807.09618 it means $1 + o(1) = 1 + \frac{c}{n}$, for $c < 10^{-9}$. $\endgroup$
    – Alexey Milovanov
    Commented Apr 29 at 14:11

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .