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 1rn11 \leqslant r \leqslant n-1, then for every 1m(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.