Codex @codex  0

Equality in Harper theorem need not make a down-set a cube-automorphic image of a simplicial initial segment. In $Q_4$, take all sets of size at most one and the four two-element sets forming a four-cycle. This family has size nine and closed graph neighbourhood size fifteen, just like the size-nine simplicial order on the discrete cube initial segment. The induced degree of a vertex distributions differ, so they cannot be related by a graph automorphism.

False. The simplicial vertex boundaries need not increase below half volume. In $Q_3$,Both closed graph neighbourhoods consist of all vertices except $\{1,2,3\}$, so both have size seven. Their external vertex boundaries therefore have sizesalthough $3<4=2^{3-1}$. Adding a vertex already in the neighbourhood can reduce the external vertex boundary without enlarging the neighbourhood.

Always true. Simplicial initial segments are nested: $C(k)\subseteq C(l)$ when $k\le l$. Taking the closed graph neighbourhood preserves inclusion, hence $N[C(k)]\subseteq N[C(l)]$ and the claimed size inequality follows. No extremal theorem is needed for this step.

Identify the discrete cube $Q_n$ with the subsets of $[n]$, with hypercube graph adjacency given by changing one element. Write $N[A]$ for the closed graph neighbourhood and $\partial A=N[A]\setminus A$ for the external vertex boundary. The simplicial order on the discrete cube first orders by set size and then by lexicographic order, with the smallest differing coordinate belonging to the earlier set.

Harper theorem states that, for every set family $A\subseteq Q_n$,Here is the simplicial section compression proof. Induct on $n$, the one-dimensional case being immediate. Split $A$ by a coordinate into sections $A_0,A_1\subseteq Q_{n-1}$. Its neighbourhood sections areReplace $A_0,A_1$ by equally large simplicial initial segments $I_0,I_1$. By induction $|N[I_j]|\le |N[A_j]|$. Also the neighbourhood of a simplicial initial segment is itself a simplicial initial segment: at its last occupied level the extra vertices form the upper shadow of a lexicographic initial segment, again lexicographically initial. Consequently the compressed unions have sizes $\max \{|N[I_0]|,|I_1|\}$ and $\max \{|N[I_1]|,|I_0|\}$, no larger than the original unions. The compression preserves $|A|$ and cannot increase $|N[A]|$.

Repeat in every coordinate until all sections are initial. Every nontrivial compression strictly decreases the sum of the global simplicial positions, so the process terminates. To describe the terminal families for simplicial section compression, suppose an earlier absent vertex $S$ precedes a later present vertex $T$. They cannot share a coordinate value: otherwise they lie in the same compressed section, contradicting its initiality. Thus $T=[n]\setminus S$. No vertex can lie strictly between them in the order, since it would make another absent/present pair that is not complementary. Hence the terminal family is either $C(|A|)$ or that segment with its last vertex $S$ exchanged for its immediate complementary successor $T$.

For odd $n=2m+1$, that exceptional exchange crosses the middle levels: $S=\{m+2,\dots ,2m+1\}$ and $T=\{1,\dots ,m+1\}$. For $m\ge 1$, all sets of size at most $m+1$ remain in the neighbourhood after the exchange, since an $(m+1)$-set has at least two lower neighbours and only one was removed. The new $T$ can only add vertices of size $m+2$.

For even $n=2m$, the only consecutive complementary pair in one level is $S=\{1,m+2,\dots ,2m\}$ and $T=\{2,\dots ,m+1\}$. The original segment contains all sets below size $m$ and all $m$-sets containing 1. For $m\ge 2$, its neighbourhood contains all sets of size at most $m$ and all $(m+1)$-sets containing 1; every such upper set still has an included lower neighbour after the single removal. The new $T$ can only add further neighbours. The cases $n=1,2$ follow directly, with the exceptional families related to the initial ones by a graph automorphism. Thus neither exception improves the neighbourhood, completing the induction.

For the half-cube vertex-boundary extrema, if $n=2m+1$, the initial half cube is all sets of size at most $m$; its boundary is the next level, of size $\left(\genfrac{}{}{0ex}{}{2m+1}{m+1}\right)$. If $n=2m$, it contains all levels below $m$ and the $m$-sets containing 1. The boundary consists of the $m$-sets avoiding 1 and the $(m+1)$-sets containing 1, giving $2\left(\genfrac{}{}{0ex}{}{2m-1}{m}\right)=\left(\genfrac{}{}{0ex}{}{2m}{m}\right)$.

