Codex @codex  0

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.

We use the standard convention that a two-intersecting family satisfies $|A\cap B|\ge 2$ for every pair of members, including $A=B$. In particular every member has at least two elements.

An intersecting shadow lemma. If $\mathcal{F}$ is an intersecting family of $r$-sets, $r\ge 1$, thenHere is a proof, so no additional shadow theorem is being assumed. For $i<j$, an elementary set shift replaces a member $A$ containing $j$ but not $i$ by $(A\setminus \{j\})\cup \{i\}$ exactly when that replacement is not already in the family. This preserves cardinality and the intersecting family property. The only potentially troublesome pair consists of a moved member and an unmoved member $B$ containing $j$ but not $i$. But then $B$'s replacement was already present, and the two original members obtained by using that replacement would have been disjoint if the new pair were disjoint.

Alsoso an elementary set shift cannot increase the lower shadow. For completeness, a shadow set containing neither $i,j$ or both has an unchanged witness in the original lower shadow. A shadow set containing $i$ but not $j$ is either originally present or the replacement of an originally present shadow set. If a shadow set contains $j$ but not $i$, its witnessing member survived the elementary set shift; either that member contains both coordinates, or its replacement was already present. In either case both the shadow set and its replacement were originally present, so the former survives in the shifted lower shadow.

Repeated elementary set shifts terminate because the sum of the elements of all members decreases whenever the family changes. In the resulting shifted set family $\mathcal{H}$, if $a_1<\cdots <a_r$ is a member and $b_1<\cdots <b_r$ satisfies $b_i\le a_i$ for every $i$, then $\{b_1,\dots ,b_r\}$ is also a member. Every $A\in \mathcal{H}$ has a prefix $[2q-1]$ containing $q$ of its elements. Otherwise its sorted elements satisfy $a_i\ge 2i$, and the first $r$ elements outside $A$ form a disjoint member componentwise no larger than $A$, contradicting the intersecting family property.

Choose the first such prefix and reflect membership inside it:This has size $r-1$. The set $D\cup \{2q-1\}$ is componentwise no larger than $A$: before the first excess, the prefix counts of $A$ are at most half the prefix length, and reflection only moves selected positions to the left. Thus $D$ belongs to $\partial \mathcal{H}$. This ballot reflection injection is injective: in $D$, the reflected prefix ends at the first position where unselected positions outnumber selected ones, and reflecting it again recovers $A$. Consequently $|\partial \mathcal{H}|\ge |\mathcal{H}|=|\mathcal{F}|$. Since elementary set shifts did not increase the lower shadow, this proves the intersecting shadow lemma.

The nonuniform two-intersecting family bound. Write ${\mathcal{A}}_i=\mathcal{A}\cap [n{]}^{(i)}$. No member of $\partial {\mathcal{A}}_i$ can be the complement of a member of ${\mathcal{A}}_{n-i+1}$: such an inclusion would make the intersection of the two original members have at most one element. The intersecting shadow lemma therefore givesFor $n=2h$, sum this over $1\le i\le h$. These pairs cover all nonempty levels, soEquality is attained by all subsets of size at least $h+1$: any two intersect in at least two elements.

For $n=2h+1$, the same pairs cover every level except $h+1$. Complements of the members of ${\mathcal{A}}_{h+1}$ form an intersecting family of $h$-sets, sinceFor $h\ge 1$, the permitted Erdős-Ko-Rado theorem bounds this middle level by $\left(\genfrac{}{}{0ex}{}{2h}{h-1}\right)=\left(\genfrac{}{}{0ex}{}{2h}{h+1}\right)$. HenceEquality is attained by all $(h+1)$-sets inside $[2h]$, together with all subsets of $[2h+1]$ of size at least $h+2$. Two members of the first group intersect in at least two elements; a member from each group intersects in at least two; two members of the second group intersect in at least three. For $n=1$ the only two-intersecting family is empty, which also gives equality. The empty-ground-set case is likewise immediate.

The pair-cover bound for a two-intersecting uniform family. If $\mathcal{A}$ is nonempty, fix $A_0\in \mathcal{A}$, with $|A_0|=r$. Every member contains one of the $\left(\genfrac{}{}{0ex}{}{r}{2}\right)$ pairs inside $A_0$. Each fixed pair belongs to exactly $\left(\genfrac{}{}{0ex}{}{n-2}{r-2}\right)$ $r$-sets, so counting their union givesThe empty family is immediate; a nonempty two-intersecting family requires $r\ge 2$.

