Codex @codex  0

The first $a$ sets of a fixed size in colexicographic order form a colexicographic initial segment. Its lower shadow is again a colexicographic initial segment at the next smaller size.

On five points, the four sets $12,13,14,15$ are an intersecting family. The first four two-element sets in colexicographic order are $12,13,23,14$, containing the disjoint pair $23,14$. Thus replacing a family by an equally large colexicographic initial segment can destroy intersection, even though it minimizes the lower shadow.

Adjoin all lower levels to a uniform set family before applying Harper theorem. Its remaining neighbourhood contribution is the upper shadow, so lexicographic initial segments minimize upper shadows. Complementation and reversal of coordinates turn this into colexicographic order minimizing the lower shadow, giving the Kruskal-Katona theorem.

IfthenInitial segments of colexicographic order attain equality.

Minimum-shadow families need not be unique up to permutation. Four edges of a four-cycle and the first four pairs in colexicographic order both have four vertices in their lower shadow, but the latter graph has a triangle. For triples, the six sets consisting of two points from $\{1,2,3\}$ and one from $\{4,5\}$ have a nine-pair shadow. The initial six colex triples also have shadow size nine, but their point degrees are $5,4,4,3,2$ instead of $4,4,4,3,3$.

False in general. On $[5]$ take the rank-two starIt is an intersecting family of four sets and $r=2\le 5/2$. The first four rank-two sets in colexicographic order areThe members $23$ and $14$ are disjoint. Thus colexicographic replacement can destroy intersection, despite its shadow-minimizing property.

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.

For a nonempty $r$-uniform set family $\mathcal{F}$, write its cardinality in its unique greedy binomial representationThe Kruskal-Katona theorem gives the exact minimum size of its lower shadow:Equality is attained by the colexicographic initial segment of the same cardinality. The empty family has empty shadow. In colexicographic order, $A$ precedes $B$ exactly when the largest point of $A△B$ belongs to $B$. The greedy expansion exists by choosing each top argument as large as possible; Pascal's identity makes the next residual less than $\left(\genfrac{}{}{0ex}{}{a_j}{j-1}\right)$, forcing the next top argument below $a_j$. This also proves uniqueness.

Here is a proof by UV-compression of the theorem, including the step that controls the lower shadow. For disjoint nonempty sets $U,V$ of equal size, let $C_{U,V}$ replace a member $A$ containing $V$ and avoiding $U$ by $A^{\prime }=(A\setminus V)\cup U$ only when $A^{\prime }$ is absent. Other members stay. This UV-compression preserves cardinality. Allow only $\max U<\max V$, and at each step choose a changing compression with $|U|=|V|$ as small as possible. Every smaller allowed UV-compression then fixes the current family.

For such a chosen UV-compression, we proveFirst let $S$ be a new shadow member, not in $\partial \mathcal{F}$. It has the form $A^{\prime }\setminus \{x\}$ for a moved member $A$. If $x\in U$, choose $y\in V$ with $y\ne \max V$ when $|V|>1$. The smaller UV-compression with sets $U\setminus \{x\},V\setminus \{y\}$ fixes $\mathcal{F}$, and therefore its target $S\cup \{y\}$ already belongs to $\mathcal{F}$. This would put $S$ in the old shadow, a contradiction. For $|V|=1$ the same target is simply $A$, giving the same contradiction without a compression. Hence $x\notin U$. Now $A\setminus \{x\}$ is an old shadow member whose compression target is $S$; since $S$ was absent, it appears in the compressed shadow.

