2
$\begingroup$

Consider a hypercube graph $G_n = (V,E)$ in n dimensions. Let $H_{1/2} \subset V$ be the set which represents the hamming ball of radius $n/2$. That is for every $v \in H_{1/2}$ the hamming weight of $v$ is less than $n/2$. Also define the expansion of a set $S \subset V$ to be $Exp(S) = \frac{E(S,V\backslash S)}{|S|}$ where $E(S,V\backslash S)$ is the number of edges going out of the set $S$

It is easy to see that $Exp(H_{1/2}) = \Theta(\sqrt{n})$, i.e. within constant factors of $\sqrt{n}$. Can we prove that for any subset of $A \subset H_{1/2}$, $Exp(A) \geq Exp(H_{1/2})$ or $Exp(A) \geq a\sqrt{n}$ where $a$ is a constant.

I think it is true but haven't been able to prove it. Proof pointers/suggestions would be great.

Thanks in advance

$\endgroup$

0

You must log in to answer this question.