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.

Identify the vertices of the Boolean hypercube with subsets of $[n]$. Write $N(\mathcal{A})$ for the closed vertex neighbourhood and $\partial \mathcal{A}=N(\mathcal{A})\setminus \mathcal{A}$ for the external vertex boundary. The cube order used here is the simplicial order on the discrete cube: increasing size, then lexicographic order, with the smallest differing coordinate belonging to the earlier set. We prove Harper theorem by induction on $n$; subtracting the common size of the families converts a closed-neighbourhood comparison into the required boundary comparison.

First, the closed neighbourhood of a simplicial initial segment is itself an initial segment. Such a family consists of full lower levels and a lexicographic initial part of its last level. Its next-level neighbours form the upper shadow of that part. For a set in the next level, its lexicographically earliest lower-level subset is obtained by deleting its largest element. This map preserves the lexicographic order weakly. Membership in the upper shadow is equivalent to that earliest subset belonging to the original initial part, so the upper shadow is an initial part too. Empty and full families satisfy the assertion directly.

Assume the theorem in dimension $n-1$. Split $\mathcal{A}$ into two sections ${\mathcal{A}}_0,{\mathcal{A}}_1$ according to membership of coordinate $i$, deleting $i$ from the second section. Their closed-neighbourhood sections areReplace each section by a simplicial initial segment $I_0,I_1$ of the same size. Induction gives $|N(I_j)|\le |N({\mathcal{A}}_j)|$. By the preceding observation, each $N(I_j)$ is an initial segment and is nested with the other section. Consequentlyand the analogous inequality holds for the other section. Thus simplicial section compression preserves size and cannot increase the closed neighbourhood.

Repeatedly apply a nontrivial section compression. The sum of the positions of the family members in the full simplicial order strictly decreases: the order induced on either fixed-coordinate section is precisely its lower-dimensional simplicial order. This positive integer potential makes the process terminate at a family $\mathcal{B}$ fixed by every section compression.

We classify such terminal families for simplicial section compression. If an earlier vertex $x$ is absent while a later vertex $y$ is present, they cannot agree at any coordinate, since the corresponding section is an initial segment. Hence $y=x^c$. Every other vertex earlier than $y$ is present, and every other vertex later than $x$ is absent, since any further inverted pair would also have to be complementary. There can therefore be no vertex strictly between $x$ and $y$. Thus $\mathcal{B}$ either is an initial segment or is an initial segment with its last vertex replaced by the next, complementary vertex.

The complementary consecutive pairs are explicit. If $n=2r+1$, the ranks must be $r$ and $r+1$, and consecutive order positions forceThe corresponding initial segment $I$ contains all sets of size at most $r$, and $\mathcal{B}=I-\{x\}+\{y\}$. Its closed neighbourhood contains all sets of size at most $r+1$: for $r\ge 1$, deletion of just one $r$-set cannot remove all the $r$-subsets of any $(r+1)$-set, and $x$ remains adjacent to one of its $(r-1)$-subsets. In addition, the $r$ supersets of $y$ of size $r+2$ enter the neighbourhood. Thus $|N(\mathcal{B})|=|N(I)|+r$; the $n=1$ case gives equality directly.

If $n=2r$, the two vertices have rank $r$. Complementation reverses the lexicographic order within that rank, so consecutive complements occupy its middle two positions. These areNow $I$ contains all sets of size less than $r$ and all $r$-sets containing coordinate one. Its closed neighbourhood contains all sets of size at most $r$ and all $(r+1)$-sets containing one. For $r\ge 2$, each such $(r+1)$-set has at least two $r$-subsets containing one, so exchanging $x$ for $y$ loses none of these neighbours. It adds the $r-1$ supersets of $y$ of size $r+1$ that avoid one. Hence $|N(\mathcal{B})|=|N(I)|+r-1$. For $n=2$ the two neighbourhoods are both the entire cube.

In both exceptional cases the initial segment has no larger neighbourhood. The induction starts with the one-vertex zero-dimensional cube, and the compression argument now proves

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 hypercube graph $Q_n$ with subsets of $[n]$, adjacent when they differ by one element. Write $N(\mathcal{F})$ for a family's closed vertex neighbourhood. The simplicial order on the discrete cube orders first by size and then, within a rank, by lexicographic order: the least element of a symmetric difference belongs to the earlier set. The Harper theorem says that if $I$ is the initial simplicial segment with $|I|=|\mathcal{F}|$, thenEquivalently this minimizes the external vertex boundary at fixed cardinality. This is the vertex-isoperimetric assertion, distinct from the edge version in Question 3.