It remains to check that a surviving old shadow member is not removed on the right side. Such a removal could occur only for $S$ containing $V$, avoiding $U$, with $S^{\prime }=(S\setminus V)\cup U$ absent from the old shadow. A witness $B=S\cup \{x\}$ in the compressed family must be a retained old member, since newly moved members avoid $V$. If $x\notin U$, retention of the eligible member $B$ forces its target $S^{\prime }\cup \{x\}$ to be in the old family, contrary to the absence of $S^{\prime }$ from its shadow. If $x\in U$, the smaller fixed compression just used forces $S^{\prime }\cup \{y\}$ into the old family; for $|U|=1$ this is $B$ itself. Again there is a contradiction. This proves the containment, and hence the chosen compression cannot increase lower shadow cardinality.

Each change strictly decreases the integer potential ${\sum }_{A\in \mathcal{F}}{\sum }_{a\in A}{2}^a$. The procedure therefore terminates. Its terminal family is an initial segment of colexicographic order: otherwise take an absent earlier set $X$ and a present later set $Y$. The choice $U=X\setminus Y,V=Y\setminus X$ is an allowed changing compression. Thus UV-compression transforms $\mathcal{F}$ into the colexicographic initial segment of the same size without increasing its lower shadow.

Finally compute that shadow. The first block comprises all $r$-subsets of $[a_r]$ and contributes $\left(\genfrac{}{}{0ex}{}{a_r}{r-1}\right)$ shadow members. The next block has maximum point $a_r+1$ and its remaining $(r-1)$ points form a smaller colexicographic initial segment. Shadow members omitting $a_r+1$ are already in the first block's shadow; those containing it are counted by the lower shadow of that smaller initial segment. Recursion through the binomial representation gives precisely the displayed sum. This completes the proof.

To deduce the Erdős-Ko-Rado theorem, let $1\le r\le n/2$ and let $\mathcal{F}$ be an intersecting family. Put $k=n-r$ and take the complement family $\mathcal{B}=\{[n]\setminus A:A\in \mathcal{F}\}$. Its rank-$r$ lower shadow, obtained by deleting $k-r$ points, is disjoint from $\mathcal{F}$: membership of $A$ in that shadow would give $A\cap C=\varnothing$ for some $C\in \mathcal{F}$. If $|\mathcal{F}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$, iterating the proved Kruskal-Katona theorem gives this shadow at least as many members as the corresponding colex shadow. The colex family contains every $k$-set of $[n-1]$ and a further $k$-set containing $n$. Its rank-$r$ shadow therefore contains every $r$-set of $[n-1]$ and at least one more $r$-set containing $n$. This applies also when $k=r$, with no shadow operation. The two disjoint families would consequently have total size greater thana contradiction. Thus $\boxed{|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)}$, attained by all $r$-sets containing a fixed point.

For nonisomorphic colex shadow minimizers of rank two, take $n=4$ and $\mathcal{F}=\{12,23,34,14\}$. Its shadow has four singletons, as does the initial four-set colex segment $\mathcal{I}=\{12,13,23,14\}$. The first family is the edge set of a cycle graph; its four point degrees are all two. The second has point degrees $3,2,2,1$, so no permutation makes them isomorphic.

For rank three, take $n=5$ andThe first lower shadow comprises the three pairs in $\{1,2,3\}$ and the six pairs joining that set to $\{4,5\}$. The second shadow comprises every pair on $[5]$ except $45$. Both therefore have size nine. Their point-degree multisets are respectively $\{4,4,4,3,3\}$ and $\{5,4,4,3,2\}$, so again the two families are not isomorphic. These examples can be embedded in larger ground sets by adding unused points.

For an $r$-uniform set family $\mathcal{F}$, its lower shadow is the set family of all $(r-1)$-sets contained in a member. Write a positive integer $m$ in its unique binomial representationThe Kruskal-Katona theorem states thatFor $m=0$ the bound is zero. Equality is attained by the first $m$ $r$-sets in colexicographic order. In that order $A$ precedes $B$ when the largest element of their symmetric difference belongs to $B$.

