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

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.

This is true. A simplicial initial segment in $[k{]}^2$ having both it and its complement larger than $(k^2-k)/2$ has an external vertex boundary of at least $k$. By the vertex-isoperimetric inequality, the same is true for every such $A$. If $A$ and $B$ were disjoint with no edge between them, then $B$ would avoid both $A$ and its external boundary, soThe hypotheses make the first two terms greater than $k^2-k$, contradicting $|{\partial }_{v}A|\ge k$.

This is false. For a central integer $s$, letThey are disjoint and no edge joins them; the omitted central layer has only $(3/4+o(1))k^2$ points. By choosing the central $s$ symmetrically, both sides havefor large $k$.

This is false. For arbitrarily large multiples $k$ of nine, take the vertical stripIt has $4k^2/9$ vertices, but only the $k$ horizontal edges crossing from column $4k/9$ to the next column leave it. Since $k<4k/3$, the proposed lower bound fails for infinitely many admissible $k$.