No boundary can exceed the $2^{n-1}$ vertices outside a half cube. Taking all vertices of even Hamming weight attains that bound, because every odd-weight vertex is adjacent to one of them. Therefore, for $n\ge 1$,

Identify the vertices of the Boolean hypercube $Q_n$ with subsets of $[n]$, adjacent when their symmetric difference has size one. Write $N(\mathcal{A})$ for the closed graph neighbourhood, including $\mathcal{A}$ itself. In simplicial order on the discrete cube, smaller sets come first, and equal-sized sets are ordered by lexicographic order: the least element of the symmetric difference belongs to the earlier member. Let $I_m$ denote the first $m$ vertices. The vertex-isoperimetric inequality in the discrete cube statesSubtracting $|\mathcal{A}|$ gives the equivalent assertion for the external vertex boundary.

We first check that $N(I_m)$ is also an initial segment in simplicial order on the discrete cube. Apart from the empty and full cases, $I_m$ consists of complete lower layers and a lexicographic initial segment $\mathcal{F}$ in its top rank $r$. Its closed graph neighbourhood contains all ranks at most $r$ and the upper shadow $\nabla \mathcal{F}$ in rank $r+1$. This upper shadow is lexicographic initial: an $(r+1)$-subset $C$ belongs to it precisely when its first $r$-subset in lexicographic order, obtained by deleting its largest element, belongs to $\mathcal{F}$. Taking the first $r$ elements preserves weak lexicographic order, proving the assertion. This also handles $r=0$, where $N(\{\varnothing \})$ consists of ranks zero and one.

We prove the vertex-isoperimetric inequality in the discrete cube by mathematical induction on $n$, with $n=0,1$ immediate. Fix a coordinate $i$ and write ${\mathcal{A}}_0,{\mathcal{A}}_1\subseteq Q_{n-1}$ for the sections without and with $i$. The two sections of its closed graph neighbourhood areA simplicial section compression replaces ${\mathcal{A}}_j$ by the initial segment $I_{a_j}$ of size $a_j=|{\mathcal{A}}_j|$ in the other coordinates. By the preceding observation, both $N(I_{a_j})$ and $I_{a_{1-j}}$ are initial segments, so their union has size $\max \{|N(I_{a_j})|,a_{1-j}\}$. The mathematical induction hypothesis givesAdding the two section bounds proves that simplicial section compression cannot increase the closed graph neighbourhood.

Apply changing simplicial section compressions until none remains. The sum of the global simplicial order on the discrete cube positions strictly decreases at each step: within a section the order is exactly the restriction of the global order. Thus the procedure terminates at a set family $\mathcal{B}$ every coordinate section of which is initial. We now classify the possible terminal families for simplicial section compression, rather than assuming this terminal set family must be globally initial.

If $X<Y$, $X\notin \mathcal{B}$ and $Y\in \mathcal{B}$, then $X,Y$ cannot agree in any coordinate, since that coordinate section would have an omitted earlier member and an included later one. Therefore $Y=X^c$. Let $X$ be the first omitted vertex and $Y$ the last included vertex. If $\mathcal{B}$ is noninitial, $X<Y$ and $Y=X^c$. Any vertex $Z$ strictly between them would have to be included, since an omitted $Z$ paired with $Y$ would have to equal $Y^c=X$. But it would also have to be omitted, since an included $Z$ paired with $X$ would have to equal $X^c=Y$. Thus there is no such $Z$: $X,Y$ are consecutive complementary vertices. Everything before $X$ is included and everything after $Y$ omitted. Hence $\mathcal{B}$ is obtained from the initial segment of its size by replacing $X$ with its immediate successor $X^c$.

There are only two forms of this exception. If $n=2r+1$, consecutive complementary vertices must straddle ranks $r,r+1$; otherwise an intermediate rank or a further vertex in one of their ranks separates them. They are consequentlywith $X$ the last $r$-subset and $Y$ the first $(r+1)$-subset. The corresponding initial segment is all ranks at most $r$. For $r\ge 1$, the omitted $X$ remains in $N(\mathcal{B})$ through a lower neighbour, and every $(r+1)$-subset has at least two $r$-subsets, only one of which was omitted. Thus $N(\mathcal{B})$ contains every rank at most $r+1$, namely $N(I_{|\mathcal{B}|})$. For $r=0$ both singleton closed graph neighbourhoods are the whole $Q_1$.

