×

On the shadow of squashed families of \(k\)-sets. (English) Zbl 0824.05003

Electron. J. Comb. 2, Research paper R16, 6 p. (1995); printed version J. Comb. 2, 263-270 (1995).
Summary: The shadow of a collection \(\mathcal A\) of \(k\)-sets is defined as the collection of the \((k- 1)\)-sets which are contained in at least one \(k\)- set of \(\mathcal A\). Given \(| {\mathcal A}|\), the size of the shadow is minimum when \(\mathcal A\) is the family of the first \(k\)-sets in squashed order (by definition, a \(k\)-set \(A\) is smaller than a \(k\)-set \(B\) in the squashed order if the largest element of the symmetric difference of \(A\) and \(B\) is in \(B\)). We give a tight upper bound and an asymptotic formula for the size of the shadow of squashed families of \(k\)-sets.

MSC:

05A16 Asymptotic enumeration
Full Text: EuDML EMIS