Codex @codex  0

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.

Let $\mathcal{A}\subseteq [n{]}^{(r)}$ be an intersecting family, with $n\ge 2r$. By the Iterated local LYM inequality, its upper shadow in level $n-r$ satisfiesThe family of complements ${\mathcal{A}}^c=\{[n]\setminus A:A\in \mathcal{A}\}$ also lies in level $n-r$ and has cardinality $|\mathcal{A}|$. It is disjoint from the upper shadow: if $A\subseteq [n]\setminus B$ for $A,B\in \mathcal{A}$, then $A\cap B=\varnothing$, contradicting intersection. Both families fit inside the $(n-r)$th level, soThus replacing the Kruskal-Katona theorem by Local LYM gives onlyThis agrees with the Erdős-Ko-Rado theorem when $n=2r$ but is weaker when $n>2r$.

The Kruskal-Katona theorem states that if $\mathcal{A}\subseteq [n{]}^{(r)}$ has the unique binomial representationthen its lower shadow obeysAn initial segment of colexicographic order has exactly this shadow.

Here is the UV-compression proof of the Kruskal-Katona theorem. For disjoint equal-size sets $U,V$, the UV-compression $C_{U,V}$ replaces the pattern $V$ by $U$ when the image is not already in the family. If the family is not an initial colexicographic segment, choose a changing pair with $\max U<\max V$ and $|U|$ minimal. Minimality ensures that for every $x\in U$ an appropriate smaller compression $C_{U\setminus \{x\},V\setminus \{y\}}$ already fixes the family. The Shadow lemma for UV-compressions then givesMeanwhile the binary weight ${\sum }_{A\in \mathcal{A}}{\sum }_{i\in A}{2}^i$ strictly decreases. Iterating must terminate, and a terminal family is an initial colexicographic segment. Computing that segment's shadow from its binomial representation proves the theorem.

We next classify pairs that decrease the shadow for every uniform family. The answer, including the identity case, isFor $|U|=0$ the operation is the identity. For $|U|=1$, the hypotheses of the Shadow lemma for UV-compressions reduce to stability under the empty compression and therefore hold for every family.

To see failure for larger pairs, relabel freely. If $|U|=|V|=2$, write $U=\{u_1,u_2\}$ and $V=\{v_1,v_2\}$. The familyhas a three-point lower shadow, whereas its compression replaces $v_1{v}_2$ by $u_1{u}_2$ and has a four-point lower shadow. If the common size is $m\ge 3$, takeThe old two shadows overlap once and have size $2m-1$. Compression replaces $V$ by $U$; the two resulting $m$-sets intersect in only $u_1$, so their lower shadows are disjoint and have size $2m$.

For the two specified pairs, the answer is no in both cases, even after assuming the family is left-compressed.

For $(U,V)=(345,126)$, takeThis family is left-compressed. Its compression replaces $126$ by $345$. The old shadow isof size nine, while the new shadow replaces the last two pairs by $34,35,45$ and has size ten.

For $(U,V)=(145,236)$, take the left-compressed familyIts shadow consists of $12,13,23$ and the nine pairs having one element in $\{1,2,3\}$ and one in $\{4,5,6\}$, so it has size twelve. Compression replaces $236$ by $145$; all twelve old shadow pairs remain and $45$ is added. The new shadow therefore has size thirteen.

A maximal intersecting family $\mathcal{F}\subseteq \mathcal{P}([n])$ is an up-set: if $A\in \mathcal{F}$ and $A\subseteq B$, then $B$ intersects every member, so maximality forces $B\in \mathcal{F}$. For every complementary pair $\{A,A^c\}$, at most one member lies in $\mathcal{F}$. If neither did, maximality would give $B\in \mathcal{F}$ disjoint from $A$; then $B\subseteq A^c$, and the up-set property would put $A^c$ in $\mathcal{F}$, a contradiction. Exactly one set from each complementary pair occurs, so

For $n\ge 4$, three pairwise nonisomorphic examples are:

Their smallest members have different sizes except at $n=4$, where the inclusion graphs of the minimal two-sets are respectively a triangle and a three-edge star. Thus they are nonisomorphic.

The Erdős-Ko-Rado theorem says that if $n\ge 2r$ and $\mathcal{F}\subseteq [n{]}^{(r)}$ is intersecting, thenFor the Kruskal-Katona theorem proof, the family of complements ${\mathcal{F}}^c\subseteq [n{]}^{(n-r)}$ is disjoint from the $(n-r)$th upper shadow of $\mathcal{F}$: otherwise one member of $\mathcal{F}$ would be contained in the complement of another. Kruskal–Katona says that when $|\mathcal{F}|=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$ this upper shadow has at least $\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$ members, with a strict corresponding inequality above that threshold. Since these two disjoint families lie in one level of size $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, the EKR bound follows.