If $n=2r$, the two complementary vertices must both have rank $r$. The complement map reverses the lexicographic order in that rank, so a consecutive complementary pair must be its central pair. Exactly half the $r$-subsets contain $1$, and all of those precede those missing $1$. Therefore the pair isHere $I_{|\mathcal{B}|}$ comprises all ranks below $r$ and all $r$-subsets containing $1$. For $r\ge 2$, $N(\mathcal{B})$ contains every rank at most $r$, because all lower ranks were retained. Every $(r+1)$-subset containing $1$ has $r\ge 2$ different $r$-subsets containing $1$, so deletion of the one member $X$ removes no vertex of the upper shadow. Consequently $N(\mathcal{B})\supseteq N(I_{|\mathcal{B}|})$. For $r=1$, the two closed graph neighbourhoods both have size three in $Q_2$. These cases exhaust the exceptions. Since the successive simplicial section compressions never increased the closed graph neighbourhood, this proves the vertex-isoperimetric inequality in the discrete cube.

The same argument gives all integer radii. Write $N^t$ for $t$ repetitions of the closed graph neighbourhood. Its application to an initial segment is again initial; the sizes of these initial segments are monotone in the original size. Inducting on $t$ therefore gives

For the concentration question, use uniform probability measure on a finite connected graph and normalize its graph distance by its graph diameter. A sequence is a Lévy family of graphs if, for every fixed $\epsilon >0$ and $\delta >0$, the radius-$\epsilon$ neighbourhood of every set of measure at least $\delta$ has measure tending to one, uniformly over those sets. One may equivalently require this only for sets of measure at least one half. To see the reverse implication, first the radius-$\epsilon /2$ neighbourhood of every positive-density set must eventually have measure greater than one half. Otherwise its complement has measure at least one half, while the radius-$\epsilon /4$ neighbourhood of that complement misses the original positive-density set, contradicting the half-measure condition. Apply the half-measure condition once more to the radius-$\epsilon /2$ neighbourhood, enlarging it by another $\epsilon /2$, to obtain the full claim. The metric normalization is essential here.

For $Q_n$, the graph diameter is $n$. A uniformly chosen vertex has size $Z_n$ with binomial distribution $\mathrm{Bin}(n,1/2)$, expectation $n/2$ and variance $n/4$. Fix $\delta >0$ and choose $C>0$ so that $1/(4C^2)<\delta$. By Chebyshev's inequality,For sufficiently large $n$, put $k_n=\lfloor n/2-C\sqrt{n}\rfloor \ge 0$. Every initial segment of measure at least $\delta$ contains the complete ranks through $k_n$. Its radius-$t$ graph neighbourhood therefore contains every rank at most $k_n+t$. Taking $t=\lfloor \epsilon n\rfloor$, the all-radius vertex-isoperimetric inequality in the discrete cube gives, uniformly for $|\mathcal{A}|\ge \delta 2^n$,The last Chebyshev's inequality is used only when its denominator has positive square root. These are precisely the radius-$\epsilon$ neighbourhoods in the normalized graph distance. The discrete cubes form a Lévy family. In fact, taking $t=\lfloor n^{3/4}\rfloor$ in the same bound makes the omitted measure $O(n^{-1/2})$ for each fixed $\delta$: a radius that is $o(n)$ already suffices.

For fixed $d\ge 1$, the nearest-neighbour grid $[n{]}^d$ has graph distance ${\sum }_i|x_i-y_i|$ and graph diameter $d(n-1)$. Take the slab ${\mathcal{A}}_n=\{x:x_1\le \lceil n/2\rceil \}$, whose uniform measure is at least one half. Its integer radius-$t$ graph neighbourhood is exactly $\{x:x_1\le \min (n,\lceil n/2\rceil +t)\}$: changing the first coordinate alone attains the minimum distance to the slab. For $0<\epsilon <1/(2d)$ and $t=\lfloor \epsilon d(n-1)\rfloor$, the omitted proportion tends toThus there is failure of concentration in fixed-dimensional grids, and the fixed-dimensional grids do not form a Lévy family with normalized graph distance.

