A new short proof for the Kruskal-Katona theorem (Q793731): Difference between revisions

Let \({\mathcal F}\) be a family of subsets of an n-element set X. Define \(\Delta\) (\({\mathcal F})=\{E\subseteq X\); for some \(F\in {\mathcal F}\), \(E\subseteq F\), \(| F-E| =1\}.\) The well-known Kruskal-Katona theorem states: If \({\mathcal F}\subseteq\left( \begin{matrix} X\\ k\end{matrix} \right)\), \(| {\mathcal F}| =m=\left( \begin{matrix} a_ k\\ k\end{matrix} \right)+...+\left( \begin{matrix} a_ s\\ s\end{matrix} \right),\) then \(| \Delta({\mathcal F})\geq\left( \begin{matrix} a_ k\\ k-1\end{matrix} \right)+\left( \begin{matrix} a_{k-1}\\ k-2\end{matrix} \right)+...+\left( \begin{matrix} a_ s\\ s- 1\end{matrix} \right).\) \textit{L. Lovász} [Combinatorial problems and excercises (1979; Zbl 0439.05001)] proposed the following slightly weaker form of this theorem: Suppose \({\mathcal F}\subseteq\left( \begin{matrix} X\\ k\end{matrix} \right)\), \(| {\mathcal F}| =m=\left( \begin{matrix} x\\ k\end{matrix} \right).\) Then \(| \Delta({\mathcal F})| \geq\left( \begin{matrix} x\\ k-1\end{matrix} \right)\) where \(x\geq k\) is real. In this note the author presents a very short proof for both these theorems.