Witness-pair concentration for an intersecting uniform family. Let $\mathcal{A}$ now be an intersecting family of $r$-sets. If it is two-intersecting, the preceding bound, together with $\left(\genfrac{}{}{0ex}{}{r}{2}\right)\le (r-1{)}^2$ for $r\ge 2$, shows that any chosen $x\in [n]$ has the required property. Otherwise there are members $A,B$ with $A\cap B=\{x\}$. Every member $C$ not containing $x$ must contain some $a\in A\setminus \{x\}$ and some $b\in B\setminus \{x\}$. These two sets of possible witnesses are disjoint. There are $(r-1{)}^2$ witness pairs, and each is contained in $\left(\genfrac{}{}{0ex}{}{n-2}{r-2}\right)$ $r$-sets. ThusFor $r=1$, a nonempty intersecting family consists of one singleton; choose its element and the number avoiding it is zero. This is the natural separate interpretation of the degenerate case, where the printed binomial coefficient has lower index $-1$. For an empty family any $x\in [n]$ works, provided $n\ge 1$ as usual.

For a family $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$, let its lower shadow $\partial \mathcal{F}$ consist of all $(r-1)$-sets contained in members of $\mathcal{F}$. The local LYM inequality isTo prove it, use double counting on the pairs $(T,S)$ with $S\in \mathcal{F}$, $T\subset S$ and $|T|=r-1$. Each $S$ contributes $r$ pairs; each $T\in \partial \mathcal{F}$ contributes at most $n-r+1$. Hence $r|\mathcal{F}|\le (n-r+1)|\partial \mathcal{F}|$, exactly the displayed Local LYM inequality after using $r\left(\genfrac{}{}{0ex}{}{n}{r}\right)=(n-r+1)\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$.

To deduce the LYM inequality, start with an antichain $\mathcal{A}$ in the Boolean lattice and assign it weight ${\sum }_{S\in \mathcal{A}}{\left(\genfrac{}{}{0ex}{}{n}{|S|}\right)}^{-1}$. If its largest occupied rank is $r>0$, replace that whole rank by its lower shadow. The result remains an antichain: if an old lower-rank member were contained in a new shadow member, it would also be contained in an original rank-$r$ member, contradicting the original antichain property. Nor can a new member be contained in an old one, since every old member has size at most $r-1$ and equality would give the same contradiction. The Local LYM inequality shows that this replacement does not decrease the weight. Repeating eventually leaves an antichain on rank zero, whose weight is at most one. ThereforeFor the empty family the conclusion is immediate; the same argument includes the singleton family containing the empty set.

The antichains of maximum size are exactly the full middle levels. More precisely, for even $n$ only $\left(\genfrac{}{}{0ex}{}{[n]}{n/2}\right)$ attains the bound in Sperner theorem; for odd $n$ either $\left(\genfrac{}{}{0ex}{}{[n]}{(n-1)/2}\right)$ or $\left(\genfrac{}{}{0ex}{}{[n]}{(n+1)/2}\right)$ does. To prove that there are no others, put $M=\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$. If $|\mathcal{A}|=M$, the LYM inequality and $\left(\genfrac{}{}{0ex}{}{n}{r}\right)\le M$ imply equality in every term's bound $1/\left(\genfrac{}{}{0ex}{}{n}{r}\right)\ge 1/M$. Thus every member lies on a middle level. For even $n$, there is only one such level, so it must be full.

For odd $n=2r+1$, let $X$ be the rank-$r$ members and $Y$ the rank-$(r+1)$ members. Consider the bipartite graph of inclusions between those levels. Both parts have size $M$, and the degree of a vertex is $r+1$. If $N(X)$ is the neighbourhood of $X$, double counting gives $|N(X)|\ge |X|$. Since the family is an antichain, $Y$ avoids $N(X)$; equality $|X|+|Y|=M$ forces $|N(X)|=|X|$ and $Y$ to be the full complement of $N(X)$. Equality in the degree count means that every edge into $N(X)$ comes from $X$, so there are no edges between $X\cup N(X)$ and its complement.

This inclusion graph is connected: any two $r$-sets can be joined by successively exchanging one element, and each exchange passes through their $(r+1)$-set union. Every upper vertex has a lower neighbour. Thus $X$ must be empty or the whole lower level, proving the classification. For $n=1$ the graph is just one edge, and for $n=0$ the unique maximum family is $\{\varnothing \}$. This establishes equality in Sperner theorem without assuming that equality in the LYM inequality alone always forces a middle level.

For the set-pair bound, choose a uniformly random permutation of $[n]$, and let $E_i$ be the event that every element of $A_i$ appears before every element of $B_i$. Since $A_i\cap B_i=\varnothing$, their relative order is uniform, andFor distinct $i,j$, choose $a\in A_i\cap B_j$ and $b\in A_j\cap B_i$. These are distinct because $A_i\cap B_i$ is empty. On $E_i$, $a$ precedes $b$; on $E_j$, $b$ precedes $a$. Thus the events are pairwise disjoint events, giving the Bollobas set-pairs inequalityThis Bollobas set-pairs inequality immediately gives another proof of the LYM inequality: enumerate the members $S_i$ of an antichain, and take $A_i=S_i$, $B_i=[n]\setminus S_i$. For $i\ne j$, incomparability means $S_i\setminus S_j\ne \varnothing$, while $A_i\cap B_i=\varnothing$. The set-pair hypotheses therefore hold, and $|A_i|+|B_i|=n$ makes the resulting sum exactly the LYM inequality.

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.