Here is the deduction of Kruskal-Katona theorem. For a family $\mathcal{B}\subseteq [n{]}^{(k)}$, adjoin every lower rank and set $\mathcal{D}=[n{]}^{(<k)}\cup \mathcal{B}$. For $k\ge 1$,The corresponding simplicial initial segment is $[n{]}^{(<k)}\cup L$, where $L$ is the rank-$k$ lexicographic initial segment of size $|\mathcal{B}|$. Canceling the common lower-rank count in Harper's inequality gives $|\nabla \mathcal{B}|\ge |\nabla L|$. The rank-zero case is immediate by considering its two possible families.

To turn upper shadows into lower shadows, let $\rho (i)=n+1-i$ and $T(B)=\rho ([n]\setminus B)$. This bijection reverses inclusion and changes rank $k$ to $n-k$. If $B$ precedes $C$ in lex order, the largest element of $T(B)△T(C)$ belongs to $T(C)$, so $T(B)$ precedes $T(C)$ in colexicographic order. Also $T(\nabla \mathcal{B})=\partial (T\mathcal{B})$. Hence applying the upper-shadow conclusion to the transformed family proveswhere $C$ is the colex initial segment of the same size and rank as $\mathcal{A}$. This is the Kruskal-Katona lower-shadow theorem. A colex segment's shadow is itself a colex segment: split its sets by their largest element, giving a full initial block of the preceding ground set followed by an initial block with the new largest element. The same description holds one rank lower. Iteration therefore shows that colex segments minimize shadows at every lower rank. This proves the Harper theorem implies the Kruskal-Katona theorem deduction, including the necessary complement and coordinate reversal.

The Erdős-Ko-Rado theorem states that for $1\le r\le n/2$, every intersecting family $\mathcal{A}\subseteq [n{]}^{(r)}$ satisfiesThe family of all $r$-sets containing a fixed point attains the bound. We use the standard convention of positive ranks here.

For the first proof, let $\mathcal{B}$ be the complements of members of $\mathcal{A}$, at rank $k=n-r\ge r$, and let $\mathcal{S}$ be its rank-$r$ lower shadow. It is disjoint from $\mathcal{A}$, since $A\subseteq [n]\setminus A^{\prime }$ would make two family members disjoint. Suppose $|\mathcal{A}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$. The colex rank-$k$ segment of that size contains every $k$-set on $[n-1]$ and at least one set containing $n$. Its rank-$r$ shadow therefore contains all $\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$ old $r$-sets and at least one new $r$-set containing $n$. The iterated Kruskal-Katona bound givesThen $|\mathcal{A}|+|\mathcal{S}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, impossible for disjoint subfamilies of rank $r$. This proves the Erdős-Ko-Rado theorem from shadows.

For the second proof use the Katona circle method. In any cyclic ordering of the $n$ points, an intersecting collection of length-$r$ intervals has at most $r$ members. To prove this, rotate one selected interval to end at position $n$, so it occupies $n-r+1,\dots ,n$. Intervals ending at $r,\dots ,n-r$ miss it and cannot be selected. Among the remaining endpoints other than $n$, pair $j$ with $j+n-r$ for $1\le j\le r-1$. The two intervals in each pair are disjoint because $n\ge 2r$, so at most one can be selected. Including the fixed interval gives at most $1+(r-1)=r$.

Now count pairs consisting of a family member and a permutation in which it is a cyclic interval. A fixed $r$-set has $nr!(n-r)!$ such permutations: choose its final position, its internal order, and the order of the remaining points. Each of the $n!$ permutations contributes at most $r$ family intervals by the proved cyclic interval intersection bound. ThusThis is the required cyclic-ordering proof, with its interval lemma established explicitly.

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.

Identify the Boolean hypercube $Q_n$ with the subsets of $[n]$. For a family $\mathcal{H}$, write $N(\mathcal{H})$ for its closed vertex neighbourhood, consisting of the family and all vertices at Hamming distance one from it. Order subsets first by increasing size and, within a fixed size, use lexicographic order: at the smallest coordinate on which they differ, the set containing that coordinate comes first. This is the simplicial order on the discrete cube. Harper's theorem states that if $I$ is its initial segment of size $|\mathcal{H}|$, thenThus simplicial initial segments minimize the external vertex boundary for each prescribed family size. The closed-neighbourhood and external-boundary formulations are equivalent because $|N(\mathcal{H})\setminus \mathcal{H}|=|N(\mathcal{H})|-|\mathcal{H}|$. No edge boundary is involved in this assertion.