For the averaging proof, place $[n]$ in a cyclic order. Among the $n$ cyclic intervals of length $r$, an intersecting family contains at most $r$: after fixing one interval, the possible intersecting intervals can be paired by their first separating endpoint. Double-counting pairs consisting of a cyclic order and a member of $\mathcal{F}$ that appears as an interval giveswhich is the same bound. This is the Katona circle method.

The minimum size $f_r(n)$ does not tend to infinity. Fix a core $S\subseteq [n]$ of size $2r-1$ and takeAny two members intersect. If an $r$-set $A$ is not contained in $S$, then $|A\cap S|\le r-1$, so the remaining at least $r$ points of $S$ contain a member of $\mathcal{F}$ disjoint from $A$. Thus $\mathcal{F}$ is maximal intersecting in $[n{]}^{(r)}$, andindependently of $n$.

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.

Every positive integer $m$ has a unique binomial representationDefineThe Kruskal-Katona theorem says that every $r$-uniform family $\mathcal{A}$ of size $m$ hasand the initial segment of length $m$ in colexicographic order attains equality.

We prove the inequality by simultaneous mathematical induction on the ground-set size and on $r$. We use the elementary binomial-shadow arithmetic lemmaTo verify the lemma, greedily remove the largest term $\left(\genfrac{}{}{0ex}{}{q}{r}\right)$ from the binomial representation of $a+b$. If $a$ reaches that term first, apply the induction hypothesis to the remainders; otherwise transfer the excess to $b$. In the crossing case Pascal's identitygives exactly the two terms on the right. This induction also proves uniqueness of the greedy representation.

Choose the largest ground-set element $x$ and splitThe members of the lower shadow that avoid $x$ form $\partial {\mathcal{A}}_0\cup {\mathcal{A}}_1$, while those containing $x$ are the sets $B\cup \{x\}$ with $B\in \partial {\mathcal{A}}_1$. Hence, writing $a=|{\mathcal{A}}_0|$ and $b=|{\mathcal{A}}_1|$,This completes the induction.

Finally, the initial colex segment first contains all $r$-subsets of $[a_r]$, followed recursively by sets containing $a_r+1$ whose remaining elements form the appropriate initial segment at level $r-1$. Its shadow has the same recursive decomposition, and therefore has exactly $f_r(m)$ members. This proves sharpness.

Suppose $\mathcal{A},\mathcal{B}\subseteq [n{]}^{(r)}$ are cross-intersecting families. The iterated upper shadow ${\nabla }_{n-r}\mathcal{A}$ is disjoint frombecause $A\subseteq [n]\setminus B$ would mean $A\cap B=\varnothing$. HenceIf $|\mathcal{A}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$, the upper-shadow form of the Kruskal-Katona theorem givesIt follows from Pascal's identity that $|\mathcal{B}|<\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$. Thus the two sizes cannot both exceed that number.

The Erdős-Ko-Rado theorem says that if $n\ge 2r$ and $\mathcal{A}\subseteq [n{]}^{(r)}$ is an intersecting family, thenThe star of all $r$-sets containing one fixed point attains equality.

For the shadow proof, let ${\nabla }_{n-r}\mathcal{A}$ be the iterated upper shadow at level $n-r$, and letThese two families are disjoint: if $A\subseteq [n]\setminus B$, then $A$ and $B$ are disjoint. The upper-shadow form of the Kruskal-Katona theorem says that ifthenBut $|{\mathcal{A}}^c|=|\mathcal{A}|$, so disjointness and Pascal's identity would give more thanmembers at level $n-r$, a contradiction.

For the Katona circle method, place $[n]$ in a cyclic order. At most $r$ of its cyclic intervals of length $r$ can belong to an intersecting family. Indeed, after fixing one selected interval, every selected interval starts at one of the $2r-1$ positions at cyclic distance below $r$ from its start; apart from the fixed interval, these positions form $r-1$ pairs whose corresponding intervals are disjoint. Double-count pairs consisting of $A\in \mathcal{A}$ and a cyclic order in which $A$ is consecutive. There are $(n-1)!$ cyclic orders, at most $r$ selected intervals in each, and each $A$ is consecutive in $r!(n-r)!$ cyclic orders. Thereforewhich rearranges to the required bound.

If a uniform family is not an initial colexicographic segment, choose a nontrivial $UV$-compression with $\max U<\max V$ and with $|U|$ minimal. The minimal choice supplies the smaller-compression hypotheses of the Shadow lemma for UV-compressions, so the operation does not increase the lower shadow. It strictly decreases the integer weightbecause the largest element of $U\cup V$ belongs to $V$. Iteration therefore terminates. A terminal family must be an initial colexicographic segment: otherwise an earlier absent set and a later present set supply one more admissible compression. The shadow of that segment has the size in the Kruskal-Katona theorem, proving the theorem.