A generalization of the Kruskal-Katona theorem (Q793732): Difference between revisions

If \(k_ n\leq k_{n-1}\leq...\leq k_ 1\) are fixed positive integers \(\left( \begin{matrix} j\\ i\end{matrix} \right)\) denotes the coefficient of \(x^ i\) in \(\prod^{j}_{r=1}(1+x+...+x^{k_ r}).\) (For \(k_ n=...=k_ 1=1\) this reduces to ordinary binomial coefficients.) If \(\ell,m\) are given with 1\(\leq m\leq\left( \begin{matrix} n\\ \ell \end{matrix} \right)\) and \(1\leq \ell \leq k_ n+...+k_ 1\), then there exist integers \(m(\ell),m(\ell -1),...,m(t)\) with \(m=\left( \begin{matrix} m(\ell)\\ \ell \end{matrix} \right)+\left( \begin{matrix} m(\ell -1)\\ \ell -1\end{matrix} \right)+...+\left( \begin{matrix} m(t)\\ t\end{matrix} \right), t>0\), \(m(\ell)\geq...\geq m(t)\), \(\left( \begin{matrix} m(t)\\ t\end{matrix} \right)>0\), if \(t<i\leq \ell\) and e satisfy \(m(i)=m(i-1)=...=m(i-e)\), then \(e<k_{m(i)+1}\). This array \(m(\ell),...,m(t)\) is unique. If there are m \(\ell\)-weight subsets of a multiset with multiplicities \(\{k_ n,...,k_ 1\}\) then they contain at least \(\left( \begin{matrix} m(\ell)\\ \ell -1\end{matrix} \right)+...+\left( \begin{matrix} m(t)\\ t-1\end{matrix} \right)\) (\(\ell -1)\)-weight subsets.