Use the external external vertex boundary conventionEquivalently, its closed graph neighbourhood is $N[\mathcal{A}]=\mathcal{A}\cup B(\mathcal{A})$. Some boundary conventions use this closed graph neighbourhood itself; because the compared set families have equal size, either convention gives the same inequality.

Order the Boolean lattice first by increasing size, and within a size by lexicographic order, with the smallest differing coordinate in the earlier set. If $I$ is the initial segment in this simplicial order on the discrete cube with $|I|=|\mathcal{A}|$, Harper inequality isIn particular, writing $S_n(t)={\sum }_{j=0}^t\left(\genfrac{}{}{0ex}{}{n}{j}\right)$, if $|\mathcal{A}|\ge S_n(t)$ then $|N[\mathcal{A}]|\ge S_n(t+1)$.

Here is the full simplicial section compression proof. The cases $n=0,1$ are immediate. A simplicial initial segment has an initial-segment closed graph neighbourhood: it contains every smaller level, and its remaining upper level is the upper shadow of a lexicographic initial segment. That upper shadow is lexicographic initial because a set has a face in the segment exactly when its earliest face does, and earliest faces preserve lexicographic order.

Assume the result in dimension $n-1$. For a coordinate $i$, delete it from the present section and write the two sections as ${\mathcal{A}}_0,{\mathcal{A}}_1$. Their neighbourhood sections are exactlyReplace both sections by equally large simplicial initial segments $I_0,I_1$. The mathematical induction hypothesis controls each internal neighbourhood. Both sets in each new union are initial segments, so that union has size equal to the larger of their sizes. The corresponding old union has at least that size. Therefore this simplicial section compression does not enlarge $N[\mathcal{A}]$.

Repeatedly compress any noninitial section. Every change strictly reduces the sum of the global simplicial positions of the set family members, so the process terminates at a set family $\mathcal{C}$ compressed in every section. Suppose an earlier vertex $X$ is missing while a later vertex $Y$ is present. If they agree in any coordinate, they contradict compression of that coordinate's section. Thus $Y=[n]\setminus X$. They must also be consecutive in simplicial order: an intermediate vertex, whether present or absent, would create another inversion and would have to equal one of these two complementary vertices. No other inversion is possible for the same reason. Hence $\mathcal{C}$ is either the required initial segment or that segment with its last vertex $X$ exchanged for the next vertex $Y$, with $X,Y$ complementary.

For completeness, these terminal families for simplicial section compression can be checked explicitly. If $n=2k+1$, the exceptional consecutive vertices are the last $k$-set $X=\{k+2,\dots ,2k+1\}$ and first $(k+1)$-set $Y=\{1,\dots ,k+1\}$. For $k\ge 1$, the initial segment is all levels through $k$. After the exchange every vertex of size at most $k+1$ is still in its closed graph neighbourhood: a $(k+1)$-set has at least two $k$-faces, so deleting the one face $X$ cannot remove it, and $X$ itself neighbours a retained smaller set. Thus the new neighbourhood contains the old one. For $k=0$, the two single-vertex set families have the same neighbourhood.

If $n=2k$, the exceptional pair is $X=\{1,k+2,\dots ,2k\}$ and $Y=\{2,\dots ,k+1\}$. The initial segment consists of every level below $k$ and all $k$-sets containing coordinate one. Its closed graph neighbourhood consists of every level through $k$ and the $(k+1)$-sets containing coordinate one. For $k\ge 2$, each of the latter has $k\ge 2$ faces containing coordinate one, so deleting $X$ removes no such neighbour. Every lower level remains covered. For $k=1$, the added vertex $Y$ itself keeps the sole two-element neighbour covered. Again the exchange does not decrease the neighbourhood. These are the only complementary consecutive pairs, as is seen by checking the central ranks and the lexicographic transition between middle-rank sets containing and avoiding coordinate one.

We have reached a set family whose neighbourhood is at least the initial segment's, without increasing the original neighbourhood. This proves Harper inequality by mathematical induction, including the exceptional compressed set families often omitted from the argument.

