A generalization of the Kruskal-Katona theorem
type: Item
instance of: scholarly article
title: A generalization of the Kruskal-Katona theorem
zbMATH Open document ID: 0539.05007
DOI: 10.1016/0097-3165(84)90025-6
author: G. F. Clements
published in: Journal of Combinatorial Theory. Series A
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05A10
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 3857118
zbMATH Keywords: Kruskal-Katona theorem
zbMATH Keywords: sets with multiple points
reviewed by: Péter Komjáth
MaRDI profile type: Publication
full work available at URL: 0097-3165(84)90025-6
OpenAlex ID: W2788003375
cites work: More on the generalized Macaulay theorem
cites work: A generalization of a combinatorial theorem of macaulay
cites work: Antichains in the set of subsets of a multiset
cites work: Q4096951
cites work: Q4096954
cites work: Q4196436
cites work: Q4052170
cites work: Q4071752
cites work: Q5726070
description: scientific article; zbMATH DE number 3857118