On the shadow of squashed families of $k$-sets

  • Frédéric Maire

Abstract

The shadow of a collection ${\cal A}$ of $k$-sets is defined as the collection of the $(k-1)$-sets which are contained in at least one $k$-set of ${\cal A}$. Given $|{\cal A}|$, the size of the shadow is minimum when ${\cal 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.

Published
1995-08-25
Article Number
R16