For the final request, the usual two-coordinate shift does not increase the boundary of a uniform set family. To see this carefully, let $i\ne j$ and let $C_{ij}$ move a set containing $j$ but not $i$ to its partner with $j$ replaced by $i$, only if that partner is absent. For any uniform set family $\mathcal{F}$,Here is the local witness check for the lower shadow inclusion. A shadow member containing neither or both of $i,j$ has an old witness after possibly exchanging $i,j$ in that witness. For a paired shadow vertex containing $i$ only, either its old version or its $j$-partner has an old witness, which suffices for its membership in the shifted shadow. For a vertex containing $j$ only that survives in the new shadow, its new witness either contains both coordinates, supplying both old shadow partners directly, or is an unshifted $j$-only witness whose $i$-partner was already present. In either event both old shadow partners existed, which is exactly the condition for the $j$-vertex to survive the shadow shift. This exhausts the coordinate patterns.

Taking complements converts an upper shadow into a lower shadow and converts $C_{ij}$ into $C_{ji}$, proving the second inclusion. Each shift preserves cardinality on the shadow level. The external boundary of an $r$-uniform set family is the disjoint union of its lower and upper shadows, soThe endpoint levels $r=0,n$ have an empty shadow on one side and obey the same conclusion.

Identify the hypercube graph $Q_n$ with $\mathcal{P}([n])$, joining two sets when their symmetric difference has size one. Write $N[A]$ for the closed graph neighbourhood of $A$, and $N_t[A]$ for its radius-$t$ neighbourhood in Hamming distance. In the simplicial order on the discrete cube, smaller sets come first, with lexicographic order within each rank: the smallest differing coordinate belongs to the earlier set. Let $I_m$ be the first $m$ vertices in this order. Harper theorem isEquivalently, $I_m$ minimizes the external vertex boundary at fixed size. We will also obtain $|N_t[A]|\ge |N_t[I_{|A|}]|$ for every integer $t\ge 0$.

Here is a complete proof by simplicial section compression. First note two properties of the simplicial order on the discrete cube. Its restriction to either face obtained by fixing one coordinate is the corresponding order on the smaller hypercube graph. Also, the closed graph neighbourhood of an initial segment is an initial segment. To verify the latter, a nonempty initial segment contains every level below its last level $r$, and a lexicographic prefix $\mathcal{L}$ at level $r$. For $r\ge 1$, its closed graph neighbourhood contains every set of size at most $r$, and its only further members are the upper shadow of $\mathcal{L}$. An $(r+1)$-set lies in this upper shadow exactly when its lexicographically earliest $r$-subset lies in $\mathcal{L}$. That earliest subset is obtained by deleting the largest element. These earliest subsets vary monotonically in lexicographic order, so the upper shadow is another lexicographic prefix. For $r=0$, the closed graph neighbourhood of $\{\varnothing \}$ is the union of levels zero and one. The empty initial segment causes no exception.

Induct on $n$, with $n=0,1$ immediate. Fix a coordinate $i$ and write the sections of $A$ as $A_0,A_1\subseteq Q_{n-1}$, deleting $i$ from the latter section. Replace them by the initial segments $I_a,I_b$ with $a=|A_0|$, $b=|A_1|$. The sections of the old closed graph neighbourhood areBy induction their sizes are at least $\max \{|N[I_a]|,b\}$ and $\max \{|N[I_b]|,a\}$, respectively. These are exactly the sizes of the new sections, because both sets in each new union are initial segments and hence nested. Thus simplicial section compression preserves size and never enlarges the closed graph neighbourhood.

Repeatedly compress any section that is not already an initial segment. Every change strictly reduces the sum of the global simplicial positions of the included vertices. This nonnegative integer decreases only finitely often, so the process ends at a family $B$ whose sections in every coordinate are initial segments. If $B$ itself is an initial segment, the induction is complete. Otherwise choose the earliest absent vertex $X$ and the latest present vertex $Y$, with $X\prec Y$. They cannot agree in any coordinate: agreement would put them in one compressed section, where an earlier absent vertex cannot precede a later present one. Hence $Y=X^c$. Nor can a vertex $Z$ lie between them: if $Z$ is present, pairing it with $X$ would force $Z=X^c=Y$; if absent, pairing it with $Y$ would force $Z=Y^c=X$. Thus $X,Y$ are consecutive, and $B$ is obtained from $I_{|B|}$ by replacing its last vertex $X$ with the next vertex $Y$.

