Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 109 / 3 / Solution

Give $[k{]}^n$ its grid graph structure, with two points adjacent when they differ by one in one coordinate. The vertex-isoperimetric inequality in a grid states that among subsets of a given size, an initial segment of the simplicial order on a grid minimizes the external vertex boundary. The simplicial order first compares the coordinate sum and breaks ties by reverse lexicographic order.

To prove it, compress each coordinate fiber to an initial interval. Comparing the two endpoints of every fiber shows that a coordinate compression does not increase the external boundary. Repeating all coordinate compressions makes the family a down-set. Within each constant-sum layer, reverse-lexicographic compression again preserves size and cannot enlarge the boundary in either neighbouring layer. Induction on the dimension and on the layers then makes every section an initial segment compatible with the preceding section. The resulting family is exactly an initial simplicial segment, proving its extremality.