Grid graph

The grid graph $[k{]}^d$ has vertices in the Cartesian power $\{1,\dots ,k{\}}^d$ and joins two vertices when they differ by one in exactly one coordinate.

For the $n\times n$ grid graph, if $b$ is an integer, $b<n/2$, and $(b-1{)}^2<a\le b(b-1)$, the minimum edge boundary of an $a$-vertex set is $2b-1$. A corner $(b-1)\times (b-1)$ square with a nonempty partial adjacent column attains it. The lower bound counts occupied rows and columns; full rows or columns are treated separately because they contribute no boundary in their own direction.

Among vertex subsets of $[k{]}^d$ with a fixed cardinality, initial segments of the simplicial order on a grid minimize the external vertex boundary.

The simplicial order on $[k{]}^d$ orders points first by increasing coordinate sum and breaks ties by reverse lexicographic order.

Coordinate compression in direction $i$ replaces every $i$-section of a subset of $[k{]}^d$ by the initial segment of the simplicial order on a grid having the same size. Assuming the vertex-isoperimetric theorem one dimension lower, this operation preserves cardinality and does not increase the external vertex boundary.

Let $A_j\subseteq [k{]}^{d-1}$ be the section of $A\subseteq [k{]}^d$ with one coordinate fixed at $j$, and put $A_0=A_{k+1}=\varnothing$. The corresponding section of its closed graph neighbourhood isAfter coordinate compression, the three sets on the right are nested initial simplicial segments. Their union therefore has the largest of their three cardinalities, which is no larger than the original union.

If initial segments of the simplicial order minimize vertex boundary in $[k{]}^2$, then they do so in every $[k{]}^d$. Inductively compress all coordinate sections. The section formula for a grid neighbourhood shows that no compression enlarges the boundary. Among boundary-minimizing compressed sets choose one with minimum coordinate-sum weight. Any departure from an initial simplicial segment produces an inversion in a two-coordinate face; the two-dimensional theorem replaces that face by its initial segment without enlarging the boundary and strictly lowers the weight. Hence no inversion remains and the set is an initial simplicial segment.

The order $00,01,11,10$ is a Gray code through the four vertices of $Q_2$. Applying this identification independently in $n$ coordinate pairs makes $[4{]}^n=P_4^n$ a spanning subgraph of the hypercube graph $Q_{2n}$. Therefore every vertex boundary in $Q_{2n}$ contains the corresponding boundary in $[4{]}^n$.