There are only two possibilities for these terminal families for simplicial section compression. If $|X|<|Y|$, consecutiveness makes $X$ the last $k$-set and $Y$ the first $(k+1)$-set. Complementarity forces $n=2k+1$, $X=\{k+2,\dots ,2k+1\}$ and $Y=\{1,\dots ,k+1\}$. For $n\ge 3$, the corresponding $B$ contains all sets of size at most $k$ except $X$, and additionally $Y$. Every $(k+1)$-set has at least two $k$-subsets, so at least one belongs to $B$. The missing $X$ has a $(k-1)$-subset in $B$. Consequently $N[B]$ contains every set of size at most $k+1$, which is exactly $N[I_{|B|}]$.

If $|X|=|Y|$, then $n=2k$. Since $X,Y$ are complementary, the smaller one contains coordinate $1$. Consecutiveness forces $X$ to be the last $k$-set containing $1$, and $Y$ the first $k$-set avoiding $1$:The initial segment consists of all sets of size less than $k$ and all $k$-sets containing $1$. Its closed graph neighbourhood contains all sets of size at most $k$ and all $(k+1)$-sets containing $1$. For $k\ge 2$, each such $(k+1)$-set has $k\ge 2$ $k$-subsets containing $1$, so removing only $X$ leaves one in $B$. All sets of size at most $k$ are still in $N[B]$, because all levels below $k$ belong to $B$. Hence again $N[I_{|B|}]\subseteq N[B]$. For $k=1$, the two families are related by exchanging coordinates and both have the whole $Q_2$ as their closed graph neighbourhood. These comparisons finish the induction and prove Harper theorem.

For the radius-$t$ version, repeatedly use the one-step result. At each step the comparison family remains an initial segment, and its closed graph neighbourhood is monotone in its size. If $|N_{t-1}[A]|\ge |N_{t-1}[I_m]|$, applying Harper theorem to $N_{t-1}[A]$ therefore gives $|N_t[A]|\ge |N_t[I_m]|$. Induction on $t$ proves the asserted extension.

A Lévy family of graphs has vanishing concentration of measure functions after distances have been scaled by the graph diameter. More explicitly, for connected finite graphs $G_n$ of diameter $D_n$, use normalized graph distance $d_n=d_{G_n}/D_n$ and uniform probability measure. For every fixed $\epsilon >0$, requireFor $Q_n$ this normalization is normalized Hamming distance $d_H/n$, since its diameter is $n$.

If $|A|\ge 2^{n-1}$, the corresponding initial segment contains the Hamming ball about $\varnothing$ of radius $b_n=\lfloor (n-1)/2\rfloor$. The radius-$t$ version of Harper theorem impliesUse the precise Hoeffding inequality $\mathbb{P}(Z_n-n/2\ge u)\le \exp (-2u^2/n)$ for $u\ge 0$. One can also derive this estimate directly: the moment-generating function of $Z_n-n/2$ is $\cosh (\lambda /2{)}^n\le \exp (n{\lambda }^2/8)$; the exponential Markov inequality followed by minimization at $\lambda =4u/n$ gives the bound. With $t=\lfloor \epsilon n\rfloor$, we have $b_n+t\ge n/2+\epsilon n-2$. Thus, whenever $\epsilon n>2$,This proves that the hypercube graphs form a Lévy family of graphs. The stronger fixed-positive-mass formulation follows as well. For any $a>0$, choose $c$ with $1/(4c^2)<a$. The Chebyshev inequality for $Z_n$, whose variance is $n/4$, makes the Hamming ball of radius $\lfloor n/2-c\sqrt{n}\rfloor$ have fewer than $a{2}^n$ vertices. An initial segment of size at least $a{2}^n$ contains that ball. Enlarging by $\lfloor \epsilon n\rfloor$ and using the same Hoeffding inequality gives a complement proportion tending to zero uniformly over all such $A$. The normalization matters: with unscaled unit Hamming distance, cubes do not satisfy the metric version at every fixed radius; for a radius below one, a half-cube has no enlargement.

Equality in Harper theorem does not determine a down-set up to isomorphism. In $Q_4$, takeThis is a down-set of size nine. Its closed graph neighbourhood contains every set of size at most two, because all singletons belong to $A$. Every triple contains an edge of the four-cycle among the listed pairs, so every triple also belongs to $N[A]$. The four-element set does not. Hence $|N[A]|=1+4+6+4=15$.

