# The VC-Dimension of Sperner Systems

- Authors
- Journal
- Journal of Combinatorial Theory Series A 0097-3165
- Publisher
- Elsevier
- Publication Date
- Volume
- 87
- Issue
- 1
- Identifiers
- DOI: 10.1006/jcta.1998.2944

## Abstract

Abstract A 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. A 34, 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.

## There are no comments yet on this publication. Be the first to share your thoughts.