# Perimeter/Neighborhood of a graph on grid

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!

-

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

-

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

-

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.

-