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!



Perimeter/Neighborhood of a graph on grid
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. $$