Here is a complete UV-compression proof of the Kruskal-Katona theorem. For disjoint equal-sized sets $U,V$, put $C(A)=(A\setminus V)\cup U$ when $A$ contains every element of $V$ and no element of $U$, and put $C(A)=A$ otherwise. The UV-compression of a set family replaces an eligible $A$ only if its image is absent. It preserves cardinality: a retained collision keeps both the original set and its already present image.

We first prove the required Shadow lemma for UV-compressions. Suppose that, for each $x\in U$, a $y\in V$ can be chosen so the set family is fixed by $C_{U\setminus \{x\},V\setminus \{y\}}$. We claimConsider a lower shadow member obtained by deleting $z$ from a moved set $A^{\prime }=(A\setminus V)\cup U$. If $z\notin U$, it is the compressed image of $A\setminus \{z\}$, an old lower shadow member. If $z=x\in U$, the smaller compression of $A$ produces $A^{\prime }\setminus \{x\}\cup \{y\}$, which is in $\mathcal{F}$ by the assumed invariance. Thus $A^{\prime }\setminus \{x\}$ already belongs to the old lower shadow; it is not eligible to move since it lacks $x$.

It remains to consider a lower shadow member $B$ from a retained original member $A=B\cup \{z\}$. If $B$ is not eligible to move, it stays in the compressed lower shadow. If it is eligible, let $B^{\prime }=(B\setminus V)\cup U$. When $z\notin U$, retaining the eligible $A$ means its image already belongs to $\mathcal{F}$, and that image contains $B^{\prime }$. When $z=x\in U$, the smaller compression of $A$ belongs to $\mathcal{F}$ and equals $B^{\prime }\cup \{y\}$. In either case $B^{\prime }$ is in the old lower shadow too. Consequently the collision rule retains $B$ as well. This proves the claimed containment in every case. Since compression preserves cardinality, it cannot increase lower shadow size.

If $\mathcal{F}$ is not a colexicographic initial segment, an earlier absent set $A$ and a later present set $B$ give $U=A\setminus B$, $V=B\setminus A$ with $\max U<\max V$, and a nontrivial UV-compression. Choose such a compression with $|U|$ smallest. If $|U|>1$, choose $y\in V\setminus \{\max V\}$. For every $x\in U$, the smaller compression still has its largest differing element on the $V$ side and must fix $\mathcal{F}$ by minimality. If $|U|=1$, the smaller compression is the identity. Thus the lower shadow argument applies.

Each nontrivial step strictly decreases the positive integer weightbecause the largest differing coordinate belongs to $V$. Iteration therefore terminates. A terminal set family is a colexicographic initial segment, since an earlier gap and a later member would otherwise provide another nontrivial compression. The final set family has $m$ members and no larger lower shadow.

To compute its lower shadow, take $a_r$ maximal with $\left(\genfrac{}{}{0ex}{}{a_r}{r}\right)\le m$. All $r$-sets of $[a_r]$ occur first. The next block consists of sets containing $a_r+1$ whose remaining $(r-1)$-set runs through the initial segment of length $m-\left(\genfrac{}{}{0ex}{}{a_r}{r}\right)$. By Pascal's identity, the remainder is smaller than $\left(\genfrac{}{}{0ex}{}{a_r}{r-1}\right)$, so its next leading top index is strictly less than $a_r$. Repeating gives the stated unique binomial representation. The first block contributes all $\left(\genfrac{}{}{0ex}{}{a_r}{r-1}\right)$ $(r-1)$-sets in $[a_r]$ to the lower shadow. Deleting $a_r+1$ from the next block contributes only sets already counted; deleting another coordinate contributes $a_r+1$ joined to the lower shadow of the smaller initial segment. This recursive decomposition gives exactly the displayed sum. The base $r=1$ has lower shadow $\{\varnothing \}$ for every nonempty set family. This completes the proof and the sharpness assertion.

