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!
 A: 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. $$
A: 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$.
A: 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.
