= Solution
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 representation>
$$
m=\binom{a_r}{r}+\binom{a_{r-1}}{r-1}+\cdots+\binom{a_j}{j},\qquad
a_r>a_{r-1}>\cdots>a_j\geq j\geq1.
$$
The <Kruskal-Katona theorem> states that
$$
\boxed{|\mathcal F|=m\quad\Longrightarrow\quad
|\partial\mathcal F|\geq\binom{a_r}{r-1}+\binom{a_{r-1}}{r-2}+\cdots+\binom{a_j}{j-1}.}
$$
For $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 claim
$$
\partial C_{U,V}(\mathcal F)\subseteq C_{U,V}(\partial\mathcal F).
$$
Consider a <lower shadow> member obtained by deleting $z$ from a moved <set> $A'=(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'\setminus\{x\}\cup\{y\}$, which is in $\mathcal F$ by the assumed invariance. Thus $A'\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'=(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'$. When $z=x\in U$, the smaller compression of $A$ belongs to $\mathcal F$ and equals $B'\cup\{y\}$. In either case $B'$ 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 weight
$$
w(\mathcal F)=\sum_{A\in\mathcal F}\sum_{i\in A}2^i,
$$
because 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 $\binom{a_r}{r}\leq 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-\binom{a_r}{r}$. By <Pascal's identity>, the remainder is smaller than $\binom{a_r}{r-1}$, so its next leading top index is strictly less than $a_r$. Repeating gives the stated unique <binomial representation>. The first block contributes all $\binom{a_r}{r-1}$ $(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> is
$$
16=\binom64+\binom33.
$$
The proved theorem gives at least $\binom63+\binom32=23$ triples in its first <lower shadow>. Apply it again to any twenty-three of those triples, using $23=\binom63+\binom32$. Their <edge> <lower shadow> has at least
$$
\binom62+\binom31=18
$$
members, contradicting the fifteen available <edges>. Conversely, the <complete graph> $K_6$ has $\binom62=15$ <edges> and $\binom64=15$ copies of $K_4$. Therefore \b[the maximum number of copies is exactly 15].
Back to article page