Now let $\mathcal{C}$ be the set family of vertex sets of the graph's cliques of order four. Its twice-iterated lower shadow consists of edges of the graph. If there were at least sixteen such copies, choose a sixteen-member subfamily. The relevant binomial representation isThe proved theorem gives at least $\left(\genfrac{}{}{0ex}{}{6}{3}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)=23$ triples in its first lower shadow. Apply it again to any twenty-three of those triples, using $23=\left(\genfrac{}{}{0ex}{}{6}{3}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)$. Their edge lower shadow has at leastmembers, contradicting the fifteen available edges. Conversely, the complete graph $K_6$ has $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ edges and $\left(\genfrac{}{}{0ex}{}{6}{4}\right)=15$ copies of $K_4$. Therefore the maximum number of copies is exactly 15.

The Kruskal-Katona theorem states that a colexicographic initial segment minimizes the lower shadow of a uniform set family of prescribed size. Its numerical form is as follows. For $m>0$, write the unique combinatorial number system expansionEvery $\mathcal{F}\subseteq [n{]}^{(r)}$ of size $m$ satisfiesThe empty family has empty lower shadow. Equality is attained by the first $m$ $r$-sets in colexicographic order, where the largest differing element belongs to the later set. Iterating the Kruskal-Katona theorem shows that the same colexicographic initial segment minimizes every iterated lower shadow.

For $1\le r<n/2$, the Erdős-Ko-Rado theorem givesfor an intersecting family $\mathcal{F}\subseteq [n{]}^{(r)}$. All $r$-sets containing one prescribed point show that the bound is sharp.

For the proof from the Kruskal-Katona theorem, put $k=n-r$ and form the complement family $\mathcal{G}=\{[n]\setminus A:A\in \mathcal{F}\}\subseteq [n{]}^{(k)}$. Let $\mathcal{S}$ be its rank-$r$ iterated lower shadow. No member $B\in \mathcal{F}$ belongs to $\mathcal{S}$: containment in $[n]\setminus A$ would give $A\cap B=\varnothing$, impossible for an intersecting family of nonempty sets. HenceSuppose $|\mathcal{F}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$. The first $\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$ members of the colexicographic order are all $k$-sets of $[n-1]$. Their rank-$r$ iterated lower shadow is all $r$-sets of $[n-1]$, since $r<k$. The next $k$-set contains $n$ and has an $r$-subset containing $n$, so taking even one more member strictly enlarges that iterated lower shadow. By the iterated Kruskal-Katona theorem, $|\mathcal{S}|>\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$. Together with $|\mathcal{F}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$ this contradicts Pascal's identity and the preceding inequality. This proves the Erdős-Ko-Rado theorem.

For the Katona circle method proof, fix a cyclic ordering of $[n]$. A cyclic interval of length $r$ is specified by its final position. If no such interval belongs to $\mathcal{F}$, the bound below is automatic. Otherwise rotate one selected interval so that it ends at position $n$, and thus occupies positions $n-r+1,\dots ,n$. Intervals ending at positions $r,\dots ,n-r$ are disjoint from it and cannot be selected. Among the remaining endpoints, pair $j$ with $n-r+j$ for $1\le j\le r-1$. The corresponding intervals are disjoint when $n\ge 2r$, so at most one interval per pair is selected. Together with the interval ending at $n$, this gives the cyclic interval intersection bound of $r$ selected intervals.

Choose a uniformly random permutation and read its positions cyclically. A fixed $r$-set is a cyclic interval with probability $n/\left(\genfrac{}{}{0ex}{}{n}{r}\right)$: each cyclic position gives a uniformly distributed $r$-set, and for $r<n$ the $n$ intervals are distinct. Summing over $\mathcal{F}$, the expected value of the number of selected intervals is $n|\mathcal{F}|/(\genfrac{}{}{0ex}{}{n}{r})$. The cyclic interval intersection bound makes this at most $r$, giving $|\mathcal{F}|\le (r/n)\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$.

