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?

`$c > 0$`

? $\endgroup$ – Mark Meckes Jul 21 '10 at 15:351more comment