[proofplan] We proceed by induction on $n$, using binary $i$-compressions that replace $i$-sections with initial segments of the binary order. The edge boundary decomposes into three terms: the edge boundaries of the two sections plus the symmetric difference (counting edges in the $i$-direction). We show binary compression does not increase any of the three terms: induction handles the first two, and the nesting of binary initial segments handles the third. The termination and classification of compressed sets mirrors the vertex isoperimetric argument, eliminating the unique anomalous compressed set by direct computation. [/proofplan] [step:Decompose $|\partial_e A|$ into contributions from the $i$-sections and the $i$-direction edges] Fix $1 \leq i \leq n$. Recall the $i$-sections: $A_-^{(i)} = \{x \in A : i \notin x\}$ and $A_+^{(i)} = \{x \setminus \{i\} : x \in A, i \in x\}$, both subsets of $\mathcal{P}(X \setminus \{i\}) \cong Q_{n-1}$. Every edge of $Q_n$ either stays within one layer (both endpoints agree on whether they contain $i$) or crosses between layers (the endpoints differ in exactly coordinate $i$). An edge $\{u, v\}$ within the $-$-layer crosses $\partial_e A$ iff exactly one of $u, v$ is in $A_-^{(i)}$, contributing $|\partial_e A_-^{(i)}|$ such edges. Similarly, edges within the $+$-layer contribute $|\partial_e A_+^{(i)}|$. An edge in the $i$-direction connects $x$ (with $i \notin x$) to $x \cup \{i\}$. This edge crosses $\partial_e A$ iff exactly one of $x$ and $x \cup \{i\}$ is in $A$, i.e., $x \in A_-^{(i)} \triangle A_+^{(i)}$. The number of such edges is $|A_-^{(i)} \triangle A_+^{(i)}|$. Therefore \begin{align*} |\partial_e A| = |\partial_e A_+^{(i)}| + |\partial_e A_-^{(i)}| + |A_+^{(i)} \triangle A_-^{(i)}|. \end{align*} [guided] Let us verify the three-term decomposition carefully. An edge $\{u, v\} \in E(Q_n)$ satisfies $|u \triangle v| = 1$, so $u$ and $v$ differ in exactly one coordinate. **Case 1: the differing coordinate is not $i$.** Then $u$ and $v$ agree on coordinate $i$. If $i \notin u$ and $i \notin v$, both lie in the $-$-layer, and $\{u, v\} \in \partial_e A$ iff exactly one of $u, v$ is in $A_-^{(i)}$. If $i \in u$ and $i \in v$, both lie in the $+$-layer, and $\{u, v\} \in \partial_e A$ iff exactly one of $u \setminus \{i\}, v \setminus \{i\}$ is in $A_+^{(i)}$, which counts as an edge in $\partial_e A_+^{(i)}$. **Case 2: the differing coordinate is $i$.** Then $\{u, v\} = \{x, x \cup \{i\}\}$ for some $x$ with $i \notin x$. The edge crosses $\partial_e A$ iff exactly one of $x, x \cup \{i\}$ is in $A$. Now $x \in A$ iff $x \in A_-^{(i)}$, and $x \cup \{i\} \in A$ iff $x \in A_+^{(i)}$. So the edge crosses $\partial_e A$ iff $x$ belongs to exactly one of $A_-^{(i)}$ and $A_+^{(i)}$, i.e., $x \in A_-^{(i)} \triangle A_+^{(i)}$. These three classes partition all edges of $\partial_e A$, giving the decomposition. [/guided] [/step] [step:Define binary $i$-compression and show it does not increase $|\partial_e A_\pm^{(i)}|$ by induction] The **binary $i$-compression** $D_i(A)$ replaces $A_+^{(i)}$ and $A_-^{(i)}$ with initial segments of the binary order on $\mathcal{P}(X \setminus \{i\})$ of the same respective sizes. Set $B = D_i(A)$. We proceed by induction on $n$. The base case $n = 1$ is immediate: $Q_1$ has two vertices $\varnothing$ and $\{1\}$ with one edge, and any set $A \subseteq Q_1$ satisfies $|\partial_e A| \in \{0, 1\}$. The initial segment of size $0$ is $\varnothing$ (with $|\partial_e| = 0$), of size $1$ is $\{\varnothing\}$ (with $|\partial_e| = 1$), and of size $2$ is $Q_1$ (with $|\partial_e| = 0$), all of which are optimal. For the inductive step, assume the theorem holds for $Q_{n-1}$: initial segments of the binary order on $Q_{n-1}$ minimise the edge boundary among all sets of the same size. Since $B_+^{(i)}$ and $B_-^{(i)}$ are binary initial segments in $Q_{n-1}$ of sizes $|A_+^{(i)}|$ and $|A_-^{(i)}|$ respectively, the inductive hypothesis gives \begin{align*} |\partial_e B_+^{(i)}| \leq |\partial_e A_+^{(i)}|, \qquad |\partial_e B_-^{(i)}| \leq |\partial_e A_-^{(i)}|. \end{align*} [/step] [step:Show that binary compression does not increase the symmetric difference term] It remains to show $|B_+^{(i)} \triangle B_-^{(i)}| \leq |A_+^{(i)} \triangle A_-^{(i)}|$. Since $B_+^{(i)}$ and $B_-^{(i)}$ are both initial segments of the binary order on $\mathcal{P}(X \setminus \{i\})$, and initial segments of the binary order are nested (a smaller initial segment is contained in a larger one), one of $B_+^{(i)}$ and $B_-^{(i)}$ is contained in the other. WLOG $|B_+^{(i)}| \leq |B_-^{(i)}|$, so $B_+^{(i)} \subseteq B_-^{(i)}$. Then \begin{align*} |B_+^{(i)} \triangle B_-^{(i)}| = |B_-^{(i)}| - |B_+^{(i)}| = |A_-^{(i)}| - |A_+^{(i)}|. \end{align*} For the original sections, $|A_+^{(i)} \triangle A_-^{(i)}| = |A_+^{(i)}| + |A_-^{(i)}| - 2|A_+^{(i)} \cap A_-^{(i)}|$. Since $|A_+^{(i)} \cap A_-^{(i)}| \leq \min\{|A_+^{(i)}|, |A_-^{(i)}|\} = |A_+^{(i)}|$ (assuming $|A_+^{(i)}| \leq |A_-^{(i)}|$), we get \begin{align*} |A_+^{(i)} \triangle A_-^{(i)}| \geq |A_-^{(i)}| + |A_+^{(i)}| - 2|A_+^{(i)}| = |A_-^{(i)}| - |A_+^{(i)}|. \end{align*} Therefore $|B_+^{(i)} \triangle B_-^{(i)}| = |A_-^{(i)}| - |A_+^{(i)}| \leq |A_+^{(i)} \triangle A_-^{(i)}|$. [guided] Why does the nesting of binary initial segments make the symmetric difference shrink? For arbitrary sets $S, T$ with $|S| = |T'|$ and $|T| = |S'|$ (same sizes as the originals), the symmetric difference $|S \triangle T|$ depends on the overlap $|S \cap T|$: \begin{align*} |S \triangle T| = |S| + |T| - 2|S \cap T|. \end{align*} When $S \subseteq T$ (which happens for binary initial segments with $|S| \leq |T|$), the overlap is maximal: $|S \cap T| = |S|$, giving $|S \triangle T| = |T| - |S|$. This is the minimum possible value of the symmetric difference among all pairs of sets with the given cardinalities. The original sections $A_+^{(i)}$ and $A_-^{(i)}$ may have smaller overlap (they are arbitrary sets), so their symmetric difference is at least as large: \begin{align*} |A_+^{(i)} \triangle A_-^{(i)}| = |A_+^{(i)}| + |A_-^{(i)}| - 2|A_+^{(i)} \cap A_-^{(i)}| \geq \big||A_+^{(i)}| - |A_-^{(i)}|\big| = |B_+^{(i)} \triangle B_-^{(i)}|. \end{align*} This is the crucial place where the nested structure of binary initial segments is used: it maximises the overlap and thereby minimises the symmetric difference. [/guided] [/step] [step:Combine the three bounds to show $|\partial_e D_i(A)| \leq |\partial_e A|$] Summing the three estimates: \begin{align*} |\partial_e B| &= |\partial_e B_+^{(i)}| + |\partial_e B_-^{(i)}| + |B_+^{(i)} \triangle B_-^{(i)}| \\ &\leq |\partial_e A_+^{(i)}| + |\partial_e A_-^{(i)}| + |A_+^{(i)} \triangle A_-^{(i)}| \\ &= |\partial_e A|. \end{align*} So the binary $i$-compression does not increase the edge boundary. [/step] [step:Iterate binary compressions to reach a fully compressed set] Define the binary weight \begin{align*} w_{\text{bin}}: \mathcal{P}(\mathcal{P}(X)) &\to \mathbb{Z}_{\geq 0} \\ A &\mapsto \sum_{x \in A} \varphi(x), \quad \text{where } \varphi(x) = \sum_{j \in x} 2^j. \end{align*} Each non-trivial application of a binary compression $D_i$ replaces sections with binary initial segments that are "lower" in the binary order, strictly decreasing $w_{\text{bin}}(A)$. Since $w_{\text{bin}}$ is a non-negative integer bounded by $|A| \cdot (2^{n+1} - 1)$, the process terminates after finitely many steps at a set $B$ that is $i$-compressed for every $1 \leq i \leq n$ (with respect to binary compressions). At each step $|\partial_e(\cdot)|$ does not increase, so $|\partial_e B| \leq |\partial_e A|$. [guided] The termination argument is the same as for simplicial compressions, but with the binary weight $w_{\text{bin}}$ replacing the cardinality-sum weight. Each binary initial segment of size $k$ in $\mathcal{P}(X \setminus \{i\})$ minimises $\sum \varphi(\cdot)$ among all $k$-element subfamilies (since it selects the $k$ elements with the smallest binary values). If a section is not already the binary initial segment of its size, replacing it strictly decreases the sum of binary values for that section. The total $w_{\text{bin}}(A)$ is the sum over all elements of their $\varphi$-values, so it decreases strictly whenever any $D_i$ makes a change. [/guided] [/step] [step:Classify fully compressed sets and eliminate the exception] By the same argument as in the vertex isoperimetric case (the [Classification of Compressed Non-Initial-Segments](/theorems/2600), adapted to the binary order), a fully binary-compressed set $B$ is either a binary initial segment or a unique anomalous set of size $2^{n-1}$. The anomalous set is \begin{align*} \tilde{B} = \big(\mathcal{P}(X \setminus \{n\}) \setminus \{\{1, 2, \ldots, n-1\}\}\big) \cup \{\{n\}\}, \end{align*} obtained from the binary initial segment of size $2^{n-1}$ (which is $\mathcal{P}(X \setminus \{n\}) = \mathcal{P}(\{1, \ldots, n-1\})$) by replacing $\{1, 2, \ldots, n-1\}$ (the last element in binary order within $\mathcal{P}(\{1, \ldots, n-1\})$) with $\{n\}$. The binary initial segment $C$ of size $2^{n-1}$ is $\mathcal{P}(\{1, \ldots, n-1\})$, a $(n-1)$-dimensional subcube. Its edge boundary consists of all edges from a vertex $x \subseteq \{1, \ldots, n-1\}$ to $x \cup \{n\}$. There are $2^{n-1}$ such edges (one per vertex of $C$), and no other edges cross the boundary since all edges within $\{1, \ldots, n-1\}$-coordinates stay inside $C$. So $|\partial_e C| = 2^{n-1}$. For the anomalous set $\tilde{B}$, we compute $|\partial_e \tilde{B}|$. The set $\tilde{B}$ differs from $C$ by removing $\{1, \ldots, n-1\}$ and adding $\{n\}$. The element $\{1, \ldots, n-1\}$ has $n-1$ edges within $C$ (to sets obtained by removing one element from $\{1, \ldots, n-1\}$, all of which are in $C$) and $1$ edge to $\{1, \ldots, n\}$ (outside $C$). Removing $\{1, \ldots, n-1\}$ from $C$ exposes $n-1$ new boundary edges (from the $n-1$ neighbours inside $C$ to the now-removed vertex) and eliminates the one edge from $\{1, \ldots, n-1\}$ to $\{1, \ldots, n\}$. But we must also account for the edges from $\{1, \ldots, n-1\}$ to $\{1, \ldots, n-1\} \setminus \{j\}$ for each $j$: these edges were internal to $C$ and now become boundary edges of $\tilde{B}$ (since $\{1, \ldots, n-1\}$ is removed). That gives $n - 1$ new boundary edges. Adding $\{n\}$: the element $\{n\}$ has $n$ edges in $Q_n$ -- one to $\varnothing$ (in $\tilde{B}$, since $\varnothing \in C$ and was not removed) and $n - 1$ edges to $\{j, n\}$ for $j = 1, \ldots, n-1$ (all outside $\tilde{B}$, since $\{j, n\} \notin C$ and $\{j, n\} \neq \{n\}$). Adding $\{n\}$ to $\tilde{B}$ removes the edge from $\varnothing$ to $\{n\}$ from the boundary (both are now in $\tilde{B}$) but adds $n - 1$ new boundary edges (from $\{n\}$ to $\{j,n\}$). Also, the edge from $\{n\}$ to $\varnothing$ was previously in $\partial_e C$; now both endpoints are in $\tilde{B}$, removing it. And the edge from $\{1,\ldots,n-1\}$ to $\{1,\ldots,n\}$ is removed (since $\{1,\ldots,n-1\} \notin \tilde{B}$, this edge is now from outside $\tilde{B}$ to outside $\tilde{B}$). Tallying carefully: start with $|\partial_e C| = 2^{n-1}$. Removing $\{1, \ldots, n-1\}$ adds $n-1$ boundary edges (its neighbours in $C$ now border the hole) and removes $1$ boundary edge (to $\{1,\ldots,n\}$). Adding $\{n\}$ adds $n-1$ boundary edges (to $\{j,n\}$) and removes $1$ boundary edge (to $\varnothing$, which was in $\partial_e C$). Net change: $(n-1) - 1 + (n-1) - 1 = 2(n-2)$. So $|\partial_e \tilde{B}| = 2^{n-1} + 2(n-2)$. For $n \geq 3$, we have $2(n-2) > 0$, so $|\partial_e \tilde{B}| > |\partial_e C| = 2^{n-1}$. For $n = 1$ and $n = 2$, direct verification shows the initial segment is optimal (and the anomalous set does not improve on it). Therefore the binary initial segment $C$ achieves the minimum edge boundary at every size, and \begin{align*} |\partial_e C| \leq |\partial_e B| \leq |\partial_e A|. \end{align*} [guided] Let us double-check the computation for $n = 3$, $|A| = 4$. The binary initial segment of size $4$ is $C = \mathcal{P}(\{1,2\}) = \{\varnothing, \{1\}, \{2\}, \{1,2\}\}$ with $|\partial_e C| = 4$ (each vertex sends one edge in the $3$-direction). The anomalous set is $\tilde{B} = \{\varnothing, \{1\}, \{2\}, \{3\}\}$, obtained by swapping $\{1,2\}$ for $\{3\}$. Computing $|\partial_e \tilde{B}|$ directly: from $\varnothing$, all three neighbours $\{1\}, \{2\}, \{3\}$ are in $\tilde{B}$, so $0$ boundary edges. From $\{1\}$, neighbours are $\varnothing$ (in), $\{1,2\}$ (out), $\{1,3\}$ (out), contributing $2$ boundary edges. From $\{2\}$, neighbours are $\varnothing$ (in), $\{1,2\}$ (out), $\{2,3\}$ (out), contributing $2$ boundary edges. From $\{3\}$, neighbours are $\varnothing$ (in), $\{1,3\}$ (out), $\{2,3\}$ (out), contributing $2$ boundary edges. Total: $|\partial_e \tilde{B}| = 6$. By our formula: $|\partial_e \tilde{B}| = 2^2 + 2(3-2) = 4 + 2 = 6$. This matches. And indeed $6 > 4 = |\partial_e C|$, confirming the anomalous set is suboptimal for $n = 3$. [/guided] [/step]