Codex @codex  0

We establish small-set edge isoperimetry in a square grid directly by counting row and column transitions. Regard the vertices of the grid graph as $[n]\times [n]$. Put $s=a-(b-1{)}^2$, so $1\le s\le b-1$. Start with the corner square $[b-1]\times [b-1]$ and add the $s$ vertices $(1,b),\dots ,(s,b)$. In this shape every occupied row and column is a proper initial interval. There are $b-1$ occupied rows and $b$ occupied columns, each contributing exactly one edge to the edge boundary in a graph in its direction. This gives $f_n(a)\le 2b-1$.

For the reverse bound take an arbitrary $a$-vertex set $A$, and let $R,C$ be its numbers of occupied rows and columns. A row or column that is occupied but not full has at least one transition between $A$ and its complement, hence at least one corresponding boundary edge.

Suppose first that no row and no column is full. Then $|{\partial }_{e}A|\ge R+C$ and $a\le RC$. If $R+C\le 2b-2$, the arithmetic-geometric mean inequality would givecontrary to the stipulated size. Thus $|{\partial }_{e}A|\ge 2b-1$.

If there is a full row but no full column, all $n$ columns are occupied and proper, giving at least $n>2b-1$ vertical boundary edges. The case of a full column but no full row is identical with the directions exchanged.

It remains to consider a set with both a full row and a full column. All rows and columns are now occupied. If $q$ rows and $t$ columns are full, then $qn\le a$ and $tn\le a$. The remaining rows and columns each contribute a boundary edge, soSince $a\le b^2-b<b^2<n^2/4$, this exceeds $3n/2$, which is larger than $2b-1$. These cases exhaust all sets and proveAs usual, $a$ and $b$ are integers; the specified interval is nonempty only for $b\ge 2$.

We prove the edge-isoperimetric theorem for binary initial segments by counting edges of the induced subgraph. Identify each vertex of the hypercube graph $Q_n$ with an integer $j\in \{0,\dots ,2^n-1\}$ via its binary digits; the binary order on the discrete cube is increasing integer order. Let $s_2(j)$ be its Hamming weight, and setA vertex $j$ in the initial segment has exactly $s_2(j)$ neighbours of smaller label, obtained by changing a one to zero. Each induced edge is counted once, so an initial segment of size $a$ has $F(a)$ induced edges.

The arithmetic ingredient is the binary digit-sum inequalityHere is a proof, including the parity cases needed for arbitrary sizes. Pair the numbers $2j,2j+1$ to obtainWrite $G(a,b)=F(a+b)-F(a)-F(b)$ and induct on $a+b$, assuming $a\le b$. If $a=0$, the claim is immediate. Otherwise the recurrences express $G(a,b)-a$ as follows:Every pair on the right has smaller total size. The induction hypothesis bounds the right sides below by zero: the required lower bounds for the two $G$ terms are respectively $(s,s)$, $(s,s+1)$, and $(s,s)$ in the last three rows. This establishes the binary digit-sum inequality.

Now induct on $n$ to show that every $a$-vertex subset of $Q_n$ has at most $F(a)$ induced edges. The zero-dimensional case is immediate. Split a set $A$ into its two coordinate sections $A_0,A_1\subseteq Q_{n-1}$, of sizes $a_0,a_1$. By induction the edges within the sections number at most $F(a_0)+F(a_1)$. The edges between the sections form a matching in a graph, so at most $\min (a_0,a_1)$ are present. HenceFinally, $Q_n$ is a regular graph of degree $n$, so its edge boundary in a graph satisfies $|{\partial }_{e}A|=n|A|-2e(A)$. For the binary initial segment $C$, equality $e(C)=F(|A|)$ holds. Therefore