Vertex expansion of the Hamming graph 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 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: 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!
 A: The "standard" generalization of the Hamming graph is slightly distinct from what you describe: namely, identifying the vertex set with $C_d^n$ (where $C_d$ is the cyclic group of order $d$), two vertices are adjacent whenever they agree in all, but one coordinate, and in the remaining coordinate they differ exactly by $1$. The resulting graph is then the Cayley graph induced on the group $C_d^n$ by its standard generating subset.
The isoperimetric problem for these graphs is well-studied. Harper's result actually resolves not only the case $d=2$, but also that of $d=4$: for, the graph on $C_4^n$ is isomorphic to the graph on $C_2^{2n}$. Lindsey ("Assignment of numbers to vertices", Amer. Math. Monthly 71 (1964), pp. 508–516) established the corresponding result for the groups $C_3^n$. It is known that for $d\ge 5$ the situation is considerably more complicated. 
A good starting point is a survey paper by Bezrukov ("Edge isoperimetric problems on graphs", Graph theory and combinatorial biology (Balatonlelle, 1996), 157–197.) You can also check this preprint of mine for some surprising connections and an essentially best possible uniform bound valid for all $d$.
A: There is such a generalisation, also due to Harper.  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.
