Traces of uniform families of sets

Balázs Patkós

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

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.

Détail

DOI : 10.37236/246

Classification : 05D05
Mots-clés : trace of a set, trace of a familiy of sets, uniform familiy, maximal chain, sharp bound, extremal family