What is the Cheeger constant of a cubical subset of the cubic lattice?

Question

The Cheeger constant of a finite graph measures the "bottleneckedness" of the graph, and is defined as:

$$h(G) := \min\Bigg\lbrace\frac{|\partial A|}{|A|} \Bigg| A\subset V, 0<|A|\leq \frac{|V|}{2} \Bigg\rbrace$$

Here $V$ is the vertex set of $G$ and $\partial A$ denotes the collection of all edges going from a vertex in $A$ to a vertex in $V\setminus A$. The idea is that $h(G)$ is small if there is a bottleneck somewhere in $G$.

Now let $G$ have vertices $\lbrace 1,2,\ldots,n\rbrace^3\subset\mathbb{Z}^3$, and with an edge between two vertices if the distance between them is 1. Suppose that $n$ is even. Then it seems intuitively obvious that the minimum should be achieved with an "orthogonal half", that is $A= \lbrace 1,2,\ldots,n/2\rbrace\times\lbrace 1,2,\ldots,n\rbrace\times\lbrace 1,2,\ldots,n\rbrace$, and so $h(G)$ would be $n^2/(n^3/2) = 2/n$. Is this in fact the minimum, and how could one prove such a thing?

Answer 1

The result (for 3 dimensions and I think easily generalises to any dimension) follows from Theorem 3 of the Bollobás and Leader paper. The theorem (in 3 dimensions) states that for any subset $A$ of the vertices $V$ of a cubical grid of side length $N$ with $|A|\leq\frac{N^3}{2}$ that $$|\partial A| \geq \min_{r=1,2,3}\left\lbrace|A|^{1-1/r}rN^{(3/r)-1}\right\rbrace$$ So: $$\min_{r=1,2,3}\left\lbrace\left(\frac{N^3}{|A|}\right)^{1/r}r\frac{1}{N}\right\rbrace \leq \frac{|\partial A|}{|A|}$$ Now $|A| \leq \frac{N^3}{2}$, so $2 \leq \frac{N^3}{|A|}$, so $\frac{r2^{1/r}}{N} \leq \left(\frac{N^3}{|A|}\right)^{1/r}r\frac{1}{N}$. We can check for $r=1,2,3$ that $2\leq r2^{1/r}$ so we get that $$ \frac{2}{N} \leq \left(\frac{N^3}{|A|}\right)^{1/r}r\frac{1}{N} $$ for each $r$, and therefore for the minimum, and so the ``orthogonal half'' subset of the cube, $(1,2,\ldots,N/2)\times (1,2,\ldots,N)\times (1,2,\ldots,N)$ which gives $\frac{|\partial A|}{|A|}=\frac{N^2}{N^3/2} = \frac{2}{N}$, is best possible.