We now give the deduction Harper theorem implies the Kruskal-Katona theorem, keeping track of the two different orders. For a family $\mathcal{F}$ of $r$-sets with $r\ge 1$, adjoin every smaller set:Its closed vertex neighbourhood is exactlywhere $\nabla \mathcal{F}$ is the upper shadow. Applying Harper theorem to $\mathcal{H}$ shows that, among $r$-uniform families of fixed size, the lexicographic initial segment minimizes the upper shadow: all the lower-level contributions to the two neighbourhood sizes are identical.

To convert this into a statement about the lower shadow of a $k$-uniform family $\mathcal{G}$, take $r=n-k$ and map each member $S$ to $R([n]\setminus S)$, where $R(i)=n+1-i$ reverses the ground-set coordinates. Complementation changes lower shadows to upper shadows, and the coordinate reversal preserves their sizes. Moreover, the resulting lexicographic order corresponds exactly to colexicographic order on the original $k$-sets: $S$ precedes $T$ in colexicographic order precisely when the largest element of $S△T$ lies in $T$. After complementation and reversal, the smallest differing coordinate lies in the image of $S$, as required for the stated lexicographic order. Hence a colexicographic initial segment minimizes the lower shadow, which is the Kruskal-Katona theorem. The cases $k=n$ and $k=0$ are immediate and need no adjoining construction.

For its usual numerical form, write the unique greedy binomial representationThen the Kruskal-Katona theorem saysHere is why the shadow of the colexicographic initial segment has exactly that size. Its first block consists of all $k$-sets in $[a_k]$. If any members remain, they have the form $\{a_k+1\}\cup T$, where $T$ runs through a colexicographic initial segment of $(k-1)$-sets. The lower shadow consists of all $(k-1)$-sets in $[a_k]$, together with $\{a_k+1\}$ adjoined to the lower shadow of that remainder. These two blocks are disjoint. Recursing gives precisely the displayed sum. For $m=0$, both the initial segment and its shadow are empty.

The Erdős-Ko-Rado theorem states that an intersecting family $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$, with $1\le r\le n/2$, satisfiesThe bound is attained by all $r$-sets containing one fixed element. For the proof Erdős-Ko-Rado theorem from shadows, take complements to obtain an $(n-r)$-uniform family $\mathcal{B}$ of the same size, and let $D$ be its rank-$r$ lower shadow. Every member of $D$ is disjoint from some member of $\mathcal{A}$, so $D\cap \mathcal{A}=\varnothing$. Iterating the Kruskal-Katona theorem bounds $|D|$ below by the rank-$r$ shadow of the colexicographic initial segment of size $|\mathcal{B}|$. This iteration is valid because lower shadows of colexicographic initial segments are again colexicographic initial segments, as the preceding block description shows.

If $|\mathcal{A}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{n-r}\right)$, that initial segment contains all $(n-r)$-sets in $[n-1]$ and at least one further set containing $n$. Since $r\le n-r\le n-1$, its rank-$r$ shadow contains every $r$-set in $[n-1]$ and at least one $r$-set containing $n$. Thus $|D|>\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$, implyingcontrary to their disjointness. This proves the bound. If $r>n/2$, all $r$-sets intersect and the trivial maximum is instead $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$.

For an intersecting family in a product alphabet, label the alphabet by $\mathbb{Z}/k\mathbb{Z}$. Partition the words into the classesEach class has $k$ words, and any two distinct words in it disagree in every coordinate. An intersecting family therefore contains at most one word per class. There are $k^{n-1}$ classes, and fixing the first coordinate gives an intersecting family of that size. Consequently the exact maximum isFor $k=1$ this just says that the single word may be included.

Finally, for a weakly intersecting family in a product alphabet, associate to each word its support $S(x)=\{i:x_i>1\}$. The occurring supports form an intersecting family of nonempty subsets, and the fibre over support $S$ has $(k-1{)}^{|S|}$ words. Put $w=k-1$. When $k\ge 2$, $w\ge 1$, and a support family can contain at most one of each complementary pair $S,[n]\setminus S$. For odd $n$, the larger support in each pair has size greater than $n/2$, soAll supports of size greater than $n/2$ are mutually intersecting, so taking every word over those supports achieves this bound. Thus the required extremal family is the strict-majority support family, with sizeThis is the weighted intersecting family bound on an odd Boolean lattice. For $k>2$, strict inequality between the complementary fibre weights forces this extremal family to be unique. For $k=2$, it is a largest family but need not be the only one; for example, all supports containing one fixed coordinate also attain the same size. For $k=1$, no word has a nonempty support, so the maximum is zero, again agreeing with the formula.

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.

For the Boolean hypercube, the initial segment of the simplicial order on the discrete cube minimizes the size of the closed vertex neighbourhood among families of a given size. Equivalently, it minimizes the external vertex boundary. This is a vertex assertion, distinct from the edge-isoperimetric inequality in the discrete cube.