✦ LIBER ✦

The VC-Dimension of Sperner Systems

✍ Scribed by G. Greco

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 119 KB
Volume: 87
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1998.2944

No coin nor oath required. For personal study only.

✦ Synopsis

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 0mÂ2 if m 7). This bound is shown to be tight for infinitely many values of m with explicit constructions.
1999 Academic Press

1. TERMINOLOGY AND NOTATION

A set system F 2 [m] , [m]=[1, 2, ..., m], is a Sperner system if for every two members of the system none contains the other (i.e., F is an antichain in the boolean lattice). A chain is a sequence of sets A i [m], 0 i n such that
A chain is complete if n=m and |A i | =i for every 0 i m.
If D is a subset of [m] the trace of F on D is
If F| D =2 D we say that F shatters D. The maximum size of a set shattered by F is the Vapnik Chervonenkis dimension (VC-dimension) of the system [10] and it is denoted by d VC (F). We recall that for every pair of positive

📜 SIMILAR VOLUMES

Sperner families of bounded VC-dimension

✍ R.P. Anstee; A. Sali 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 344 KB

We explore a problem of Frankl (1989). A family ~ of subsets of {1, 2, ..., m} is said to have trace Kk if there is a subset SC\_{1,2 ..... m} with IS] = k so that {FNSIF C .~} yields all 2 k possible subsets. Frankl (1989) conjectured that a family ~ which is an antichain (in poser given by C\_ ord

On the complexity of approximating the V

On the complexity of approximating the VC dimension

✍ Elchanan Mossel; Christopher Umans 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 181 KB

We study the complexity of approximating the VC dimension of a collection of sets, when the sets are encoded succinctly by a small circuit. We show that this problem is: 3 -hard to approximate to within a factor 2 À e for all e > 0; \* approximable in AM to within a factor 2; and \* AM-hard to appr

Exact VC-dimension of Boolean monomials

✍ Thomas Natschläger; Michael Schmitt 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 166 KB

The Systems Vc and Vd of Xe2

✍ K. Tsukiyama 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 100 KB

Minimum matrix representation of Sperner

Minimum matrix representation of Sperner systems

✍ F.E. Bennett; L. Wu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 483 KB

Let X be an n-element set and 2' be the family of subsets of X. If&C c 2' such that for any K. K\_ F .%'" K. f K\_ it-dim K. ct K. then Wr is ca!!pd a Sn~rtwr wstem Let \_M be 8~ ,+\_ x g \_\_l'\_\_L-~" '\_\_I , \_\_' \_\_\_\_=\_\_ \_\_ \_\_I i \_\_' \_ .

Polynomial Bounds for VC Dimension of Si

Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks

✍ Marek Karpinski; Angus Macintyre 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 438 KB

We introduce a new method for proving explicit upper bounds on the VC dimension of general functional basis networks and prove as an application, for the first time, that the VC dimension of analog neural networks with the sigmoidal activation function \_( y)=1Â1+e & y is bounded by a quadratic poly