The VC-Dimension of Sperner Systems

AbstractA family F of subsets of a finite set X shatters a set D⊆X, if the intersections of the members of F with D coincide with the power set of D. The maximum size of a set shattered by F is the VC-dimension (or density) of the system. P. Frankl (1983, J. Combin. Theory Ser. A34, 41–45) investigates the behavior of the maximum size of a Sperner family having bounded VC-dimension and conjectures that if F⊆2[m] is a Sperner family of VC-dimension less than 0<d⩽m/2+1 then |F|⩽ [[formula]]. Recently this conjecture has been proved true for d=2, 3, 4 by R. P. Anstee and A. Sali (1997, Discrete Math.175, 13–21). We evaluate the maximum d(m) of the VC-dimension of Sperner families and give an upper bound on the maximum size of a family of dimension d(m) (where d(m)>m/2 if m⩾7). This bound is shown to be tight for infinitely many values of m with explicit constructions