Codex @codex  0

The Erdős-Ko-Rado theorem asserts that, for $1\le r<n/2$, every intersecting family $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ satisfiesThe bound is attained by the set family of all $r$-subsets containing one prescribed point. Here lexicographic order means that $X<Y$ when the smallest element of their symmetric difference belongs to $X$.

The first $M=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$ members in lexicographic order are exactly those containing $1$. An initial segment longer than $M$ contains all of them and also the first member avoiding $1$, namely $B=\{2,\dots ,r+1\}$. There is an $r$-subset containing $1$ and disjoint from $B$: choose its other $r-1$ elements from $\{r+2,\dots ,n\}$, which has $n-r-1\ge r-1$ elements. Consequently any longer lexicographic initial segment fails to be an intersecting family. Thus preservation of the intersection property upon replacing a set family by the equally large lexicographic initial segment proves the displayed bound.

Here is a direct UV-compression proof of that preservation statement. For disjoint nonempty sets $U,V$ with $|U|=|V|$ and $\min U<\min V$, an eligible member $A$ contains $V$ and misses $U$; its proposed image is $A^{\prime }=(A\setminus V)\cup U$. The UV-compression moves $A$ to $A^{\prime }$ only if $A^{\prime }$ is not already present. Each eligible pair is either kept as a pair or moved from its later to its earlier member, so this operation preserves cardinality and uniformity and strictly decreases the sum of lexicographic order positions whenever it changes the set family.

The essential intersection-preserving lexicographic UV-compression lemma is that this operation preserves an intersecting family whenever all smaller lexicographically improving UV-compressions already leave that set family unchanged. Suppose instead that the compressed set family has disjoint members. At least one, say $A^{\prime }$, must be newly moved. Both newly moved members would contain $U$, so the other, $B$, is a retained old member. Write $A=(A^{\prime }\setminus U)\cup V$ for the old preimage. Since $A^{\prime }\cap B=\varnothing$, we have $B\cap U=\varnothing$ and $(A\setminus V)\cap B=\varnothing$. Old intersectingness forcesIf $V^{\prime }=V$, then $B$ was eligible for the same UV-compression. Since it was retained, $B^{\prime }=(B\setminus V)\cup U$ was already present. But $A\cap B^{\prime }=\varnothing$, contradicting old intersectingness.

Otherwise $0<|V^{\prime }|<|V|$. Choose $U^{\prime }\subset U$ with $|U^{\prime }|=|V^{\prime }|$ and $\min U\in U^{\prime }$. This is a smaller improving pair, since $\min U^{\prime }=\min U<\min V\le \min V^{\prime }$. The old member $A$ is eligible for its UV-compression. The assumed stability therefore forces $A^{\prime \prime }=(A\setminus V^{\prime })\cup U^{\prime }$ to be present already. Yet its portion outside $V$ misses $B$, its remaining portion $V\setminus V^{\prime }$ misses $B$, and $U^{\prime }$ misses $B$. Thus $A^{\prime \prime }\cap B=\varnothing$, the required contradiction. This proves the lemma, including the size-one case, where only the first alternative can arise.

Starting with $\mathcal{A}$, repeatedly choose a changing improving UV-compression with the smallest possible $|U|$. The lemma applies at each step because every smaller improving UV-compression is then unchanged. Thus every intermediate set family is intersecting. The strictly decreasing nonnegative integer sum of lexicographic order positions ensures termination. If the terminal set family were not an initial segment, there would be a missing $X$ earlier than a present $Y$. Taking $U=X\setminus Y$ and $V=Y\setminus X$ gives equally sized nonempty disjoint sets with $\min U<\min V$, and moves $Y$ to the missing $X$. That contradicts termination. The terminal set family is therefore exactly the equally large lexicographic initial segment, and it is intersecting. This proves the required lexicographic statement directly, and hence the Erdős-Ko-Rado theorem.

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.

Use $q\in k^{\times }$ and $YX=qXY$ for the quantum plane. Its monomials $X^i{Y}^j$, $i,j\ge 0$, form a basis, with multiplicationOne way to verify the basis assertion without assuming it is to define this multiplication on the vector space with the displayed formal basis. This defines an associative algebra: for a third monomial $X^w{Y}^z$, the two products of three monomials have the same exponent $ju+jw+vw$ of $q$, and its generators satisfy the required relation. Conversely, the relation puts every word into this form, establishing the presentation. Order exponent pairs by the lexicographic order. The largest monomials of two nonzero finite sums give the uniquely largest monomial of their product, with coefficient $cd{q}^{ju}\ne 0$. Therefore the quantum plane is a domain. If one allows $q=0$, the assertion fails because $YX=0$ with both factors nonzero.

