5
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I looked at the paper, but I could not figure from it how to deal with the discrete case. Would it be correct to say that in the discrete case, if q is very large, then sets of this form are close to be optimal? $\endgroup$ – Or Meir May 6 '15 at 17:43
  • $\begingroup$ Also, for my application I don't need to know the exact form of the optimal sets - I just need a lower bound on the size of the neighborhood. Can I derive any such lower bound from the paper? $\endgroup$ – Or Meir May 6 '15 at 17:45
  • $\begingroup$ The continous problem certainly provides a lower bound on the size of the neighbourhood in the discrete case. Whether that gives you useful quantitative information depends on what you can say quantitatively about the continuous problem. This appears to be discussed towards the end of Section 2, but no firm conclusion is reached. $\endgroup$ – Ben Barber May 7 '15 at 10:26
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks, but I am more interested in the graph I described. By the way, I took my definition of the Hamming graph from Wikipedia. $\endgroup$ – Or Meir May 3 '15 at 19:19
  • $\begingroup$ Still, check Bezrukov's survey. He addresses lots of variations. For $d=3$ there is no difference, BTW. $\endgroup$ – Seva May 3 '15 at 20:16
  • 3
    $\begingroup$ As far as I'm aware, the definition of Hamming graph used by the OP, where vertices are adjacent if their Hamming distance is 1, is the standard definition used throughout graph theory, algebraic graph theory, coding theory, association schemes and so on. $\endgroup$ – Gordon Royle May 4 '15 at 11:26
  • $\begingroup$ @Gordon Royle: seems you are right about the terminology. The graph in my answer is rather called the lattice graph, or the grid graph. $\endgroup$ – Seva May 4 '15 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.