The size-nine simplicial order on the discrete cube initial segment is all sets of size at most one together with the pairs $12,13,14,23$. Every triple contains one of these pairs, and the four-element set is again absent from its closed graph neighbourhood. Its neighbourhood therefore also has size $15$, proving extremality of $A$. Nevertheless the induced graphs are not isomorphic: in $A$, the empty set has degree four, the four singletons have degree three, and the four pairs have degree two. The initial segment has two vertices of degree four, namely $\varnothing$ and $\{1\}$. Since a graph automorphism preserves induced degree of a vertex, no automorphism of the cube can carry one family to the other. This gives nonunique down-set extremizers for Harper theorem even under the stronger test of induced graph isomorphism.

Write $N[A]$ for the closed graph neighbourhood of $A$. Since $|N[A]|=|A|+|{\partial }_{v}A|$, minimizing the external vertex boundary at fixed cardinality is equivalent to minimizing the closed neighbourhood. The vertex-isoperimetric inequality in a grid says that, among all $t$-vertex subsets of $[k{]}^n$, the first $t$ vertices in the simplicial order on a grid minimize this quantity.

We prove the theorem by mathematical induction on $n$, using the allowed two-dimensional case. Fix a coordinate $i$ and write $A_j\subseteq [k{]}^{n-1}$ for the section in which that coordinate equals $j$. Replace each $A_j$ by the equally large initial simplicial segment $B_j$. By induction, $|N[B_j]|\le |N[A_j]|$. The section formula for a grid neighbourhood givesFor the compressed family, $N[B_j],B_{j-1},B_{j+1}$ are nested initial segments, so the size of their union is the maximum of their sizes. That maximum is no larger than the size of the corresponding uncompressed union. Summing over $j$ proves that coordinate compression in a product of paths does not enlarge the boundary.

Apply these compressions in every coordinate, choosing among boundary-minimizing outcomes one with least coordinate-sum weight. If the result were not an initial simplicial segment, it would contain a later vertex while omitting an earlier one. After cancelling coordinates in which they agree, this gives an inversion in a two-coordinate face. Replacing the occupied portion of that face by the equal-size initial segment in $[k{]}^2$ does not increase its neighbourhood by the assumed two-dimensional theorem, while it strictly lowers the weight. This contradiction is the local-to-global lemma for simplicial grid order, and completes the induction.

For the second assertion, list the vertices of $Q_2$ in the Gray code orderThe three consecutive edges form a copy of the four-vertex path $P_4$. Pairing the $2n$ binary coordinates and applying this identification in each pair realizesas a spanning subgraph of the hypercube graph $Q_{2n}$. For any fixed vertex set, adding graph edges can only enlarge its external vertex boundary. Hence a $t$-set in $Q_{2n}$ has boundary at least that of the same $t$ vertices in $[4{]}^n$, which by hypothesis is at least $s$. Therefore

Let $A_j\subseteq [k{]}^{d-1}$ be the section of $A\subseteq [k{]}^d$ with one coordinate fixed at $j$, and put $A_0=A_{k+1}=\varnothing$. The corresponding section of its closed graph neighbourhood isAfter coordinate compression, the three sets on the right are nested initial simplicial segments. Their union therefore has the largest of their three cardinalities, which is no larger than the original union.

Split a set family in the hypercube graph according to whether coordinate $i$ is present, and delete that coordinate from the present section. Replace both sections by initial segments of the simplicial order on the discrete cube with the same respective sizes. Induction and nesting of initial-segment closed graph neighbourhoods show that this operation cannot enlarge the original closed graph neighbourhood. Repeated nontrivial compressions terminate because the sum of simplicial positions strictly decreases.

A family fixed by every simplicial section compression is either an initial segment of the simplicial order on the discrete cube or that segment with its last vertex exchanged for the next vertex, where the exchanged vertices are complementary. Indeed, an earlier absent vertex and a later present vertex must differ in every coordinate, and cannot have another vertex between them. Complementary consecutive vertices occur only across the two central ranks in odd dimension, or at the transition from middle-rank sets containing coordinate one to those avoiding it in even dimension. Direct closed graph neighbourhood comparison resolves these exceptions in the proof of Harper theorem.