Vertex-isoperimetric inequality in a grid

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.