Return to Question

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

Harper's theorem pins down the vertex expansion of the boolean Hamming cube $\left\{0,1\right\}^n$: it says that the optimal of the Hamming cube (i.e., the sets $S$ that minimize the ratio $\frac{|N(S)|}{|S|}$) are exactly the Hamming balls. Using this theorem, it is fairly easy to lower bound $|N(S)|$ in terms of $|S|$ in the Hamming cube using Hoeffding's inequality.

Now, suppose we wish to study the vertex expansion of 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. There is another paper by Harper that characterizes the optimal sets $S$ of this graph. This characterization, however, is more complicated. My questions are:

1. In principle, it is possible to lower bound $|N(S)|$ in terms of $|S|$ in the Hamming graph using the latter result of Harper. Nevertheless, here the calculation is more difficult compared to the case of the Hamming cube. Is there any published source that did this calculation explicitly?
2. The latter paper of Harper omits many details that may be obvious to experts, but might not be so clear to general audience (e.g., myself). Is there a presentation of the proof that is targeted to non-experts, and in particular, includes all the details?

Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$ (i.e., the set of vertices that have neighbors in $S$). The vertex expansion of $G$ is $$ \min_{S\subseteq V, |S|\le |V|/2} \left\{ \frac{|N(S)|}{|S|} \right\}.$$

Harper's theorem pins down the vertex expansion of the boolean Hamming cube $\left\{0,1\right\}^n$: it says that the optimal of the Hamming cube (i.e., the sets $S$ that minimize the ratio $\frac{|N(S)|}{|S|}$) are exactly the Hamming balls. Using this theorem, it is fairly easy to lower bound $|N(S)|$ in terms of $|S|$ in the Hamming cube using Hoeffding's inequality.

Now, suppose we wish to study the vertex expansion of 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. There is another paper by Harper that characterizes the optimal sets $S$ of this graph. This characterization, however, is more complicated. My questions are:

1. In principle, it is possible to lower bound $|N(S)|$ in terms of $|S|$ in the Hamming graph using the latter result of Harper. Nevertheless, here the calculation is more difficult compared to the case of the Hamming cube. Is there any published source that did this calculation explicitly?
2. The latter paper of Harper omits many details that may be obvious to experts, but might not be so clear to general audience (e.g., myself). Is there a presentation of the proof that is targeted to non-experts, and in particular, includes all the details?

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

Harper's theorem pins down the vertex expansion of the boolean Hamming cube $\left\{0,1\right\}^n$: it says that the optimal of the Hamming cube (i.e., the sets $S$ that minimize the ratio $\frac{|N(S)|}{|S|}$) are exactly the Hamming balls. Using this theorem, it is fairly easy to lower bound $|N(S)|$ in terms of $|S|$ in the Hamming cube using Hoeffding's inequality.

Now, suppose we wish to study the vertex expansion of 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. There is another paper by Harper that characterizes the optimal sets $S$ of this graph. This characterization, however, is more complicated. My questions are:

1. In principle, it is possible to lower bound $|N(S)|$ in terms of $|S|$ in the Hamming graph using the latter result of Harper. Nevertheless, here the calculation is more difficult compared to the case of the Hamming cube. Is there any published source that did this calculation explicitly?
2. The latter paper of Harper omits many details that may be obvious to experts, but might not be so clear to general audience (e.g., myself). Is there a presentation of the proof that is targeted to non-experts, and in particular, includes all the details?

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

Harper's theorem pins down the vertex expansion of the boolean Hamming cube $\left\{0,1\right\}^n$: it says that the optimal of the Hamming cube (i.e., the sets $S$ that minimize the ratio $\frac{|N(S)|}{|S|}$) are exactly the Hamming balls. Using this theorem, it is fairly easy to lower bound $|N(S)|$ in terms of $|S|$ in the Hamming cube using Hoeffding's inequality.

Now, suppose we wish to study the vertex expansion of 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. There is another paper by Harper that characterizes the optimal sets $S$ of this graph. This characterization, however, is more complicated. My questions are:

1. In principle, it is possible to lower bound $|N(S)|$ in terms of $|S|$ in the Hamming graph using the latter result of Harper. Nevertheless, here the calculation is more difficult compared to the case of the Hamming cube. Is there any published source that did this calculation explicitly?
2. The latter paper of Harper omits many details that may be obvious to experts, but might not be so clear to general audience (e.g., myself). Is there a presentation of the proof that is targeted to non-experts, and in particular, includes all the details?

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

Harper's theorem pins down the vertex expansion of the boolean Hamming cube $\left\{0,1\right\}^n$: it says that the optimal of the Hamming cube (i.e., the sets $S$ that minimize the ratio $\frac{|N(S)|}{|S|}$) are exactly the Hamming balls. Using this theorem, it is fairly easy to lower bound $|N(S)|$ in terms of $|S|$ in the Hamming cube using Hoeffding's inequality.

Now, suppose we wish to study the vertex expansion of 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. There is another [paper by Harper] that characterizes the optimal sets $S$ of this graph. This characterization, however, is more complicated. My questions are:

1. In principle, it is possible to lower bound $|N(S)|$ in terms of $|S|$ in the Hamming graph using the latter result of Harper. Nevertheless, here the calculation is more difficult compared to the case of the Hamming cube. Is there any published source that did this calculation explicitly?
2. The latter paper of Harper omits many details that may be obvious to experts, but might not be so clear to general audience (e.g., myself). Is there a presentation of the proof that is targeted to non-experts, and in particular, includes all the details?

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

Harper's theorem pins down the vertex expansion of the boolean Hamming cube $\left\{0,1\right\}^n$: it says that the optimal of the Hamming cube (i.e., the sets $S$ that minimize the ratio $\frac{|N(S)|}{|S|}$) are exactly the Hamming balls. Using this theorem, it is fairly easy to lower bound $|N(S)|$ in terms of $|S|$ in the Hamming cube using Hoeffding's inequality.

Now, suppose we wish to study the vertex expansion of 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. There is another paper by Harper that characterizes the optimal sets $S$ of this graph. This characterization, however, is more complicated. My questions are:

1. In principle, it is possible to lower bound $|N(S)|$ in terms of $|S|$ in the Hamming graph using the latter result of Harper. Nevertheless, here the calculation is more difficult compared to the case of the Hamming cube. Is there any published source that did this calculation explicitly?
2. The latter paper of Harper omits many details that may be obvious to experts, but might not be so clear to general audience (e.g., myself). Is there a presentation of the proof that is targeted to non-experts, and in particular, includes all the details?