Traces of Uniform Families of Sets - Patkós, Balázs (The Electronic Journal of Combinatorics, 2009)
The trace of a set F on a another set X is F|_X=F X and the trace of a family F of sets on X is F_X={F|_X: F F}. In this note we prove that if a k-uniform family F [n] k has the property that for any k-subset X the trace F|_X does not contain a maximal chain (a family C_0 C_1 ... C_k with |C_i|=i), then |F| ≤ n-1 k-1. This bound is sharp as shown by {F [n] k, 1 F}. Our proof gives also the stability of the extremal family.