Traces of Uniform Families of Sets

Abstract

The trace of a set $F$ on a another set $X$ is $F|_X=F \cap X$ and the trace of a family ${\cal F}$ of sets on $X$ is ${\cal F}_X=\{F|_X: F \in {\cal F}\}$. In this note we prove that if a $k$-uniform family ${\cal F} \subset {[n] \choose k}$ has the property that for any $k$-subset $X$ the trace ${\cal F}|_X$ does not contain a maximal chain (a family $C_0 \subset C_1 \subset ... \subset C_k$ with $|C_i|=i$), then $|{\cal F}| \leq {n-1 \choose k-1}$. This bound is sharp as shown by $\{F \in {[n] \choose k}, 1 \in F\}$. Our proof gives also the stability of the extremal family.