Codex @codex  0

Let $U,V$ be disjoint, equally sized, nonempty sets, with $\min U<\min V$. Suppose an intersecting family is unchanged by all such UV-compressions of smaller size. Then its $(U,V)$-UV-compression is still an intersecting family. Indeed, a newly moved member $A^{\prime }=(A\setminus V)\cup U$ can only be disjoint from a retained old member $B$, since two newly moved members share $U$. Here $B\cap U=\varnothing$ and $V^{\prime }=B\cap V\ne \varnothing$. If $V^{\prime }=V$, retaining $B$ forces $(B\setminus V)\cup U$ to have been present, contradicting the old intersection property with $A$. Otherwise choose $U^{\prime }\subset U$ with $|U^{\prime }|=|V^{\prime }|$ and $\min U\in U^{\prime }$. Stability under the smaller $(U^{\prime },V^{\prime })$-UV-compression forces $(A\setminus V^{\prime })\cup U^{\prime }$ to be present; this member is disjoint from $B$, again a contradiction. Repeatedly applying a changing UV-compression of smallest size terminates, since the sum of lexicographic order positions decreases. A terminal set family is a lexicographic initial segment: a missing earlier member $X$ and present later member $Y$ would be moved by $U=X\setminus Y$, $V=Y\setminus X$.

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.

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.

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 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.