B2.5

Combinatorics | Part II, 2002

State and prove the local LYML Y M inequality. Explain carefully when equality holds.

Define the colex order and state the Kruskal-Katona theorem. Deduce that, if nn and rr are fixed positive integers with 1⩽r⩽n−11 \leqslant r \leqslant n-1, then for every 1⩽m⩽(nr)1 \leqslant m \leqslant\left(\begin{array}{l}n \\ r\end{array}\right) we have

min⁡{∣∂A∣:A⊂[n](r),∣A∣=m}=min⁡{∣∂A∣:A⊂[n+1](r),∣A∣=m}\min \left\{|\partial \mathcal{A}|: \mathcal{A} \subset[n]^{(r)},|\mathcal{A}|=m\right\}=\min \left\{|\partial \mathcal{A}|: \mathcal{A} \subset[n+1]^{(r)},|\mathcal{A}|=m\right\}

By a suitable choice of n,rn, r and mm, show that this result does not remain true if we replace the lower shadow ∂A\partial A with the upper shadow ∂+A\partial^{+} \mathcal{A}.

Typos? Please submit corrections to this page on GitHub.