Set family shadow

A shadow moves a uniform set family to an adjacent level of the subset lattice by deleting or adding one element.

The lower shadow of $\mathcal{A}\subseteq [n{]}^{(r)}$ is

Repeatedly take the lower shadow of a uniform set family. After $j$ steps the result consists of all subsets of its members whose size is $j$ smaller. Iterating the Kruskal-Katona theorem shows that colexicographic initial segments minimize every iterated lower shadow.

For the uniform set family of vertex sets of $r$-cliques, its $(r-2)$-fold lower shadow consists of graph edges. Repeated use of the Kruskal-Katona theorem bounds clique count from edge count. Sixteen four-cliques have at least twenty-three triples in their shadow and at least eighteen edges in their second shadow, by the expansions $16=\left(\genfrac{}{}{0ex}{}{6}{4}\right)+\left(\genfrac{}{}{0ex}{}{3}{3}\right)$ and $23=\left(\genfrac{}{}{0ex}{}{6}{3}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)$. Hence a graph with fifteen edges has at most fifteen four-cliques, attained by the complete graph on six vertices.

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

For a nonempty $r$-uniform set family, define $x>r-1$ by $|\mathcal{F}|=\left(\genfrac{}{}{0ex}{}{x}{r}\right)$ using real binomial coefficients. Then its lower shadow has at least $\left(\genfrac{}{}{0ex}{}{x}{r-1}\right)$ members. This continuous estimate is often easier to use than the exact integer expansion in the Kruskal-Katona theorem.

A short proof uses coordinate shifts of a set family. In a fully left-shifted set family split at coordinate one into ${\mathcal{F}}_0$ and ${\mathcal{F}}_1$, deleting one in the present section. The shifting property implies $\partial {\mathcal{F}}_0\subseteq {\mathcal{F}}_1$, and the total lower shadow has size $|{\mathcal{F}}_1|+|\partial {\mathcal{F}}_1|$. Induct on uniformity and, at fixed uniformity, on set family size. If $|{\mathcal{F}}_1|<\left(\genfrac{}{}{0ex}{}{x-1}{r-1}\right)$, the Pascal's identity and the size mathematical induction force $|\partial {\mathcal{F}}_0|>\left(\genfrac{}{}{0ex}{}{x-1}{r-1}\right)$, a contradiction. The uniformity mathematical induction applied to ${\mathcal{F}}_1$, followed by the Pascal's identity, proves the estimate. Integer $x$ is sharp for the full $r$-level on $x$ coordinates.

Split a uniform set family into the section avoiding a coordinate and the section containing it, with that coordinate removed. Replace each section by a colexicographic initial segment of the same size. Induction on the ground-set size, and nesting of initial segments, show that this operation cannot enlarge the lower shadow.

Let $f_r(m)$ be the lower-shadow size prescribed by the binomial representation in the Kruskal-Katona theorem. ThenInduction using Pascal's identity proves the inequality and drives the standard ground-set induction for the theorem.

Let $U,V\subseteq [n]$ be disjoint and have the same cardinality. For a set $A$, its $UV$-compression isFor a uniform set family $\mathcal{A}$, a member is replaced only when its image is absent from $\mathcal{A}$; this convention preserves the family's cardinality.

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

A set family is left-compressed when replacing a member $j$ by a missing smaller element $i<j$ always produces another member. Equivalently, it is fixed by every $\{i\},\{j\}$-compression with $i<j$.

Suppose that for every $x\in U$ there is a $y\in V$ such that $\mathcal{A}$ is fixed by the smaller compression $C_{U\setminus \{x\},V\setminus \{y\}}$. ThenIndeed, deleting an element outside $U$ from a newly compressed member gives the $UV$-compression of an old shadow member. If the deleted element is $x\in U$, stability under the chosen smaller compression shows that the resulting set already belongs to the old lower shadow. Thusand compression preserves cardinality.

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.

The upper shadow of $\mathcal{A}\subseteq [n{]}^{(r)}$ isAmong families of fixed size, an initial lexicographic segment minimizes its upper shadow.