×

Shadows of colored complexes. (English) Zbl 0651.05003

Let \({\mathcal F}\) be a family of k-subsets of a set V. The shadow of \({\mathcal F}\), \(\Delta\) \({\mathcal F}\) is defined by \(\Delta\) \({\mathcal F}=S\subset V:\) \(| S| =k-1\), \(S\subset T\in {\mathcal F}\}\). The well-known Kruskal- Katona Theorem determines the minimum cardinality of \(\Delta\) \({\mathcal F}\) as a function of the cardinality of \({\mathcal F}\). A family \({\mathcal F}\) is r- colored if there exists a partition of V, \(V=V_ 1\cup V_ 2...V_ r\) such that for every \(S\in {\mathcal F}\) and every \(1\leq i\leq r\), \(| V_ i\cap S| \leq 1\). The minimum size of the shadow of an r-colored family of k-sets \({\mathcal F}\), \(| {\mathcal F}| =m\) is determined. These results generalize the Kruskal-Katona Theorem, and imply (combined with known results) a complete description of f-vectors of completely balanced Cohen-Macaulay complexes.
Reviewer: Z.Füredi

MSC:

05A05 Permutations, words, matrices
PDFBibTeX XMLCite
Full Text: DOI EuDML