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?

  • 1
    $\begingroup$ Does it work in $\mathbb Z^2 ?$ $\endgroup$ – Will Jagy Jul 21 '10 at 2:03
  • 2
    $\begingroup$ See math.ucsd.edu/~fan/research/revised.html $\endgroup$ – Will Jagy Jul 21 '10 at 5:11
  • $\begingroup$ Hi Henry. I don't have time to think about this at the moment, but I added a couple (nonobvious?) tags that may attract the attention of people who know the right kind of stuff. (Follow Will's link to see something of the connections.) $\endgroup$ – Mark Meckes Jul 21 '10 at 15:17
  • $\begingroup$ I will add quickly, though, that exact solutions of such isoperimetric problems are often very hard to come by, and it's often much easier to get an estimate of the order of $h(G)$. Would it be good enough for you just to know that $h(G) \ge c/n$ for some constant $c > 0$? $\endgroup$ – Mark Meckes Jul 21 '10 at 15:35
  • 1
    $\begingroup$ One reference that may be relevant is Bollobás and Leader's "Edge-isoperimetric inequalities in the grid". I haven't seen the full paper, but among the results claimed in the abstract is that the semi-cube has the smallest edge-boundary over all sets containing between 1/4 and 3/4 of the vertices. $\endgroup$ – Kevin P. Costello Jul 21 '10 at 17:12

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.

  • $\begingroup$ If I'm not mistaken, there's nothing that prevents you from accepting your own answer. $\endgroup$ – Mark Meckes Jul 23 '10 at 12:24
  • $\begingroup$ Looks like it! Thanks to Will Jagy for the reference that led me to the paper I needed. $\endgroup$ – Henry Segerman Jul 23 '10 at 12:31

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.