Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello,

I have a $\sqrt{n}\times\sqrt{n}$ lattice graph $G=(V,E)$ i.e. vertices on said 2-dim integer lattice, and two vertices have an edge if their $L_1$ distance is one. Now I want to claim something like this: For any partition of $V$ into $V_1, V_2$ with $n/4\leq |V_1| \leq n/2$, there are at least $\sqrt{n}$ edges of type $v~w$ where $v\in V_1$ and $w\in V_2$. It seems quite easy, and I was wondering if there is a simple crisp known proof for it. It seems some geometry might help e.g. to claim that perimeter of subset $S$ of area $n/4$ is minimized when $S$ is just one rectangle etc. Any reference for extensions to higher dimension would be helpful too. Thank you!

share|improve this question

3 Answers 3

up vote 2 down vote accepted

If you are serious about this, search the web for the "edge-isoperimetric problem for the grid graph". If you just want a (relatively) short solution to your specific problem, consider the following.

Let $k:=\sqrt n$, and assume for simplicity that $k$ is an integer and $|V_1|=n/4=k^2/4$. Let $x_1,\ldots,x_k$ and $y_1,\ldots,y_k$ be the number of points from $V_1$ on the "horizontal" and "vertical" segments of your grid, respectively. Thus, $0\le x_i,y_j\le k$, and $$ x_1+\dotsb+x_k=y_1+\dotsb+y_k=k^2/4. \tag{1} $$ Write $X:=\max x_i,\ \xi:=\min x_i,\ Y:=\max y_i$, and $\eta:=\min y_i$. Also, denote by $a$ the number of those indices $i\in[1,k]$ with $0<x_i<k$, and, similarly, denote by $b$ the number of those $i\in[1,k]$ with $0<y_i<k$. Finally, let $\partial(V_1)$ be the set of all those edges joining a vertex from $V_1$ with a vertex from $V_2$. We want to show that $|\partial(V_1)|\ge k$.

For every $i\in[1,k]$ with $0<x_i<k$, the $i$th horizontal segment contributes at least one edge to $\partial(V_1)$; hence, the number of horizontal edges in $\partial(V_1)$ is at least $a$. Also, for each $i\in[1,k-1]$ the number of horizontal edges in $\partial(V_1)$ between the $i$th vertical segment and the $i+1$ vertical segment is at least $|y_{i+1}-y_i|$. Thus, the number of horizontal edges in $\partial(V_1)$ is at least $$ |y_2-y_1|+\dotsb+|y_k-y_{k-1}| \ge Y-\eta. $$ As a result, we have at least $$ \max \{ Y-\eta, a \} $$ horizontal edges in $\partial(V_1)$. Counting in the same way vertical edges, we get \begin{align*} |\partial(V_1)| &\ge \max \{ Y-\eta, a \} + \max \{ X-\xi, b \} \\ &\ge \frac12\,(X-\xi+a) + \frac12\,(Y-\eta+b). \end{align*}

We now show that $$ X-\xi+a\ge k. \tag{2} $$ Similarly, $Y-\eta+b\ge k$, and the two estimates readily yield the assertion.

We observe that (2) is immediate if $X=k$ and $\xi=0$, and also if $X<k$ and $\xi>0$ (when $a=k$). The two remaining cases can be dealt with as follows.

If $X<k$ and $\xi=0$, then $a$ is the number of those indices $i\in[1,k]$ with $x_i>0$. Therefore, in view of (1), we have $k^2/4\le aX$, whence $$ X-\xi+a = X+a \ge k, $$ as wanted.

Finally, if $X=k$ and $\xi>0$, then $a$ is the number of those $i\in[1,k]$ with $x_i<k$. Hence, (1) gives $$ k^2/4 \ge a\xi+(k-a)k = k^2 - a(k-\xi), $$ implying $a(k-\xi)>k^2/4$ and, as a result, $$ X-\xi+a = a+(k-\xi) > k. $$

share|improve this answer

The $n$-dimensional case is solved in Bollobás and Leader, Edge-isoperimetric inequalities in the grid, Combinatorica 11 (1991), no. 4, 299–314. In two dimensions the optimal sets are small squares, then "half-space" rectangles, then complements of small squares. The range you specify is exactly the range where rectangles are best, and your guess is correct: there are almost exactly $\sqrt n$ edges in the smallest edge boundary.

Ryan O'Donnell's suggestion to consider the vertex isoperimetry problem will give the answer up to a constant factor (because the degrees are bounded), but curiously the extremal sets are very different: always sets roughly of the form $x+y \leq r$.

share|improve this answer

For the similar question of minimizing vertex boundary in the grid graph, I believe the optimal solutions were given by Bollobas and Leader in "Compressions and Isoperimetric Inequalities" (J. Combinatorial Theory A 56, pp. 47-62, 1991). Since the graph is very close to being regular I think it shouldn't be too hard to pass between the vertex and edge boundary problems.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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