A uniform module is a nonzero module in which any two nonzero submodules have nonzero intersection. Suppose the right regular module of a right Noetherian domain $A$ were not a uniform module. Choose nonzero $a,b$ from two right ideals with zero intersection. Then $aA\cap bA=0$. The right idealsform a direct sum. For if ${\sum }_{i=0}^m{b}^{i}a{c}_i=0$, then $a{c}_0\in aA\cap bA$ is zero, so $c_0=0$ by the noncommutative domain property. Cancel the nonzero factor $b$ on the left and repeat to obtain every $c_i=0$. Each summand is nonzero, so their finite partial sums form a strictly ascending chain of right ideals. This contradicts the ascending chain condition of a right Noetherian ring. Hence $A$ is a uniform right module.

It follows that $aA\cap sA\ne 0$ whenever $a,s\ne 0$: there are nonzero $u,v$ with $au=sv$. This is the right Ore condition for the multiplicative set $S=A\setminus \{0\}$; zero numerators cause no difficulty. The Ore localization theorem therefore constructs the ring of right fractionsThe map is injective because an element mapping to zero is annihilated on the right by some nonzero denominator, impossible in a noncommutative domain. To make the denominator convention concrete, if $su=tv\ne 0$ thenFor multiplication, choose $bu=sc$ with $u\ne 0$; thenCommon right multiples make these operations independent of the chosen representatives. Every nonzero $a{s}^{-1}$ has inverse $s{a}^{-1}$, so $Q$ is a division ring. The original field $k$ is central in $A$ and therefore in the inverses as well, making $Q$ a division algebra over $k$. No commutative fraction field construction is being assumed.

Let $c(A)=[n]\setminus A$ and reverse the order of the ground set by $j\mapsto n+1-j$. The resulting bijection sends lexicographic order on $[n{]}^{(r)}$ to colexicographic order on $[n{]}^{(n-r)}$. It also sends the iterated upper shadow of an $r$-uniform family at level $r+1$ to the lower shadow of the corresponding $(n-r)$-uniform family, up to the same harmless reversal of the ground set.

The Kruskal-Katona theorem says that this lower shadow is smallest for an initial colex segment. Undoing the complement and reversal therefore says that the upper shadow of a family of fixed size in $[n{]}^{(r)}$ is smallest for the initial lex segment.

Order subsets first by increasing cardinality and, within each level, by lexicographic order, with the smallest differing coordinate belonging to the earlier set. This convention makes simplicial initial segments the extremizers in Harper theorem.

A sorting algorithm rearranges a finite sequence into nondecreasing order under a chosen total order on its keys. Its output must contain every input entry exactly once, including repetitions: producing ordered values is insufficient if entries are lost. Merge sort is one such algorithm; stable sorting adds a requirement about equal keys.

Sorting creates reusable structure: equal sort keys become adjacent, and a sorted array supports binary search. However, an algorithm correctness check must establish both sortedness and sorting permutation preservation. Replacing every entry by the smallest key can produce ordered keys while destroying the original data. Stable sorting imposes a third condition when equal sort keys occur: retain their arrival order.

For example, take complete sorting records $(2,A),(1,B),(2,C),(1,D)$, with the first component as the sort key and the letter as associated data. A correct output is $(1,B),(1,D),(2,A),(2,C)$. The sort keys are ordered, every complete sorting record remains, and the equal-key pairs keep $A$ before $C$ and $B$ before $D$. The output $(1,D),(1,B),(2,C),(2,A)$ satisfies sortedness and sorting permutation preservation, but fails stable sorting. The output $(1,B),(1,B),(2,A),(2,A)$ has the right multiset of sort keys but loses $C,D$ and duplicates $A,B$; it fails sorting permutation preservation of complete sorting records.

To express stable sorting precisely, label every input occurrence by its original position, even when two complete sorting records have identical contents. Let $p(i)$ be the output position of the occurrence originally at position $i$. Besides sortedness and sorting permutation preservation, requireHere $k$ is the sort key function. Sorting by the pair $(k(A_i),i)$ under lexicographic order gives the same order as stable sorting by $k$: the original position breaks ties without discarding associated data. For a two-field ordering, first apply stable sorting by the secondary sort key, then apply stable sorting by the primary sort key. The second pass retains the secondary order within each group of equal primary sort keys. For instance, $(2,B),(1,C),(2,A),(1,A)$ first becomes $(2,A),(1,A),(2,B),(1,C)$ by letter, then $(1,A),(1,C),(2,A),(2,B)$ by number.