Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$. The vertex expansion of $G$ is 
$$ \min\_{S\subseteq V, |S|\le |V|/2} \left\{ \frac{|N(S)|}{|S|} \right\}.$$


For the binary Hamming cube $\{0,1\}^n$, the vertex expansion is well understood: [Harper's theorem](http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_frankl_short-proof-for-isoperimetric.pdf) says that the set of size $s$ of minimal-size neighborhood is the ball of size $s$.


Let us now consider the general [Hamming graph](http://en.wikipedia.org/wiki/Hamming_graph): this is the graph whose vertices are the strings $\{0,\ldots,q-1\}^n$, and two strings are connected by an edge if and only if they differ on exactly one coordinate. My questions are:


* Is anything known about the vertex expansion of the general Hamming graph? In particular, is there an analogue of Harper's theorem for this graph?
* Harper's theorem actually says something stronger: Denote by $N\_d(S)$ the $d$-neighborhood of $S$, i.e., the set of vertices of distance at most $d$ from $S$. Then, the set $S$ of size $s$ minimizing $|N\_d(S)|$ is the ball of size $S$. Is there any lower bound about $|N\_d(S)|$ as a function of $|S|$ in the Hamming graph?


Thanks!



Vertex expansion of the Hamming graph
There is such a generalisation, [also due to Harper](http://www.sciencedirect.com/science/article/pii/S0166218X99000827). In the continuous limit the optimal sets all have the following form: choose some $0 \leq t \leq 1$ and mark the point $t$ on each of the coordinate axes. These $n$ points naturally define a division of the unit cube into $2^n$ sub-cuboids; consider a union of these cuboids corresponding to a ball about $0$ in the discrete cube $\mathcal Q\_n$. This doesn't say anything about which $t$ and which ball to pick.


The proof is an excellent illustration of an approach that can be taken when compressions aren't enough to do the job. We first show that optimal sets may be taken to be downsets, then pass to the continuous situation by dividing a unit cube into smaller cubes. We then distort this picture by sliding around the (originally equally spaced) ticks on the axes but keeping the same cuboids filled in as they are rescaled. Since the volume and boundary are both locally linear in everything in sight it's easy to understand what happens, and by sliding adjacent ticks in opposite directions until they collide with something it turns out that as long as there is more than one tick on some axis we can obtain a situation that is at least as good but has one fewer tick. This brings us to the situation where optimal sets correspond to down sets of $\mathcal Q\_n$, so an extra argument is then required to show that balls are best.


