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

For $\mathcal{A}$ in the $n$-dimensional Boolean hypercube, the edge-isoperimetric inequality in the discrete cube iswhere $e(\mathcal{A})$ is the number of edges spanned by $\mathcal{A}$. Since the cube is $n$-regular, the equivalent boundary form is

We prove the induced-edge form by induction on $n$. Split the cube according to its last coordinate, and let the two sections have sizes $a\ge b$. At most $b$ edges of $\mathcal{A}$ cross between the sections. The induction hypothesis givesPut $x=b/(a+b)\le 1/2$. The required comparison with $\frac{1}{2}(a+b){\log }_2(a+b)$ is equivalent towhere $H_2$ is the binary entropy function. This follows from concavity because the graph of $H_2$ lies above the chord joining $(0,0)$ to $(1/2,1)$. The induction is complete. Subcubes attain equality when $|\mathcal{A}|$ is a power of two.

Solved by gpt-5.6-sol high.

The statement is false. In the grid graph $[9{]}^2$, take the four-row stripIt has $36=6^2$ vertices, and only the nine edges between rows four and five lie in its edge boundary. The corner square $[6{]}^2$ has six boundary edges along each of its two exposed sides, for a total of twelve. Thus a set of size $t^2$ can have smaller edge boundary than $[t{]}^2$.

Solved by gpt-5.6-sol high.

Apply coordinate compression in a product of paths in both coordinates. Replacing every fiber by an initial interval preserves the number of edges inside that fiber; between two neighboring fibers, the compressed sets span the minimum of their sizes, at least their original intersection size. Repeating the operation therefore never decreases the number of edges spanned and eventually produces a down-set.

Write the nonzero row lengths of this down-set asThe horizontal edges number $t^2-q$, and the vertical edges numberConsequentlySince $t^2\le q{a}_1$, the arithmetic-geometric mean inequality gives $q+a_1\ge 2t$. Henceas required.

Solved by gpt-5.6-sol high.