A generalization of a theorem of Kruskal (Q1073037): Difference between revisions

For a set \({\mathcal A}\) of k-subsets of \(\{\) 1,...,n\(\}\) with \(| {\mathcal A}| \geq \lceil n/k\rceil\), \(\cup_{A\in {\mathcal A}}A=\{1,...,n\}\) the author determines the minimal cardinality of the \(\ell\)-shadow of \({\mathcal A}\), i.e. of the set of \(\ell\)-sets contained in the sets of \({\mathcal A}\). His result generalizes the Kruskal-Katona-Lindström theorem (KKL theorem) [see e.g. \textit{P. Frankl}, Discrete Math. 48, 327-329 (1984; Zbl 0539.05006)] by imposing the additional condition \(\cup_{A\in {\mathcal A}}A=\{1,...,n\}\). A necessary and sufficient condition is also given for the uniqueness of the solution in the KKL theorem.