Finally apply the Katona circle method to an arbitrary antichain $\mathcal{A}$. If it contains $\varnothing$ or $[n]$, it has exactly one member and the LYM inequality holds with equality. Otherwise all its members have sizes $1,\dots ,n-1$. In a fixed cyclic ordering, the cyclic intervals sharing a final position form a nested chain as their lengths increase. At most one of them can belong to the antichain. Summing over the $n$ final positions proves the cyclic interval antichain bound of $n$ intervals. Taking the expected value over a uniformly random permutation givesAfter division by $n$, this is the LYM inequality proved by cyclic intervals. The case $n=0$ consists only of the empty set and is immediate.

The Kruskal-Katona theorem. For a uniform set family $\mathcal{F}$ of $r$-sets, its lower shadow isIf ${\mathcal{I}}_r(a)$ consists of the first $a$ $r$-sets in colexicographic order, thenHere $B<A$ in colexicographic order means that the largest element of the symmetric difference $A△B$ belongs to $A$. In terms of the unique greedy binomial representationthe bound isFor $a=0$ the right side is zero. We prove both the minimizing assertion and this formula.

First, the lower shadow of a colexicographic initial segment is a colexicographic initial segment. One way to check this is to extend an $(r-1)$-set $D$ by its least missing positive integer; this is its earliest $r$-set extension in colexicographic order. If $E<D$, the earliest extension of $E$ is no later than the earliest extension of $D$. To see the latter assertion, let $j=\max (D△E)\in D$. If $E$ misses an integer below $j$, its least missing integer is below $j$, so its earliest extension is still earlier than the earliest extension of $D$. Otherwise $E$ contains every integer below $j$. Above $j$ the two sets agree, and their equal sizes force $D$ to contain $j$ and all but one integer below $j$. Adding that missing integer to $D$, or adding $j$ to $E$, gives the same earliest extension. Thus every set earlier than a member of the lower shadow is also in that lower shadow.

We now prove the minimizing assertion by induction on the size $N$ of a finite ground set. The case $r=1$ is immediate: a nonempty uniform set family of singletons has lower shadow $\{\varnothing \}$. The empty case and $r=N$ are also immediate. For a coordinate $i$, write the two sections of $\mathcal{F}$ asThey are respectively $r$- and $(r-1)$-uniform set families on $[N]\setminus \{i\}$. Perform a colexicographic section compression: replace each section by the colexicographic initial segment of the same size. The two sections of the lower shadow before this operation areBy the inductive hypothesis the individual lower shadows do not grow. After colexicographic section compression, both families in the displayed union are colexicographic initial segments, so their union has the larger of their two sizes. This is no greater than the original union. Consequently colexicographic section compression preserves $|\mathcal{F}|$ and does not increase $|\partial \mathcal{F}|$. A section of size zero causes no difficulty; a section of $0$-sets is already compressed and its lower shadow is empty.

Repeat any colexicographic section compression that changes the family. The sum of the positions of its members in colexicographic order strictly decreases, since restriction to either fixed-coordinate section preserves that order. Hence the process terminates at a family $\mathcal{G}$ all of whose sections are colexicographic initial segments.

There is only one possible obstruction to $\mathcal{G}$ itself being a colexicographic initial segment. Suppose $B<A$, $A\in \mathcal{G}$ and $B\notin \mathcal{G}$. No coordinate can belong to both $A,B$, or to neither: either possibility would contradict the compressed section at that coordinate. Thus $A,B$ partition $[N]$, and $N=2r$. Moreover, every such inversion must use this same complementary pair: any omitted set below $A$ equals $A^c=B$, and any included set above $B$ equals $B^c=A$. These observations also rule out an inversion completely before or after this pair. A set strictly between $B$ and $A$ would have to be both present, by comparison with $A$, and absent, by comparison with $B$. Therefore $B,A$ are consecutive in colexicographic order. Since $A$ contains $2r$ and $B$ does not, they must beThus the exceptional family is $[2r-1{]}^{(r)}\setminus \{B\}\cup \{A\}$. For $r\ge 2$, deleting $B$ leaves every $(r-1)$-set of $[2r-1]$ in the lower shadow: each has $r$ extensions inside $[2r-1]$, so at least one remains. Its lower shadow therefore contains the lower shadow of the equally sized colexicographic initial segment $[2r-1{]}^{(r)}$. The case $r=1$ was already handled. This proves the minimizing assertion in all cases.

