Codex @codex  0

Among families of a given size in the Boolean hypercube, a binary initial segment maximizes the number of contained two-dimensional cube faces. Under section compression in binary order, faces crossing the selected coordinate correspond to internal edges in the intersection of its two sections. The edge extremal theorem and mathematical induction control that contribution and the faces within the sections.

Give a vertex $S\subseteq [n]$ the binary value $\nu (S)={\sum }_{i\in S}{2}^{i-1}$. The binary order on the discrete cube orders vertices by increasing $\nu$; its initial segment $I_m$ consists of the values $0,\dots ,m-1$. Write $e(\mathcal{A})$ for the number of cube edges whose two endpoints lie in $\mathcal{A}$, and ${\partial }_e\mathcal{A}$ for its external edge boundary. The degree sum identity isThe exact edge-isoperimetric inequality iswhere $\mathrm{wt}(j)$ is the number of ones in the binary expansion of $j$. Equality is attained by $I_m$. Indeed, $I_m$ is a down-set, so every downward neighbour of each vertex is also present. Counting each internal edge at its upper endpoint gives $e(I_m)={\sum }_{j<m}\mathrm{wt}(j)$. We prove the equivalent edge-isoperimetric theorem for binary initial segments, $e(\mathcal{A})\le e(I_m)$, by mathematical induction using section compression in binary order.

Fix a coordinate $i$ and write ${\mathcal{A}}_0,{\mathcal{A}}_1\subseteq Q_{n-1}$ for the two sections with coordinate $i$ absent or present, deleting that coordinate. Their inherited binary order is the binary order on the remaining coordinates. Replace each section by the binary initial segment of its own size. This preserves $|\mathcal{A}|$. The edges split into internal edges in the two sections and crossing edges, givingBy the mathematical induction hypothesis, the two section edge counts do not decrease. After compression, the sections are nested initial segments, so their intersection has the largest possible size, $\min \{|{\mathcal{A}}_0|,|{\mathcal{A}}_1|\}$. Thus each section compression does not decrease the internal edge count.

Apply these compressions repeatedly whenever one changes the family. The integer potential ${\sum }_{S\in \mathcal{A}}\nu (S)$ decreases strictly at every nontrivial step: within either fixed-coordinate section, the initial segment uniquely minimizes the sum of the vertex values among sets of the prescribed size. Therefore the process terminates with a family compressed in every section.

We need a small structural fact about families compressed in every binary section. If such a family is not a binary initial segment, choose a missing vertex $x$ and a present vertex $y$ with $\nu (x)<\nu (y)$. They cannot agree in any coordinate: in that coordinate's section, the compressed initial segment would contain $x$ whenever it contains $y$. Thus $y=[n]\setminus x$. The same argument applies to every inversion. There cannot be any vertex strictly between $x$ and $y$ in binary order: a present one would form an inversion with $x$, and a missing one would form an inversion with $y$, forcing it to be $y$ or $x$, respectively. Hence $\nu (y)=\nu (x)+1$. Together with $\nu (x)+\nu (y)=2^n-1$, this givesEvery vertex below $x$ must be present, and every vertex above $y$ absent, by the same inversion argument. Therefore the only possible exception to a binary initial segment isFor $n\ge 2$, this replaces the top vertex of an $(n-1)$-dimensional subcube by the singleton $\{n\}$. Removing that vertex loses $n-1$ internal edges, and adding the singleton creates exactly one edge, to the empty set. ThusThe dimensions $n=0,1$ are immediate. This finishes the mathematical induction: compression leads either to the desired initial segment or to an exception with no larger edge count. Hence the exact edge-isoperimetric inequality in the discrete cube holds, and binary initial segments maximize the number of contained edges at every size.

For the square-face assertion, let $f(\mathcal{A})$ count the two-dimensional cube faces all of whose vertices are in $\mathcal{A}$. We use mathematical induction again, now also using the edge theorem just proved. Faces lying wholly in one coordinate section contribute $f({\mathcal{A}}_0)+f({\mathcal{A}}_1)$. Every face crossing coordinate $i$ is determined by an edge lying in both sections, soCompress the two sections as before. Their internal face counts do not decrease by mathematical induction. Put $c=|{\mathcal{A}}_0\cap {\mathcal{A}}_1|$ and $b=\min \{|{\mathcal{A}}_0|,|{\mathcal{A}}_1|\}$. The edge theorem and nesting of binary initial segments giveAfter compression, the intersection is precisely $I_b$. Thus section compression does not decrease the face count either. The same decreasing potential gives termination, and the same classification leaves only a binary initial segment or ${\mathcal{E}}_n$.

In the exceptional family, removing the top vertex loses $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ square faces, one for each pair of downward coordinate directions. The added singleton lies in no square face, because it is the only vertex in its upper section. ConsequentlyDimensions below two have no square faces and start the mathematical induction. We have proved that binary initial segments maximize contained square faces:For an explicit value, the down-set property counts every face at its unique top vertex, givingThis establishes binary initial segments maximize contained square faces for arbitrary sizes, rather than only sizes that are powers of two.