The VC-dimension of Sperner systems

A family F of subsets of a finite set X shatters a set D subset of or equal to X, if the intersections of the members of F with D coincide with the po wer 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. A 34, 4 1-45) investigates the behavior of the maximum size of a Sperner family hav ing bounded VC-dimension and conjectures that if F subset of or equal to 2( [m]) is a Sperner family of VC-dimension less than 0 < d less than or equal to m/2 + 1 then \F\ less than or equal to ((m)(d-1)). Recently this conjec ture 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-dimens ion of Sperner families and give an upper bound on the maximum size of a fa mily of dimension d(m) (where d(m) m/2 > m/2 if m greater than or equal to 7). This bound is shown to be tight for infinitely many values of m with ex plicit constructions. (C) 1999 Academic Press.