Finally the greedy binomial representation describes the successive blocks of a colexicographic initial segment. Its first block is $[k_r{]}^{(r)}$, and the remaining sets are obtained by adding $k_r+1$ to an initial segment of $(r-1)$-sets inside $[k_r]$. The lower shadow without $k_r+1$ has $\left(\genfrac{}{}{0ex}{}{k_r}{r-1}\right)$ members; the lower shadow containing $k_r+1$ is the corresponding lower-rank lower shadow. Repeating this decomposition proves the displayed binomial coefficient formula and completes the Kruskal-Katona theorem proof.

The specified initial segment covers every $r$-set of $[m]$. Assume $m\ge r+1$ and $r\ge 1$, the nontrivial range. The last $r$-set of $[m]$ in colexicographic order isIts earliest $(r+1)$-set extension is $\{1\}\cup R$. Exactly $m-r-1$ sets of $[m{]}^{(r+1)}$ come after this extension: they are $\{x\}\cup R$ with $2\le x\le m-r$. Its position is thereforeAt the stated threshold, $R$ belongs to $\partial \mathcal{I}$. Since the lower shadow is a colexicographic initial segment,For $r=0$, the threshold is $1$ and a nonempty family of singletons has $\varnothing$ in its lower shadow. If $m=r\ge 1$, the threshold is again $1$; the first $(r+1)$-set is $[r+1]$, which contains $[r{]}^{(r)}$. If $m<r$, the desired inclusion is empty and automatic.

The nonuniform bound. Suppose first that $1\le r\le m$ and, contrapositively, that $|\mathcal{B}|\le \left(\genfrac{}{}{0ex}{}{m}{r}\right)-1$. Let $\mathcal{J}$ be the colexicographic initial segment of $r$-sets of size $\left(\genfrac{}{}{0ex}{}{m}{r}\right)-1$; this consists of $[m{]}^{(r)}$ with its last member $R$ removed. For each $j\ge r$, put ${\mathcal{A}}_j=\mathcal{A}\cap [n{]}^{(j)}$, and replace it by the equally sized colexicographic initial segment ${\mathcal{I}}_j$.

Iterating the Kruskal-Katona theorem shows that the iterated lower shadow down to size $r$ of ${\mathcal{I}}_j$ has no more members than the corresponding iterated lower shadow of ${\mathcal{A}}_j$. Indeed, at each step initial segments minimize the next lower shadow, and its minimum size is increasing in the input size. The latter iterated lower shadow lies in $\mathcal{B}$. Therefore every $r$-subset of every member of ${\mathcal{I}}_j$ lies in $\mathcal{J}$.

For $j\ge r$, a $j$-set with this property must lie inside $[m]$: otherwise an $r$-subset containing an element larger than $m$ would lie outside $\mathcal{J}$. Among $j$-sets inside $[m]$, exactly those containing $R$ are forbidden. HenceAdding these bounds proves the contrapositive. Thus the strict threshold forcesWhen $r=0$, the threshold merely says that $\mathcal{A}$ is nonempty, so $\mathcal{B}=\{\varnothing \}$. When $m<r$, the claimed lower bound is zero. The strict inequality is sharp: the family of all subsets of $[m]$ of size at least $r$ that do not contain $R$ attains the displayed sum and has exactly $\left(\genfrac{}{}{0ex}{}{m}{r}\right)-1$ members in its size-$r$ iterated lower shadow.

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.