Affordable Access

Publisher Website

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.

Statistics

Seen <100 times
0 Comments

More articles like this

Sperner families of bounded VC-dimension

on Discrete Mathematics Jan 01, 1997

The VC-dimension of set systems defined by graphs

on Discrete Applied Mathematics Jan 01, 1997
More articles like this..