Almost isoperimetric subsets of the discrete cube

Abstract

We show that a set $A\subset \{0,1{\}}^n$ with edge-boundary of size at most $|A|({\log }_2(2^n/|A|)+\epsilon )$ can be made into a subcube by at most $(2\epsilon /{\log }_2(1/\epsilon ))|A|$ additions and deletions, provided $\epsilon$ is less than an absolute constant. We deduce that if $A\subset \{0,1{\}}^n$ has size $2^t$ for some $t\in \mathbb{N}$, and cannot be made into a subcube by fewer than $\delta |A|$ additions and deletions, then its edge-boundary has size at least $|A|{\log }_2(2^n/|A|)+|A|\delta {\log }_2(1/\delta )=2^t(n-t+\delta {\log }_2(1/\delta ))$, provided $\delta$ is less than an absolute constant. This is sharp whenever $\delta =1/2^j$ for some $j\in \{1,2,\dots ,t\}$.

Typos corrected in Conjectures 12 and 13

References in corpus (2)

• Shadows and intersections: stability and new proofs
• Threshold for monotone symmetric properties through a logarithmic Sobolev inequality