3 added 42 characters in body

OK, suppose that $n\ge 3$, let $A$ be a subset set of even vertices of cardinatily $2^n\mu\ge 2^{n-2}$ (so $\mu\ge \frac 14$) 14$), and let write$n\ge 3$. Let B:=A{\stackrel2+}E$; that is, $B$ be is the set of odd vertices with at least 2 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.

2 added 73 characters in body

OK, let $A$ be a subset of even vertices of cardinatily $2^n\mu\ge 2^{n-2}$ (so $\mu\ge \frac 14$) and let $n\ge 3$. Let $B$ be the set of odd vertices with at least 2 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=\mu-2\mu^2$ \|g\|_2^2=\mu-2\mu^2$and, thereby,$\|Tg\|^2\le \|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\ge |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. 1 OK, let$A$be a subset of even vertices of cardinatily$2^n\mu\ge 2^{n-2}$(so$\mu\ge \frac 14$) and let$n\ge 3$. Let$B$be the set of odd vertices with at least 2 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. Then$\|g\|^2=\mu-2\mu^2$and, thereby,$\|Tg\|^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\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.