I have a good motivation to ask the question below, but since the post is
already a little long, and the problem looks rather natural and appealing
(well, to me, at least), I'd rather go straight to the point.


Let $n\ge 3$ be an integer. If $E$ denotes the standard basis of the
vector space ${\mathbb F}\_2^n$, then for any subset $A\subset{\mathbb
F}\_2^n$ we have $|A+E|\ge|A|$. This trivial estimate is easy to improve
in various ways, but this is not my concern here. What I am interested in
instead is the sumset $A{\stackrel2+} E$ consisting of all those vectors
of ${\mathbb F}\_2^n$ with *at least two* representations as $a+e$,
where $a\in A$ and $e\in E$; that is, vectors at Hamming distance $1$
from at least two elements of $A$. How small can this sumset be?


It is not difficult to find a linear subspace $L<{\mathbb F}\_2^n$ of
co-dimension ${\rm codim}\,L=\lfloor\log\_2 n\rfloor+1$ such that every two
elements of $L$ are at least distance $3$ from each other. Clearly,
$L{\stackrel2+} E$ is empty, showing that if $|A|<2^n/n$, then, in general,
no lower bound for $|A{\stackrel2+} E|$ can be obtained. Let's assume,
however, that $A$ is large; what can be said in this case? A simple double
counting shows that
 $$ |A{\stackrel2+} E| > \Big( 1-\frac{2^n}{n|A|} \Big) |A|. $$
My question is: assuming that $A$ is large enough (say, $|A|=2^{n-1}$),
can this estimate be improved to $|A{\stackrel2+} E|\ge|A|$? Here is a
way to put it in a particularly simple, notation-free form:



> 
> Suppose that half of the vertices of the $n$-dimensional hypercube are
>  colored, say, red. Is it true that under any such coloring, at least half
>  of the vertices have two (or more) red neighbors?
> 
> 
> 


Notice that, if true, the estimate $|A{\stackrel2+}E|\ge|A|$ is best
possible: equality is attained, for instance, if $A$ is the set of all
vectors of the same parity (alternatively, all vectors with the first
coordinate equal to $0$, or all vectors with the sum of all coordinates, but
the first one, equal to $0$).


Another remark is that $|A{\stackrel2+} E|\ge|A|$ holds true if $A\subseteq{\mathbb F}\_2^n$ is an *affine subspace* with $|A|>2^n/n$.



The hypercube: $|A {\stackrel2+} E| \ge |A|$?
OK, suppose that $n\ge 3$, let $A$ be a set of *even* vertices of cardinatily $2^n\mu\ge 2^{n-2}$ (so $\mu\ge \frac 14$), and write $B:=A{\stackrel2+}E$; that is, $B$ is the set of odd vertices with at least two neighbors in $A$. Assume that $|B|=2^n\xi$. Our aim is to show that $\xi\ge\mu$. Let us consider the action of the averaging (over neighbors) operator $T$ in $L^2$ with respect to the Haar measure. 


Let $f$ be the characteristic function of $A$. Let $g$ be $f$ with the constant and the alternating components removed; thus, $g(z)=f(z)-2\mu$ if $z$ is even, and $g(z)=0$ if $z$ is odd. Then $\|g\|\_2^2=\mu-2\mu^2$ and, thereby, $\|Tg\|\_2^2\le (1-\frac 2n)^2(\mu-2\mu^2)$ because we removed the eigenspaces corresponding to the eigenvalues $\pm 1$ and every other eigenvalue is at most $1-\frac 2n$.


On the other hand, we know that $Tg\le \frac 1n-2\mu$ on the complement of $B$ in the set of odd vertices. To balance it to the average $0$, we should have $Tg$ at least $\frac{\frac 12-\xi}{\xi}(2\mu-\frac 1n)$ on $B$ on average and, since the quadratic average can be only larger, we get
$$
\|Tg\|\_2^2\ge \left[(\frac 12-\xi)+\xi\left(\frac{\frac 12-\xi}{\xi}\right)^2\right]
(2\mu-\frac 1n)^2=\frac 12\frac{\frac 12-\xi}{\xi}(2\mu-\frac 1n)^2
$$
Thus
$$
\frac 12(\frac 12-\xi)(2\mu-\frac 1n)^2\le \xi(1-\frac 2n)^2(\mu-2\mu^2)
$$
Now, $2\mu-\frac 1n=2\mu(1-\frac{2}{4\mu n})\ge 2\mu(1-\frac 2n)$ under our assumption $\mu\ge \frac 14$. So, we get
$$
\frac 12(\frac 12-\xi)4\mu^2 \le \xi(\mu-2\mu^2)
$$
or, equivalently,
$$
(1-2\xi)\mu\le (1-2\mu)\xi
$$
i.e.,
$$
\mu\le\xi.
$$


I hope I haven't made a stupid mistake anywhere though I do not really like this proof: it works for $\stackrel{2}+$, but not for $\stackrel{4}+$ and you are, probably, interested in $\stackrel{K}+$ for all fixed $K$ as $n\to\infty$. Anyway, it gives the desired cutoff at $1/2$ for fixed parity and, thereby, the cutoff at $\frac 34$ in general.


