= Lovász shadow bound
{c}
{title2=$|\mathcal F|=\binom xr\ \Longrightarrow\ |\partial\mathcal F|\geq\binom{x}{r-1}$}
For a nonempty $r$-<uniform set family>, define $x>r-1$ by $|\mathcal F|=\binom xr$ using real <binomial coefficients>. Then its <lower shadow> has at least $\binom{x}{r-1}$ 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|<\binom{x-1}{r-1}$, the <Pascal's identity> and the size <mathematical induction> force $|\partial\mathcal F_0|>\binom{x-1}{r-1}$, 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.
Back to article page
